Seberapa baik programmer yang dibutuhkan dengan operasi bit-wise? [Tutup]

Saya telah browsing beberapa kode OpenJDK baru-baru dan telah menemukan beberapa menarik potongan kode sana yang harus dilakukan dengan operasi bit-bijaksana . Aku bahkan bertanya pertanyaan tentang hal itu di StackOverflow.

Contoh lain yang menggambarkan intinya:

 1141       public static int bitCount(int i) {
 1142           // HD, Figure 5-2
 1143           i = i - ((i >>> 1) & 0x55555555);
 1144           i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
 1145           i = (i + (i >>> 4)) & 0x0f0f0f0f;
 1146           i = i + (i >>> 8);
 1147           i = i + (i >>> 16);
 1148           return i & 0x3f;
 1149       }

Kode ini dapat ditemukan di kelas Integer .

Mau tidak mau aku merasa bodoh ketika melihat ini. Apakah saya ketinggalan satu atau dua kelas di perguruan tinggi atau ini bukan sesuatu yang seharusnya saya dapatkan ? Saya dapat melakukan operasi bit-wise sederhana (seperti ANDing, ORing, XORing, shifting), tetapi ayolah, bagaimana seseorang membuat kode seperti itu di atas?

Seberapa baik programmer yang dibutuhkan dengan operasi bit-wise?

Di samping catatan ... Yang membuat saya khawatir adalah orang yang menjawab pertanyaan saya di StackOverflow menjawabnya dalam hitungan menit. Jika dia bisa melakukan itu, mengapa saya hanya menatap seperti rusa di lampu depan?

Saya akan mengatakan bahwa sebagai pengembang menyeluruh, Anda perlu memahami operator dan operasi bitwise.

Jadi, minimal, Anda harus dapat mengetahui kode di atas setelah sedikit berpikir.

Operasi bitwise cenderung tingkat yang agak rendah, jadi jika Anda bekerja di situs web dan perangkat lunak LOB, Anda tidak akan sering menggunakannya.

Seperti hal-hal lain, jika Anda tidak menggunakannya terlalu banyak, Anda tidak akan mahir menggunakannya.

Jadi, Anda tidak perlu khawatir tentang seseorang yang dapat mengetahuinya dengan sangat cepat, karena mereka (mungkin) sering menggunakan kode semacam ini. Mungkin menulis kode OS, kode driver atau manipulasi bit rumit lainnya.

Jika Anda memahami bagaimana menyelesaikan masalah seperti "menentukan apakah bit 3 dan 8 ditetapkan," "clear bit 5" atau "menemukan nilai integer yang diwakili oleh bit 7-12" Anda memiliki cukup pemahaman tentang operator bitwise untuk memeriksa Can Kotak Twiddle Bits pada daftar periksa "lengkap".

Apa yang ada dalam contoh Anda berasal dari Hacker's Delight , kompilasi algoritma berkinerja tinggi untuk memanipulasi bit kecil data seperti integer. Siapa pun yang menulis kode itu semula tidak hanya memuntahkannya dalam lima menit; cerita di baliknya lebih mungkin bahwa ada kebutuhan untuk cara cepat, bebas cabang untuk menghitung bit dan penulis punya waktu untuk menghabiskan menatap string bit dan memasak cara untuk memecahkan masalah. Tidak ada yang akan mengerti cara kerjanya sekilas kecuali mereka sudah melihatnya sebelumnya. Dengan pemahaman yang kuat tentang dasar-dasar bitwise dan beberapa waktu yang dihabiskan untuk bereksperimen dengan kode, Anda mungkin bisa mengetahui bagaimana ia melakukan apa yang dilakukannya.

Bahkan jika Anda tidak memahami algoritme ini, hanya dengan mengetahui algoritma itu ada menambah "kebulatan" Anda karena ketika saatnya tiba untuk berurusan dengan, katakanlah, penghitungan bit berkinerja tinggi, Anda tahu apa yang harus dipelajari. Di dunia pra-Google, jauh lebih sulit untuk mengetahui hal-hal ini; sekarang penekanan tombol pergi.

Pengguna yang menjawab pertanyaan SO Anda mungkin telah melihat masalah sebelumnya atau telah mempelajari hashing. Tulis dia dan tanyakan.

Dari contoh Anda ada beberapa hal yang harus Anda ketahui tanpa benar-benar berpikir.

1143 i = i - ((i >>> 1) & 0x55555555);

Anda harus mengenali pola bit 0x555 ... sebagai pola bit berganti-ganti 0101 0101 0101 dan bahwa operator mengimbangi dengan 1 bit (ke kanan), dan itu & adalah operasi masking (dan apa yang dimaksud masking berarti).

1144 i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);

Sekali lagi sebuah pola, yang ini adalah 0011 0011 0011. Juga bergeser dua kali ini dan menutupi lagi. pergeseran dan penutup mengikuti pola yang harus Anda kenali ...

1145 i = (i + (i >>> 4)) & 0x0f0f0f0f;

polanya membeku. Kali ini 00001111 00001111 dan, tentu saja, kami menggesernya 4 kali ini. setiap kali kita bergeser berdasarkan ukuran topeng.

1148 mengembalikan i & 0x3f;

pola bit lain, 3f adalah blok nol diikuti oleh blok yang lebih besar.

Semua hal ini harus terlihat jelas jika Anda "Lengkap". Bahkan jika Anda tidak pernah berpikir Anda akan menggunakannya, Anda mungkin akan kehilangan beberapa peluang untuk menyederhanakan kode Anda jika Anda tidak tahu ini.

Bahkan dalam bahasa tingkat yang lebih tinggi, bit patters digunakan untuk menyimpan JAUH jumlah data yang lebih besar di bidang yang lebih kecil. Inilah sebabnya mengapa Anda selalu melihat batas 127/8, 63/4 dan 255/6 dalam permainan, itu karena Anda harus menyimpan begitu banyak hal ini sehingga tanpa mengemas bidang Anda akan dipaksa untuk menggunakan sebanyak sepuluh kali lipat dari jumlah memori. (Ya, yang paling penting adalah jika Anda perlu menyimpan sejumlah besar boolean dalam array, Anda bisa menghemat 32-64 kali jumlah memori yang akan Anda gunakan jika Anda tidak memikirkannya - sebagian besar bahasa menerapkan boolean sebagai sebuah kata yang akan sering menjadi 32 bit. Mereka yang merasa tidak nyaman pada level ini akan menolak peluang untuk menyimpan data seperti ini hanya karena mereka takut akan hal yang tidak diketahui.

Mereka juga akan menghindar dari hal-hal seperti paket parsing manual yang dikirim melalui jaringan dalam format yang dikemas - sesuatu yang sepele jika Anda tidak takut. Ini bisa mengambil permainan yang membutuhkan paket 1k turun hingga membutuhkan 200 byte, paket yang lebih kecil akan meluncur melalui jaringan lebih efisien dan menurunkan latensi dan memungkinkan kecepatan interaksi yang lebih tinggi (yang memungkinkan seluruh mode permainan baru untuk suatu permainan).

Saya kebetulan mengenali kode itu karena saya pernah melihatnya di perangkat lunak untuk memanipulasi bingkai video. Jika Anda secara teratur bekerja dengan hal-hal seperti audio dan video CODEC, protokol jaringan, atau register chip, Anda akan melihat banyak operasi bitwise dan itu akan menjadi kebiasaan Anda.

Anda seharusnya tidak merasa sedih jika pekerjaan Anda tidak sering terjadi bersamaan dengan domain tersebut. Saya tahu operasi bitwise dengan baik, tapi saya memperlambat jalan pada kesempatan langka saya perlu menulis GUI, karena semua kebiasaan dengan tata letak dan pembobotan dan pengembangan dan sedemikian rupa sehingga saya yakin merupakan sifat kedua bagi orang lain. Kekuatan Anda adalah di mana pun Anda memiliki pengalaman paling banyak.

hal utama yang harus Anda waspadai adalah bagaimana bilangan bulat diwakili (secara umum bitvector dengan panjang tetap di mana panjangnya tergantung pada platform) dan operasi apa yang tersedia pada mereka

operasi aritmatika utama + - * / %dapat dipahami tanpa perlu memahaminya meskipun dapat berguna untuk optimasi mikro (meskipun sebagian besar waktu kompiler akan dapat mengurusnya untuk Anda)

set manipulasi bit | & ~ ^ << >> >>>membutuhkan setidaknya pemahaman yang lewat untuk dapat menggunakannya

Namun sebagian besar waktu Anda hanya akan menggunakannya untuk melewati flag bit ke metode sebagai ORing bersama-sama dan melewati int dan kemudian ANDmengeluarkan pengaturan lebih mudah dibaca daripada melewati beberapa (hingga 32) boolean dalam daftar parameter panjang dan memungkinkan bendera yang mungkin berubah tanpa mengubah antarmuka

belum lagi booleans umumnya disimpan secara terpisah dalam byte atau int bukannya mengemasnya seperti flag

Adapun potongan kode itu melakukan penghitungan paralel dari bit ini memungkinkan algoritma untuk berjalan di O(log(n))mana n adalah jumlah bit bukannya loop naif yangO(n)

langkah pertama adalah yang paling sulit untuk dipahami tetapi jika Anda mulai dari pengaturan itu harus mengganti urutan bit 0b00ke 0b00, 0b01ke 0b01, 0b10ke 0b01dan 0b11untuk 0b10itu menjadi lebih mudah untuk diikuti

jadi untuk langkah pertama i - ((i >>> 1) & 0x55555555)jika kita anggap isama dengan 0b00_01_10_11maka output dari ini seharusnya0b00_01_01_10

(perhatikan bahwa 0x5sama dengan 0b0101)

IUF kita mengambil i = 0b00_01_10_11ini berarti bahwa 0b00_01_01_10 - (0b00_00_11_01 & 0b01_01_01_01)adalah 0b00_01_10_11 - 0b00_00_01_01yang pada gilirannya menjadi0b00_01_01_10

mereka bisa melakukan (i & 0x55555555) + ((i >>> 1) & 0x55555555)untuk hasil yang sama tetapi ini adalah 1 operasi tambahan

langkah-langkah berikut berada dalam nada yang sama

Setiap orang harus memahami operasi bit-wise dasar. Ini adalah komposisi operasi dasar untuk melakukan tugas dengan cara yang optimal dan kuat yang membutuhkan banyak latihan.

Mereka yang bekerja dengan manipulasi bit setiap hari (seperti orang yang disematkan), tentu saja, akan mengembangkan intuisi yang kuat dan sekumpulan trik yang bagus.

Berapa banyak keterampilan yang harus dimiliki seorang programmer yang tidak melakukan hal-hal tingkat rendah dengan manipulasi bit-wise? Cukup untuk bisa duduk dengan bait seperti yang Anda tempelkan dan mengerjakannya perlahan-lahan seolah itu adalah asah otak atau teka-teki.

Dengan cara yang sama, saya akan mengatakan bahwa seorang programmer yang tertanam harus memahami sebanyak tentang http sebagai pengembang web mengerti tentang manipulasi bit-bijaksana. Dengan kata lain itu "OK" untuk tidak menjadi ahli manipulasi bit jika Anda tidak menggunakannya sepanjang waktu.

Kegembiraan hacker adalah karya turunan. Nenek moyang semua adalah HakMem dari 1972. http://w3.pppl.gov/~Hammett/work/2009/AIM-239-ocr.pdf

Yang penting adalah mengetahui bahwa algoritma yang jelas untuk tugas apa pun belum tentu yang terbaik. Ada banyak kasus di mana mengetahui keberadaan solusi elegan untuk masalah partucular adalah yang penting.

Seberapa sulitkah operator bitwise untuk menafsirkan?

Saya memprogram sistem tertanam. Saya sudah banyak berlatih hal ini. Pertanyaan Anda yang ditautkan tentang peta hash dengan kode

static int hash(int h) {
   // This function ensures that hashCodes that differ only by
   // constant multiples at each bit position have a bounded
   // number of collisions (approximately 8 at default load factor).
   h ^= (h >>> 20) ^ (h >>> 12);
   return h ^ (h >>> 7) ^ (h >>> 4);
}

masuk akal bagi saya di sekitar selama diperlukan untuk mendikte kode dengan keras. Peristiwa yang dijelaskan dalam bitCountsegera jelas, tetapi butuh satu menit untuk mencari tahu mengapa itu benar-benar menghitung bit. Komentar akan sangat bagus, dan akan membuat pemahaman apa yang dilakukan kode hanya sedikit lebih keras daripada masalah hash.

Penting untuk membuat perbedaan antara membaca dan memahami kode. Saya dapat menafsirkan bitCountkode, dan membacakan apa yang dilakukannya, tetapi membuktikan mengapa ia bekerja atau bahkan yang berfungsi akan membutuhkan waktu sebentar. Ada perbedaan antara bisa membaca kode dengan lancar dan bisa mengerti mengapa kodenya seperti itu. Beberapa algoritma cukup sulit. The apa dari hashkode masuk akal, tapi komentar menjelaskan mengapa apa yang sedang dilakukan. Jangan berkecil hati jika fungsi menggunakan operator bitwise sulit dimengerti, mereka sering digunakan untuk melakukan hal-hal matematika yang rumit yang akan sulit terlepas dari formatnya.

Sebuah analogi

Saya sudah terbiasa dengan hal ini. Satu hal yang saya tidak terbiasa adalah regex. Saya kadang-kadang berurusan dengan mereka dalam membangun skrip, tetapi tidak pernah dalam pekerjaan pengembangan sehari-hari.

Saya tahu cara menggunakan elemen regex berikut:

• [] kelas karakter
• The *, .dan +wildcard
• Mulai dari string ^dan akhir string$
• Kelas karakter \ d, \ w, dan
• Bendera / g

Ini cukup untuk membuat pertanyaan sederhana, dan banyak dari pertanyaan yang saya lihat tidak menyimpang jauh dari ini.

Apa pun yang tidak ada dalam daftar ini, saya meraih lembar contekan. Apa pun, kecuali {}dan ()- Lembar contekan tidak akan cukup. Saya tahu cukup banyak tentang orang-orang ini untuk mengetahui bahwa saya akan membutuhkan papan tulis, manual referensi, dan mungkin rekan kerja. Anda dapat mengemas beberapa algoritma gila ke dalam beberapa baris pendek regex.

Untuk merancang regex yang membutuhkan atau menyarankan apa pun yang tidak ada dalam daftar elemen yang diketahui, saya akan mencantumkan semua kelas input yang saya harapkan untuk dikenali dan memasukkannya ke dalam test suite. Saya akan membuat regex secara perlahan dan bertahap, dengan banyak langkah yang terputus-putus, dan melakukan langkah-langkah ini untuk mengendalikan sumber dan / atau meninggalkannya dalam komentar sehingga saya bisa mengerti apa yang seharusnya terjadi nanti ketika rusak. Jika ada dalam kode produksi, saya akan memastikan bahwa kode tersebut ditinjau oleh seseorang yang lebih berpengalaman.

Apakah ini tempat Anda bersama operator bitwise?

Jadi, Anda ingin berpengetahuan luas?

Menurut perkiraan saya, jika Anda dapat menafsirkan kode seperti apa yang dilakukan dengan menarik selembar kertas atau pergi ke papan tulis dan menjalankan operasi secara manual, Anda memenuhi syarat sebagai berpengetahuan luas. Untuk memenuhi syarat sebagai programmer yang berpengetahuan luas di bidang operasi bitwise Anda harus dapat melakukan empat hal:

1. Dapat membaca dan menulis operasi umum dengan lancar
   Untuk programmer aplikasi, operasi umum dengan operator bitwise mencakup operator dasar |dan &untuk mengatur dan menghapus tanda. Ini seharusnya mudah. Anda harus dapat membaca dan menulis hal-hal seperti

   open('file', O_WRONLY | O_APPEND | O_CREAT );
   // Use an OR operator ^ here and ^ here to set multiple flags
   

   tanpa melambat (dengan asumsi Anda tahu apa artinya bendera ).

2. Mampu membaca operasi yang lebih kompleks dengan beberapa pekerjaan
   Menghitung bit sangat cepat dalam waktu O (log (n)) tanpa cabang, memastikan bahwa jumlah tabrakan dalam kode hash dapat berbeda dengan jumlah yang dibatasi, dan menguraikan alamat email , nomor telepon , atau HTML dengan regex adalah masalah yang sulit. Adalah masuk akal bagi siapa saja yang bukan ahli dalam bidang ini untuk meraih papan tulis, tidak masuk akal untuk tidak dapat mulai bekerja untuk memahami.

3. Mampu menulis beberapa algoritma kompleks dengan banyak pekerjaan.
   Jika Anda bukan seorang ahli, Anda seharusnya tidak dapat melakukan hal-hal yang kompleks dan sulit. Namun, seorang programmer yang baik harus dapat menyelesaikannya dengan bekerja terus menerus. Lakukan ini cukup, dan Anda akan segera menjadi ahli :)

Jika Anda masuk ke universitas yang layak, Anda seharusnya diminta mengambil kelas dalam Matematika Diskrit. Anda akan belajar gerbang biner, oktal, dan heksadesimal dan gerbang logika.

Pada catatan itu adalah normal untuk merasa bingung dengan itu, jika itu merupakan penghiburan bagi Anda karena saya menulis aplikasi web terutama saya jarang perlu melihat atau menulis kode seperti ini, tetapi karena saya mengerti aritmatika biner dan perilaku operator bitwise Saya akhirnya bisa mengetahui apa yang terjadi di sini dengan waktu yang cukup.

Sebagai seorang programmer ponsel saya harus berurusan dengan hal semacam ini. Ini cukup umum di mana perangkat tidak memiliki banyak memori, atau di mana kecepatan transmisi penting. Dalam kedua kasus, Anda berupaya mengemas informasi sebanyak mungkin ke dalam beberapa byte.

Saya tidak ingat menggunakan operator bitwise dalam 5 tahun atau lebih dari PHP (mungkin itu hanya saya), tidak dalam 10 tahun atau lebih pemrograman Windows, meskipun beberapa hal Windows tingkat lebih rendah tidak paket bit.

Anda mengatakan "Saya tidak bisa menahan perasaan bodoh ketika saya melihat ini". JANGAN - merasa marah.

Anda baru saja memenuhi output dari programmer koboi.

Apakah dia tidak tahu apa-apa tentang menulis kode yang bisa dipelihara? Saya sungguh berharap bahwa dia adalah orang yang harus kembali ke sini dalam setahun dan mencoba dan mengingat apa artinya.

Saya tidak tahu apakah Anda memotong komentar atau jika tidak ada, tetapi kode ini tidak akan lulus tinjauan kode di mana saya adalah manajer QA s / w (dan saya telah beberapa kali).

Inilah aturan praktis yang bagus - satu-satunya "bilangan bulat telanjang" yang diizinkan dalam kode adalah 0 1. Semua angka lainnya harus #define, biaya, enum, dll, tergantung pada bahasa Anda.

Jika 3 dan 0x33333333 mengatakan sesuatu seperti NUM_WIDGET_SHIFT_BITS dan WIDGET_READ_MASK, kodenya akan lebih mudah dibaca.

Malu siapa pun yang meletakkan ini dalam proyek open source, tetapi bahkan untuk komentar kode pribadi dengan baik dan menggunakan definisi / enum yang bermakna dan memiliki standar pengkodean Anda sendiri.

Sepotong kode khusus ini diambil langsung dari buku Hacker's Delight , gambar 5.2. Ini online di C (fungsi pop) di sini . Perhatikan penulis sekarang merekomendasikan menggunakan versi yang diperbarui: http://www.hackersdelight.org/HDcode/newCode/pop_arrayHS.c.txt

Jika Anda ingin mempelajari optimasi mikro semacam ini, saya sarankan buku itu; itu menyenangkan, tetapi kecuali jika Anda melakukan pemrograman bit tingkat sangat rendah sering Anda mungkin tidak akan memahaminya; dan sebagian besar waktu kompiler Anda akan dapat melakukan banyak optimasi semacam ini untuk Anda.

Ini juga membantu untuk menulis ulang semua angka heksadesimal dalam biner untuk memahami algoritma semacam ini dan bekerja melalui mereka pada satu atau dua test case.

Penjelasan dengan contoh. Data adalah urutan bit. Mari kita hitung bit pada byte 01001101 yang memiliki operasi berikut tersedia: 1. Kita dapat memeriksa nilai bit terakhir. 2. Kita bisa menggeser urutannya.

1. 01001101 -> byte terakhir adalah 1, total = 1. bergeser
2. 10100110 -> byte terakhir adalah 0, total = 1. bergeser
3. 01010011 -> byte terakhir adalah 1, total = 2. bergeser
4. 10101001 -> byte terakhir adalah 1, total = 3. bergeser
5. 11010100 -> byte terakhir adalah 0, total = 3. bergeser
6. 01101010 -> byte terakhir adalah 0, total = 3. bergeser
7. 00110101 -> byte terakhir adalah 1, total = 4. bergeser
8. 10011010 -> byte terakhir adalah 0, total = 4. bergeser

Jawaban kami: 4.

Ini tidak sulit, bukan? Masalah besar dengan operasi bitwise adalah bahwa ada hal-hal terbatas yang dapat kita lakukan. Kami tidak dapat mengakses sedikit secara langsung. Tapi kita bisa, misalnya, mengetahui nilai bit terakhir membandingkannya dengan MASK 00000001 dan kita bisa membuat setiap bit menjadi yang terakhir dengan operasi shift. Tentu saja, algoritma yang dihasilkan akan terlihat menakutkan bagi mereka yang tidak terbiasa. Tidak ada hubungannya dengan kecerdasan.

Saya tidak akan mengatakan Anda membutuhkannya kecuali pekerjaan yang Anda lakukan terkait dengan:

• Pemrosesan audio
• Pemrosesan video
• Grafik
• Jaringan (khususnya di mana ukuran paket penting)
• Sejumlah besar data

Menyimpan izin dalam flag unix style juga merupakan kegunaan lain untuk itu, jika Anda memiliki model izin yang sangat rumit untuk sistem Anda, atau benar-benar ingin menjejalkan semuanya ke dalam satu byte, dengan mengorbankan keterbacaan.

Selain dari bidang-bidang itu saya akan menghitungnya sebagai nilai tambah besar jika pengembang / pengembang senior dapat menunjukkan pergeseran bit, dan menggunakan | & dan ^ karena menunjukkan minat pada profesi yang dapat Anda katakan mengarah pada kode yang lebih stabil dan andal.

Sejauh tidak 'mendapatkan' metode pada pandangan pertama, seperti yang disebutkan Anda perlu penjelasan tentang apa yang dilakukannya dan latar belakang. Saya tidak akan mengatakan itu terkait dengan kecerdasan tetapi seberapa akrab Anda dengan bekerja dengan heksadesimal setiap hari dan mengenali masalah yang dapat dipecahkan oleh pola tertentu.