Apa gunanya operator bit? [Tutup]

Bahasa pemrograman sering kali datang dengan berbagai operator bit (mis., Bitwise left- and right shift, bitwise AND, OR, XOR ...). Ini tidak digunakan meskipun sangat banyak, atau setidaknya seperti pengalaman saya. Mereka kadang-kadang digunakan dalam tantangan pemrograman atau pertanyaan wawancara, atau solusi mungkin memerlukannya, misalnya:

• Tanpa menggunakan operator kesetaraan, buat fungsi yang kembali trueketika dua nilai sama
• Tanpa menggunakan variabel ketiga, tukar nilai dua variabel

Ini sekali lagi, mungkin memiliki sedikit kegunaan dunia nyata . Saya kira mereka harus lebih cepat karena mereka secara langsung memanipulasi memori pada level rendah.

Mengapa seperti itu ditemukan di sebagian besar bahasa pemrograman? Adakah kasus penggunaan dunia nyata?

Tidak, mereka memiliki banyak aplikasi dunia nyata, dan operasi mendasar pada komputer.

Mereka digunakan untuk

• Menyulap blok byte di sekitar yang tidak cocok dengan tipe data bahasa pemrograman
• Beralih encoding bolak-balik dari big ke little endian.
• Mengemas 4 keping data 6bit menjadi 3 byte untuk beberapa koneksi serial atau usb
• Banyak format gambar memiliki jumlah bit berbeda yang ditetapkan untuk setiap saluran warna.
• Apa pun yang melibatkan pin IO dalam aplikasi tertanam
• Kompresi data, yang seringkali tidak memiliki data yang sesuai dengan batas 8-bit yang bagus. \
• Algoritma Hashing, CRC atau pemeriksaan integritas data lainnya.
• Enkripsi
• Generasi nomor psuedorandom
• Raid 5 menggunakan bitor XOR antara volume untuk menghitung paritas.
• Banyak lagi

Faktanya, secara logis, semua operasi pada komputer pada akhirnya bermuara pada kombinasi operasi bitwise tingkat rendah ini, yang terjadi di dalam gerbang listrik prosesor.

Karena mereka operasi mendasar.

Dengan alur pemikiran yang sama, Anda dapat berargumen bahwa penambahan memiliki sedikit kegunaan di dunia nyata, karena dapat diganti sepenuhnya dengan pengurangan (dan negasi) dan multiplikasi. Tetapi kami terus menambahkan karena ini adalah operasi yang mendasar.

Dan jangan berpikir sejenak bahwa hanya karena Anda belum melihat banyak kebutuhan untuk operasi bitwise tidak berarti mereka tidak terlalu sering digunakan. Memang, saya telah menggunakan operasi bitwise di hampir setiap bahasa yang saya gunakan untuk hal-hal seperti bit masking.

Dari atas kepala saya, saya telah menggunakan operasi bitwise untuk pemrosesan gambar, bitfields dan flags, pemrosesan teks (misalnya, semua karakter dari kelas tertentu sering berbagi pola bit yang umum), pengkodean dan decoding data serial, decoding VM atau CPU opcodes, dan sebagainya. Tanpa operasi bitwise, sebagian besar tugas ini akan membutuhkan operasi yang lebih kompleks berkali-kali untuk melakukan tugas dengan kurang andal atau dengan keterbacaan yang lebih buruk.

Sebagai contoh:

// Given a 30-bit RGB color value as a 32-bit int
// A lot of image sensors spit out 10- or 12-bit data
// and some LVDS panels have a 10- or 12-bit format
b = (color & 0x000003ff);
g = (color & 0x000ffc00) >> 10;
r = (color & 0x3ff00000) >> 20;

// Going the other way:
color = ((r << 20) & 0x3ff00000) | ((g << 10) & 0x000ffc00) | (b & 0x000003ff);

Mendekode instruksi CPU untuk CPU tipe RISC (seperti ketika meniru platform lain) membutuhkan penggalian bagian-bagian dengan nilai besar seperti di atas. Kadang-kadang, melakukan operasi ini dengan multiplikasi dan pembagian dan modulo, dll., Bisa sepuluh kali lebih lambat dari operasi bitwise yang setara.

Contoh khas adalah mengekstraksi warna individual dari nilai RGB 24 bit dan kembali.

EDIT: Dari http://www.docjar.com/html/api/java/awt/Color.java.html

    value =  ((int)(frgbvalue[2]*255 + 0.5))    |
                (((int)(frgbvalue[1]*255 + 0.5)) << 8 )  |
                (((int)(frgbvalue[0]*255 + 0.5)) << 16 ) |
                (((int)(falpha*255 + 0.5)) << 24 );

Inilah contoh dunia nyata yang akan Anda temukan di Quake 3, Quake 4. Doom III. Semua game yang menggunakan mesin Q3 .

float Q_rsqrt( float number )
{
        long i;
        float x2, y;
        const float threehalfs = 1.5F;

        x2 = number * 0.5F;
        y  = number;
        i  = * ( long * ) &y;                       // evil floating point bit level hacking [sic]
        i  = 0x5f3759df - ( i >> 1 );               // what the fuck? [sic]
        y  = * ( float * ) &i;
        y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration
//    y  = y * ( threehalfs - ( x2 * y * y ) );   // 2nd iteration, this can be removed

        return y;
}

(Untuk memahami kode yang Anda perlu memahami bagaimana angka floating point disimpan, saya pasti tidak bisa menguraikannya)

Dalam hal penggunaan, kecuali jika Anda berada di bidang yang memerlukan sedikit pergeseran seperti jaringan atau grafik, maka Anda mungkin menemukan tujuannya sedikit akademis. Tapi tetap menarik (bagi saya minimal).

Pergeseran lebih cepat daripada mengalikan atau membaginya dengan kekuatan dua. Misalnya, a << = 2 mengalikan a dengan 4. Sebaliknya, a >> = 2 membagi a dengan empat. Seseorang juga dapat menggigit data ke perangkat menggunakan operator bit-bijaksana. Sebagai contoh, kita dapat mengirim stream data serial N dari port N pin menggunakan operasi shift, xor, dan "dan" di dalam loop N. Apa pun yang dapat dicapai dalam logika digital juga dapat dicapai pada perangkat lunak dan sebaliknya.

Dahulu kala, operator bit bermanfaat. Hari ini mereka kurang begitu. Oh mereka tidak sepenuhnya tidak berguna, tapi sudah lama sejak saya melihat satu yang seharusnya digunakan.

Pada tahun 1977 saya adalah seorang programmer bahasa assembly. Saya yakin assembler adalah satu-satunya bahasa yang benar. Saya yakin bahwa bahasa seperti Pascal adalah untuk para akademisi yang tidak pernah harus melakukan sesuatu yang nyata .

Lalu saya membaca "Bahasa Pemrograman C" oleh Kernighan dan Ritchie. Itu mengubah pikiran saya sepenuhnya. Alasannya? Itu operator bit! Itu adalah bahasa assembly! Itu hanya memiliki sintaks yang berbeda.

Kembali pada masa itu saya tidak bisa membayangkan menulis kode tanpa ands, ors, shift, dan rotates. Saat ini saya hampir tidak pernah menggunakannya.

Jadi, jawaban singkat untuk pertanyaan Anda adalah: "Tidak ada." Tapi itu tidak adil. Jadi jawaban yang lebih panjang adalah: "Kebanyakan tidak ada."

Enkripsi

Saya sarankan melihat cuplikan yang sangat kecil dari algoritma enkripsi DES :

temp = ((left >>> 1) ^ right) & 0x55555555; right ^= temp; left ^= (temp << 1);
temp = ((right >>> 8) ^ left) & 0x00ff00ff; left ^= temp; right ^= (temp << 8);
temp = ((right >>> 2) ^ left) & 0x33333333; left ^= temp; right ^= (temp << 2);
temp = ((left >>> 16) ^ right) & 0x0000ffff; right ^= temp; left ^= (temp << 16);
temp = ((left >>> 4) ^ right) & 0x0f0f0f0f; right ^= temp; left ^= (temp << 4);

Banyak jawaban bagus, jadi saya tidak akan mengulangi kegunaan itu.

Saya menggunakannya cukup banyak dalam kode terkelola (C # / .Net), dan itu tidak ada hubungannya dengan penghematan ruang, kinerja tinggi atau algoritma bit shifting yang pintar. Kadang-kadang beberapa logika cocok untuk menyimpan data dengan cara ini. Saya sering menggunakannya ketika saya memiliki enum tetapi instans dapat secara bersamaan mengambil beberapa nilai dari enum itu. Saya tidak dapat memposting contoh kode dari kantor, tetapi google cepat untuk "Flags enum" ("Flags" adalah cara C # untuk mendefinisikan enum untuk digunakan dalam cara bitwise) memberikan contoh yang bagus ini: http: // www.dotnetperls.com/enum-flags .

Ada juga komputasi paralel bit. Jika data Anda hanya 1 dan 0, Anda bisa mengemas 64 dari kata-kata yang panjang dan tidak bertanda, dan mendapatkan operasi paralel 64 arah. Informasi genetik adalah dua bit (mewakili pengkodean AGCT dari DNA), dan jika Anda dapat melakukan berbagai perhitungan dengan cara paralel, Anda dapat melakukan lebih banyak daripada jika tidak. Belum lagi kepadatan data dalam memori-jika memori, atau kapasitas disk, atau bandwidth komunikasi terbatas menyiratkan bahwa kompresi / dekompresi harus dipertimbangkan. Bahkan integer precison rendah, yang muncul di area seperti pemrosesan gambar, dapat mengambil keuntungan dari komputasi paralel bit yang rumit. Ini adalah keseluruhan seni itu sendiri.

Mengapa mereka ditemukan?

Yah itu mungkin karena mereka sesuai dengan instruksi perakitan dan kadang-kadang mereka hanya berguna untuk hal-hal dalam bahasa tingkat yang lebih tinggi. Hal yang sama berlaku untuk yang ditakuti GOTOyang sesuai dengan JMPinstruksi perakitan.

Apa kegunaan mereka?

Sungguh hanya ada banyak kegunaan untuk nama jadi saya hanya akan memberikan yang baru, meskipun sangat lokal, penggunaan. Saya banyak bekerja dengan 6502 perakitan dan saya sedang mengerjakan sebuah aplikasi kecil yang mengubah alamat memori, nilai, membandingkan nilai dll menjadi kode yang dapat digunakan untuk perangkat GameGenie (Pada dasarnya aplikasi cheat untuk NES). Kode dibuat oleh beberapa manipulasi bit.

Banyak programmer hari ini digunakan untuk komputer dengan memori hampir tak terbatas.

Tetapi beberapa penggunaan masih memprogram mikrokontroler kecil di mana setiap bit diperhitungkan (ketika Anda hanya memiliki 1k atau kurang RAM misalnya), dan operator bitwise memungkinkan seorang programmer untuk menggunakan bit-bit itu satu per satu alih-alih menghabiskan beberapa pemrograman yang jauh lebih besar entitas abstraksi daripada yang mungkin diperlukan untuk menahan beberapa kondisi yang diperlukan oleh algoritma. IO pada perangkat tersebut mungkin juga perlu dibaca atau dikendalikan pada basis bitwise.

"Dunia nyata" memiliki jauh lebih banyak mikrokontroler kecil daripada server atau PC.

Untuk tipe CS teoritis murni, mesin Turing adalah semua tentang bit negara.

Hanya satu lagi dari banyak kemungkinan penggunaan operator bitwise ...

Operator bitwise juga dapat membantu membuat kode Anda lebih mudah dibaca. Pertimbangkan deklarasi fungsi berikut ....

int  myFunc (bool, bool, bool, bool, bool, bool, bool, bool);

...

myFunc (false, true, false, false, false, true, true, false);

Sangat mudah untuk melupakan parameter boolean apa artinya saat menulis atau bahkan membaca kode. Juga mudah kehilangan jejak penghitungan Anda. Rutinitas seperti itu dapat dibersihkan.

/* More descriptive names than MY_FLAGx would be better */
#define MY_FLAG1    0x0001
#define MY_FLAG2    0x0002
#define MY_FLAG3    0x0004
#define MY_FLAG4    0x0008
#define MY_FLAG5    0x0010
#define MY_FLAG6    0x0020
#define MY_FLAG7    0x0040
#define MY_FLAG8    0x0080

int  myFunc (unsigned myFlags);

...

myFunc (MY_FLAG2 | MY_FLAG6 | MY_FLAG7);

Dengan nama bendera yang lebih deskriptif, itu menjadi jauh lebih mudah dibaca.

Jika Anda tahu sesuatu tentang Unicode , Anda mungkin akrab dengan UTF-8. Ini menggunakan banyak tes bit, shift dan masker untuk mengemas titik kode 20 bit menjadi 1 hingga 4 byte.

Saya tidak sering menggunakannya tetapi kadang-kadang berguna. Penanganan Enum muncul di pikiran.

Contoh:

enum DrawBorder{None = 0, Left = 1, Top = 2, Right = 4, Bottom = 8}

DrawBorder drawBorder = DrawBorder.Left | DrawBorder.Right;//Draw right & left border
if(drawBorder & DrawBorder.Left == DrawBorder.Left)
  //Draw the left border
if(drawBorder & DrawBorder.Top == DrawBorder.Top)
  //Draw the top border
//...

Tidak yakin apakah penggunaan ini telah dicatat:

Saya melihat ATAU cukup banyak ketika bekerja dengan kode sumber illumos (openSolaris) untuk mengurangi beberapa nilai pengembalian menjadi 0 atau 1, misalnya

int ret = 0;
ret |= some_function(arg, &arg2); // returns 0 or 1
ret |= some_other_function(arg, &arg2); // returns 0 or 1
return ret;