Pertanyaan Apakah operator pergeseran bitwise (bit-shift) dan bagaimana cara kerjanya?


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

Apa yang saya ingin tahu adalah, pada tingkat inti, apa yang sedikit-bergeser (<<, >>, >>>) lakukan, masalah apa yang dapat membantu memecahkan, dan apa yang terjadi di balik tikungan? Dengan kata lain, panduan pemula mutlak untuk sedikit bergeser dalam semua kebaikannya.


1189
2017-09-26 19:47


asal


Jawaban:


Operator penggeser bit melakukan persis apa yang namanya tersirat. Mereka menggeser sedikit. Berikut ini pengantar singkat (atau tidak begitu singkat) untuk operator shift yang berbeda.

Operator

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

Semua operator ini dapat diterapkan ke nilai integer (int, long, mungkin short dan byte atau char). Dalam beberapa bahasa, menerapkan operator shift ke tipe data apa pun yang lebih kecil dari int secara otomatis mengubah ukuran operan menjadi int.

Perhatikan itu <<< bukan operator, karena itu akan menjadi berlebihan. Perhatikan juga bahwa C dan C ++ tidak membedakan antara operator shift kanan. Mereka hanya menyediakan >> operator, dan perilaku pengalihan hak adalah implementasi yang ditentukan untuk jenis yang ditandatangani.


Shift kiri (<<)

Bilangan bulat disimpan, dalam memori, sebagai serangkaian bit. Misalnya, angka 6 disimpan sebagai 32-bit int akan menjadi:

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, digit telah bergeser ke kiri oleh satu posisi, dan digit terakhir di sebelah kanan diisi dengan nol. Anda mungkin juga mencatat bahwa bergeser ke kiri setara dengan perkalian dengan kekuatan 2. Jadi 6 << 1 setara dengan 6 * 2, dan 6 << 3 setara dengan 6 * 8. Kompilator pengoptimal yang baik akan menggantikan perkalian dengan pergeseran bila memungkinkan.

Non-circular shifting

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

11100000 00000000 00000000 00000000

hasil di 3,221,225,472:

11000000 00000000 00000000 00000000

Digit yang digeser "off the end" hilang. Itu tidak membungkus.


Pergeseran kanan logis (>>>)

Pergeseran kanan yang logis adalah sebaliknya ke shift kiri. Alih-alih memindahkan bit ke kiri, mereka hanya bergerak ke kanan. Misalnya, menggeser angka 12:

00000000 00000000 00000000 00001100

ke kanan oleh satu posisi (12 >>> 1) akan mendapatkan kembali 6 asli kami:

00000000 00000000 00000000 00000110

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

Bit yang hilang hilang

Namun, pergeseran tidak dapat mengambil kembali bit-bit yang "hilang". Misalnya, jika kita menggeser pola ini:

00111000 00000000 00000000 00000110

ke 4 posisi kiri (939,524,102 << 4), kami mendapat 2.147.483.744:

10000000 00000000 00000000 01100000

dan kemudian bergeser kembali ((939,524,102 << 4) >>> 4) kami mendapat 134.217.734:

00001000 00000000 00000000 00000110

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


Pergeseran kanan aritmatika (>>)

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

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

10000000 00000000 00000000 01100000

kami memiliki nomor -2,147,483,552. Mengalihkan ini ke posisi 4 yang tepat dengan pergeseran aritmetika (-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 yang logis. Dan sekali lagi, kita melihat bahwa kita melakukan pembagian dengan kekuatan 2.


1508
2017-09-26 20:46



Katakanlah kita memiliki satu byte:

0110110

Menerapkan satu bithift kiri membuat kita:

1101100

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

Bit-bit tidak bergulir; mereka dibuang. Itu berarti jika Anda meninggalkan shift 1101100 dan kemudian menggesernya, Anda tidak akan mendapatkan hasil yang sama.

Pergeseran ke kiri oleh N setara dengan mengalikan dengan 2N.

Bergeser ke kanan oleh N adalah (jika Anda menggunakan pelengkap seseorang) setara dengan membagi dengan 2N dan membulatkan ke nol.

Bitshifting dapat digunakan untuk perkalian dan pembagian cepat gila-gilaan, asalkan Anda bekerja dengan kekuatan 2. Hampir semua rutinitas grafik tingkat rendah menggunakan bitshifting.

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

memoryOffset = (row * 320) + column

Sekarang, kembali pada hari itu dan usia, kecepatan sangat penting, jadi kami akan menggunakan bitshifts untuk melakukan operasi ini.

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

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

Sekarang kita dapat mengonversinya menjadi shift kiri:

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

Untuk hasil akhir:

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

Sekarang kita mendapatkan offset yang sama seperti sebelumnya, kecuali bukannya operasi perkalian yang mahal, kita menggunakan dua bitshifts ... di x86 itu akan menjadi sesuatu seperti ini (catatan, sudah selamanya sejak saya melakukan assembly (catatan editor: diperbaiki 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 memangkas 16 siklus CPU.

Dalam mode 32 atau 64-bit, kedua versi mendapatkan jauh lebih pendek dan lebih cepat. CPU eksekusi out-of-order yang modern seperti Intel Skylake (lihat http://agner.org/optimize/) memiliki perangkat keras yang sangat cepat berkembang biak (latensi rendah dan throughput tinggi), sehingga gain jauh lebih kecil. AMD Bulldozer-keluarga sedikit lebih lambat, terutama untuk multiply 64-bit. Pada CPU Intel, dan AMD Ryzen, dua shift memiliki latensi yang sedikit lebih rendah tetapi lebih banyak instruksi daripada pengganda (yang dapat menghasilkan throughput yang 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 caranya gcc, clang, dan MSVC semua menggunakan shift + lea saat mengoptimalkan return 320*row + col;.

Hal yang paling menarik untuk dicatat di sini adalah itu x86 memiliki instruksi shift-and-add (LEA) yang dapat melakukan shift kiri kecil dan menambahkan pada saat yang sama, dengan kinerja seperti dan add petunjuk. ARM bahkan lebih kuat: satu operand dari setiap instruksi dapat di kiri atau kanan digeser secara gratis. Jadi penskalaan oleh konstanta waktu kompilasi yang dikenal sebagai kekuatan-2 dapat lebih efisien daripada banyak.


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;

Di C ++, kompiler harus melakukan ini untuk Anda jika Anda menggunakan a struct dengan dua anggota 8-bit, tetapi dalam praktiknya tidak selalu.


169
2017-09-26 19:55



Operasi bitwise, termasuk pergeseran bit, merupakan dasar untuk perangkat keras tingkat rendah atau pemrograman yang disematkan. Jika Anda membaca spesifikasi untuk perangkat atau bahkan beberapa format file biner, Anda akan melihat byte, kata-kata, dan kata sandi, dipecah menjadi bitfield non-byte, yang mengandung berbagai nilai yang menarik. Mengakses bit-fields ini untuk membaca / menulis adalah penggunaan yang paling umum.

Contoh nyata sederhana dalam pemrograman grafis adalah bahwa piksel 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 hijau HANYA, yang dimulai pada offset 5 dan berakhir pada 10 (yaitu 6-bit panjang), Anda perlu menggunakan (bit) mask, yang bila diterapkan terhadap seluruh piksel 16-bit, akan menghasilkan hanya bit yang kami minati.

#define GREEN_MASK  0x7E0

Masker yang tepat adalah 0x7E0 yang dalam biner adalah 0000011111100000 (yang 2016 dalam desimal).

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

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

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

Setelah menerapkan topeng, Anda akan mendapatkan nomor 16-bit yang sebenarnya hanya angka 11-bit karena MSB-nya berada di bit ke-11. Green sebenarnya hanya 6-bit, jadi kita perlu menskalakannya menggunakan shift yang benar (11 - 6 = 5), maka penggunaan 5 sebagai offset (#define GREEN_OFFSET 5).

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

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

83
2017-09-26 22:22



Bit Masking & Shifting

Pergeseran bit sering digunakan dalam pemrograman grafik tingkat rendah. Misalnya nilai warna piksel yang 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 diberi label 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 dapat dengan mudah mendapatkan nilai itu masking dan bergeser.

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

Yang logis & operator 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 dengan 16 tempat (Pergeseran kanan logis).

 green_value = masked_color >>> 16

Et voilá, kami memiliki integer 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,....


39
2018-03-31 10:49



Satu gotcha adalah bahwa berikut ini tergantung pada implementasi (sesuai dengan standar ANSI):

char x = -1;
x >> 1;

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

Dalam prakteknya, biasanya yang terakhir.


26
2017-09-26 20:07



Perhatikan bahwa dalam implementasi Java, jumlah bit untuk digeser adalah mod'd oleh ukuran sumber.

Sebagai contoh:

(long) 4 >> 65

sama dengan 2. Anda mungkin berharap menggeser bit ke kanan 65 kali akan mengabaikan semuanya, tetapi sebenarnya setara dengan:

(long) 4 >> (65 % 64)

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


8
2017-08-28 13:16



Saya hanya menulis kiat dan trik, mungkin berguna dalam tes / ujian.

  1. n = n*2: n = n<<1
  2. n = n/2: n = n>>1
  3. Memeriksa apakah n adalah kekuatan 2 (1,2,4,8, ...): periksa !(n & (n-1))
  4. Mendapatkan xth sedikit n: n |= (1 << x)
  5. Memeriksa apakah x genap atau ganjil: x&1 == 0 (bahkan)
  6. Alihkan nth sedikit x: x ^ (1<<n)

6
2017-10-11 22:43



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

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

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

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


-2
2017-10-23 14:28