Saya sudah berusaha mempelajari C di waktu luang saya, dan bahasa lain (C #, Java, dll.) Memiliki konsep yang sama (dan seringkali operator yang sama) ...

Yang saya bertanya-tanya adalah, di tingkat inti, apa bit-pergeseran ( <<, >>, >>>) lakukan, masalah apa yang bisa ia membantu memecahkan, dan apa Gotchas mengintai di tikungan? Dengan kata lain, panduan pemula mutlak untuk sedikit mengubah semua kebaikannya.

Operator penggeser bit melakukan persis seperti namanya. Mereka menggeser bit. Berikut adalah pengantar singkat (atau tidak terlalu singkat) untuk operator shift yang berbeda.

Operator

• >> adalah operator pergeseran kanan aritmatika (atau ditandatangani).
• >>> adalah operator shift kanan yang logis (atau tidak ditandatangani).
• << adalah operator shift kiri, dan memenuhi kebutuhan shift logis dan aritmatika.

Semua operator ini dapat diterapkan untuk nilai integer ( int, long, mungkin shortdan byteatau char). Dalam beberapa bahasa, menerapkan operator shift ke semua tipe data yang lebih kecil dari intsecara otomatis mengubah ukuran operan menjadi int.

Perhatikan bahwa <<<itu bukan operator, karena itu akan berlebihan.

Perhatikan juga bahwa C dan C ++ tidak membedakan antara operator shift kanan . Mereka hanya menyediakan >>operator, dan perilaku pengalihan kanan adalah implementasi yang ditentukan untuk tipe yang ditandatangani. Sisa jawabannya menggunakan operator C # / Java.

(Dalam semua utama C dan C ++ implementasi termasuk GCC dan dentang / LLVM, >>pada jenis ditandatangani adalah aritmatika Beberapa kode mengasumsikan ini, tapi itu bukan sesuatu yang jaminan standar Ini bukan.. Terdefinisi , meskipun; standar membutuhkan implementasi untuk menentukan salah satu cara atau lainnya.Namun, meninggalkan pergeseran nomor bertanda negatif adalah perilaku yang tidak terdefinisi (ditandatangani integer overflow). Jadi, kecuali Anda memerlukan aritmatika pergeseran kanan, biasanya merupakan ide yang baik untuk melakukan bit-shifting Anda dengan tipe yang tidak ditandai.)

Shift kiri (<<)

Integer disimpan, dalam memori, sebagai serangkaian bit. Misalnya, nomor 6 yang disimpan sebagai 32-bit intadalah:

00000000 00000000 00000000 00000110

Menggeser pola bit ini ke posisi satu kiri ( 6 << 1) akan menghasilkan angka 12:

00000000 00000000 00000000 00001100

Seperti yang Anda lihat, angka telah bergeser ke kiri dengan satu posisi, dan digit terakhir di sebelah kanan diisi dengan nol. Anda mungkin juga mencatat bahwa menggeser ke kiri setara dengan perkalian dengan kekuatan 2. Begitu 6 << 1juga dengan 6 * 2, dan6 << 3 setara dengan 6 * 8. Kompilator pengoptimal yang baik akan menggantikan perkalian dengan shift jika memungkinkan.

Pergeseran non-lingkaran

Harap dicatat bahwa ini bukan pergeseran melingkar. Menggeser nilai ini ke kiri dengan satu posisi ( 3,758,096,384 << 1):

11100000 00000000 00000000 00000000

hasil dalam 3.221.225.472:

11000000 00000000 00000000 00000000

Digit yang digeser "dari ujung" hilang. Itu tidak membungkus.

Pergeseran kanan logis (>>>)

Pergeseran kanan logis adalah kebalikan dari pergeseran kiri. Alih-alih memindahkan bit ke kiri, mereka hanya bergerak ke kanan. Misalnya, menggeser angka 12:

00000000 00000000 00000000 00001100

ke kanan dengan satu posisi ( 12 >>> 1) akan mengembalikan 6 asli kami:

00000000 00000000 00000000 00000110

Jadi kita melihat bahwa bergeser ke kanan setara dengan pembagian dengan kekuatan 2.

Bit hilang hilang

Namun, pergeseran tidak bisa mendapatkan kembali bit yang "hilang". Misalnya, jika kita menggeser pola ini:

00111000 00000000 00000000 00000110

ke 4 posisi kiri ( 939,524,102 << 4), kita mendapatkan 2.147.483.744:

10000000 00000000 00000000 01100000

dan kemudian bergeser kembali ( (939,524,102 << 4) >>> 4) kita dapatkan 134.217.734:

00001000 00000000 00000000 00000110

Kami tidak bisa mendapatkan kembali nilai asli kami setelah kehilangan bit.

Aritmatika bergeser kanan (>>)

Pergeseran kanan aritmatika persis seperti pergeseran kanan logis, kecuali alih-alih bantalan dengan nol, itu bergeser dengan bit yang paling signifikan. Ini karena bit yang paling signifikan adalah bit tanda , atau bit yang membedakan angka positif dan negatif. Dengan mengisi dengan bit yang paling signifikan, pergeseran kanan aritmatika adalah mempertahankan tanda.

Misalnya, jika kita menafsirkan pola bit ini sebagai angka negatif:

10000000 00000000 00000000 01100000

kami memiliki nomor -2.147.483.552. Menggeser ini ke posisi 4 kanan dengan perubahan aritmatika (-2,147.483.552 >> 4) akan memberi kita:

11111000 00000000 00000000 00000110

atau angka -134.217.722.

Jadi kita melihat bahwa kita telah mempertahankan tanda angka negatif kita dengan menggunakan pergeseran kanan aritmatika, daripada pergeseran kanan logis. Dan sekali lagi, kita melihat bahwa kita melakukan pembagian dengan kekuatan 2.

Katakanlah kita memiliki satu byte:

0110110

Menerapkan satu bithift kiri memberi kita:

1101100

Nol paling kiri digeser keluar dari byte, dan nol baru ditambahkan ke ujung kanan byte.

Bit tidak terguling; mereka dibuang. Itu berarti jika Anda meninggalkan shift 1101100 dan kemudian shift kanan, Anda tidak akan mendapatkan hasil yang sama kembali.

Pergeseran ditinggalkan oleh N setara dengan mengalikan dengan 2 ^N .

Menggeser kanan oleh N adalah (jika Anda menggunakan komplemen yang ) adalah sama dengan membagi dengan 2 ^N dan pembulatan ke nol.

Bitshifting dapat digunakan untuk perkalian dan pembagian yang sangat cepat, asalkan Anda bekerja dengan kekuatan 2. Hampir semua rutinitas grafis tingkat rendah menggunakan bitshifting.

Misalnya, pada masa lalu, kami menggunakan mode 13j (320x200 256 warna) untuk game. Dalam Mode 13h, memori video diletakkan berurutan per piksel. Itu berarti menghitung lokasi untuk piksel, Anda akan menggunakan matematika berikut:

memoryOffset = (row * 320) + column

Sekarang, pada zaman itu, kecepatan sangat penting, jadi kami akan menggunakan bithift untuk melakukan operasi ini.

Namun, 320 bukan kekuatan dua, jadi untuk mengatasi ini kita harus mencari tahu apa kekuatan dua yang ditambahkan bersama membuat 320:

(row * 320) = (row * 256) + (row * 64)

Sekarang kita bisa mengubahnya menjadi shift kiri:

(row * 320) = (row << 8) + (row << 6)

Untuk hasil akhir dari:

memoryOffset = ((row << 8) + (row << 6)) + column

Sekarang kita mendapatkan offset yang sama seperti sebelumnya, kecuali alih-alih operasi perkalian yang mahal, kita menggunakan dua bithifts ... di x86 itu akan menjadi sesuatu seperti ini (catatan, sudah selamanya sejak saya melakukan perakitan (catatan editor: dikoreksi beberapa kesalahan dan menambahkan contoh 32-bit)):

mov ax, 320; 2 cycles
mul word [row]; 22 CPU Cycles
mov di,ax; 2 cycles
add di, [column]; 2 cycles
; di = [row]*320 + [column]

; 16-bit addressing mode limitations:
; [di] is a valid addressing mode, but [ax] isn't, otherwise we could skip the last mov

Total: 28 siklus pada CPU kuno apa pun yang memiliki timing ini.

Vrs

mov ax, [row]; 2 cycles
mov di, ax; 2
shl ax, 6;  2
shl di, 8;  2
add di, ax; 2    (320 = 256+64)
add di, [column]; 2
; di = [row]*(256+64) + [column]

12 siklus pada CPU kuno yang sama.

Ya, kami akan bekerja keras untuk mengurangi 16 siklus CPU.

Dalam mode 32 atau 64-bit, kedua versi menjadi jauh lebih pendek dan lebih cepat. CPU eksekusi modern out-of-order seperti Intel Skylake (lihat http://agner.org/optimize/ ) memiliki perkalian perangkat keras yang sangat cepat (latensi rendah dan throughput tinggi), sehingga keuntungannya jauh lebih kecil. AMD Bulldozer-family sedikit lebih lambat, terutama untuk 64-bit. Pada CPU Intel, dan AMD Ryzen, dua shift latensi sedikit lebih rendah tetapi lebih banyak instruksi daripada multiply (yang dapat menyebabkan throughput lebih rendah):

imul edi, [row], 320    ; 3 cycle latency from [row] being ready
add  edi, [column]      ; 1 cycle latency (from [column] and edi being ready).
; edi = [row]*(256+64) + [column],  in 4 cycles from [row] being ready.

vs.

mov edi, [row]
shl edi, 6               ; row*64.   1 cycle latency
lea edi, [edi + edi*4]   ; row*(64 + 64*4).  1 cycle latency
add edi, [column]        ; 1 cycle latency from edi and [column] both being ready
; edi = [row]*(256+64) + [column],  in 3 cycles from [row] being ready.

Compiler akan melakukan ini untuk Anda: Lihat bagaimana GCC, Dentang, dan Microsoft Visual C ++ semua menggunakan shift + lea saat mengoptimalkanreturn 320*row + col; .

Hal yang paling menarik untuk dicatat di sini adalah bahwa x86 memiliki instruksi shift-and-add ( LEA) yang dapat melakukan shift kiri kecil dan menambahkan pada saat bersamaan, dengan kinerja sebagai addinstruksi. ARM bahkan lebih kuat: satu operan dari instruksi apa pun dapat digeser ke kiri atau kanan secara gratis. Jadi penskalaan oleh konstanta waktu-kompilasi yang dikenal sebagai kekuatan-2 bisa lebih efisien daripada perkalian.

OK, kembali ke zaman modern ... sesuatu yang lebih berguna sekarang adalah menggunakan bitshifting untuk menyimpan dua nilai 8-bit dalam integer 16-bit. Misalnya, dalam C #:

// Byte1: 11110000
// Byte2: 00001111

Int16 value = ((byte)(Byte1 >> 8) | Byte2));

// value = 000011111110000;

Dalam C ++, kompiler harus melakukan ini untuk Anda jika Anda menggunakan anggota structdengan dua 8-bit, tetapi dalam praktiknya mereka tidak selalu.

Operasi bitwise, termasuk bit shift, merupakan hal mendasar untuk perangkat keras tingkat rendah atau pemrograman tertanam. Jika Anda membaca spesifikasi untuk perangkat atau bahkan beberapa format file biner, Anda akan melihat byte, kata-kata, dan kata-kata, yang dipecah menjadi bitfield yang tidak sejajar, yang berisi berbagai nilai menarik. Mengakses bit-field ini untuk membaca / menulis adalah penggunaan yang paling umum.

Contoh nyata yang sederhana dalam pemrograman grafis adalah pixel 16-bit direpresentasikan sebagai berikut:

  bit | 15| 14| 13| 12| 11| 10| 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1  | 0 |
      |       Blue        |         Green         |       Red          |

Untuk mendapatkan nilai hijau, Anda akan melakukan ini:

 #define GREEN_MASK  0x7E0
 #define GREEN_OFFSET  5

 // Read green
 uint16_t green = (pixel & GREEN_MASK) >> GREEN_OFFSET;

Penjelasan

Untuk mendapatkan nilai HANYA hijau, yang dimulai pada offset 5 dan berakhir pada 10 (yaitu panjang 6-bit), Anda perlu menggunakan masker (bit), yang bila diterapkan terhadap seluruh piksel 16-bit, akan menghasilkan hanya bit yang kami minati.

#define GREEN_MASK  0x7E0

Topeng yang sesuai adalah 0x7E0 yang dalam biner adalah 0000011111100000 (yang 2016 dalam desimal).

uint16_t green = (pixel & GREEN_MASK) ...;

Untuk menerapkan masker, Anda menggunakan operator DAN (&).

uint16_t green = (pixel & GREEN_MASK) >> GREEN_OFFSET;

Setelah menerapkan topeng, Anda akan berakhir dengan angka 16-bit yang benar-benar hanya angka 11-bit karena MSB-nya berada di bit ke-11. Hijau sebenarnya hanya panjang 6-bit, jadi kita perlu menurunkannya menggunakan shift kanan (11 - 6 = 5), maka penggunaan 5 sebagai offset (#define GREEN_OFFSET 5 ).

Juga umum menggunakan bit shift untuk perkalian dan pembagian cepat dengan kekuatan 2:

 i <<= x;  // i *= 2^x;
 i >>= y;  // i /= 2^y;

Bit Masking & Shifting

Bit shifting sering digunakan dalam pemrograman grafis tingkat rendah. Misalnya, nilai warna piksel yang diberikan dikodekan dalam kata 32-bit.

 Pixel-Color Value in Hex:    B9B9B900
 Pixel-Color Value in Binary: 10111001  10111001  10111001  00000000

Untuk pemahaman yang lebih baik, nilai biner yang sama dilabeli dengan bagian apa yang mewakili bagian warna apa.

                                 Red     Green     Blue       Alpha
 Pixel-Color Value in Binary: 10111001  10111001  10111001  00000000

Katakanlah misalnya kita ingin mendapatkan nilai hijau dari warna piksel ini. Kita bisa dengan mudah mendapatkan nilai itu dengan menutupi dan mengubah .

Topeng kami:

                  Red      Green      Blue      Alpha
 color :        10111001  10111001  10111001  00000000
 green_mask  :  00000000  11111111  00000000  00000000

 masked_color = color & green_mask

 masked_color:  00000000  10111001  00000000  00000000

&Operator logis memastikan bahwa hanya nilai-nilai di mana topeng 1 disimpan. Hal terakhir yang harus kita lakukan sekarang, adalah mendapatkan nilai integer yang benar dengan menggeser semua bit ke kanan sebanyak 16 tempat (logical right shift) .

 green_value = masked_color >>> 16

Demikian juga, kami memiliki bilangan bulat yang mewakili jumlah hijau dalam warna piksel:

 Pixels-Green Value in Hex:     000000B9
 Pixels-Green Value in Binary:  00000000 00000000 00000000 10111001
 Pixels-Green Value in Decimal: 185

Ini sering digunakan untuk encoding atau decoding format gambar seperti jpg, png, dll

Satu gotcha adalah bahwa yang berikut ini tergantung pada implementasi (menurut standar ANSI):

char x = -1;
x >> 1;

x sekarang bisa menjadi 127 (01111111) atau masih -1 (11111111).

Dalam praktiknya, biasanya yang terakhir.

Saya hanya menulis tip dan trik. Mungkin bermanfaat dalam ujian dan ujian.

1. n = n*2: n = n<<1
2. n = n/2: n = n>>1
3. Memeriksa apakah n berkekuatan 2 (1,2,4,8, ...): centang !(n & (n-1))
4. Mendapatkan x ^th menggigit dari n:n |= (1 << x)
5. Memeriksa apakah x genap atau ganjil: x&1 == 0(genap)
6. Alihkan n ^th sedikit x:x ^ (1<<n)

Perhatikan bahwa dalam implementasi Java, jumlah bit yang diubah diubah oleh ukuran sumber.

Sebagai contoh:

(long) 4 >> 65

sama dengan 2. Anda mungkin berharap menggeser bit ke kanan 65 kali akan nol semuanya, tapi itu sebenarnya setara dengan:

(long) 4 >> (65 % 64)

Ini berlaku untuk <<, >>, dan >>>. Saya belum mencobanya dalam bahasa lain.

Beberapa operasi bit / manipulasi yang berguna dalam Python.

Saya menerapkan jawaban Ravi Prakash dengan Python.

# Basic bit operations
# Integer to binary
print(bin(10))

# Binary to integer
print(int('1010', 2))

# Multiplying x with 2 .... x**2 == x << 1
print(200 << 1)

# Dividing x with 2 .... x/2 == x >> 1
print(200 >> 1)

# Modulo x with 2 .... x % 2 == x & 1
if 20 & 1 == 0:
    print("20 is a even number")

# Check if n is power of 2: check !(n & (n-1))
print(not(33 & (33-1)))

# Getting xth bit of n: (n >> x) & 1
print((10 >> 2) & 1) # Bin of 10 == 1010 and second bit is 0

# Toggle nth bit of x : x^(1 << n)
# take bin(10) == 1010 and toggling second bit in bin(10) we get 1110 === bin(14)
print(10^(1 << 2))

Ketahuilah bahwa hanya versi PHP 32 bit yang tersedia di platform Windows.

Kemudian jika Anda misalnya menggeser << atau >> lebih dari 31 bit, hasilnya tidak dapat diharapkan. Biasanya angka asli bukan nol akan dikembalikan, dan itu bisa menjadi bug yang sangat rumit.

Tentu saja jika Anda menggunakan PHP versi 64 bit (Unix), Anda harus menghindari pergeseran lebih dari 63 bit. Namun, misalnya, MySQL menggunakan BIGINT 64-bit, jadi seharusnya tidak ada masalah kompatibilitas.

PEMBARUAN: Dari PHP 7 Windows, PHP build akhirnya dapat menggunakan integer 64 bit penuh: Ukuran integer bergantung pada platform, meskipun nilai maksimum sekitar dua miliar adalah nilai biasa (yang ditandatangani 32 bit). Platform 64-bit biasanya memiliki nilai maksimum sekitar 9E18, kecuali pada Windows sebelum PHP 7, di mana selalu 32 bit.