bit – Cinta Programming

Manipulasi bit bagian 4: ekstraksi bit

Ekstraksi bit adalah proses pengambilan satu atau lebih bit dari sebuah bilangan. Saya contohkan dulu dalam sistem desimal sebelum masuk ke sistem biner.

Waktu kuliah, NIM saya adalah 13598054. Angka ini sebagai desimal bisa dibaca menjadi tiga belas juta lima ratus sembilan puluh delapan ribu lima puluh empat. Tapi. NIM itu bukan untuk dibaca sebagai bilangan, NIM itu dibentuk dari kode: 1 adalah jenjang (1=s1, 2=s2, 3=s3) kode 35 adalah jurusan (informatika), 98 adalah tahun masuk dan 054 adalah nomor urut saya. Dengan mengekstraksi digit desimal maka kita bisa mendapatkan makna baru dari sebuah bilangan.

Bagaimana cara mengekstraksi bagian jurusan (35) dari angka tersebut? Dengan manipulasi string, kita bisa melakukannya dengan substr/substring/fungsi sejenis. Tapi konversi ke string tidak efisien. Operasi aritmatika bisa digunakan untuk ekstraksi 2 digit jurusan.

Pertama kita bisa menggeser semua digit tahun masuk dan nomor urut (5 angka), dengan shift right 5 digit alias membagi dengan 100000 dibulatkan ke bawah. Hasilnya adlah 135. Setelah itu kita bisa menggunakan modulus 100 untuk mendapatkan angka 35.

Dalam biner, hal yang sama bisa kita lakukan. Misalnya kita ingin menyimpan tanggal (1-31) bulan (1-12) dan tahun (00-99) dalam satu angka biner. Cara penyimpanan seperti ini memungkinkan kita mengurutkan tanggal dengan mudah dan cepat.

Kita bisa menyimpan tahun dalam 7 bit (0-127) bulan dalam 4 bit (0-15) dan tanggal dalam 5 bit (0-31). Total kita butuh 16 bit.

Misalnya kita akan menyimpan tahun 12 (0001010) bulan 5 (0101) tanggal 17 (10001):

0001010 0101 10001

Atau:

0001010010110001

Jika dipandang sebagai 1 bilangan 16 bit: 5272.

Angka tersebut kelihatan jauh sekali dari angka awal kita (17-5-12).

Untuk mengekstraksi bulan. Kita perlu mengubah 5272 menjadi biner:

0001010010110001

Kita geser ke kanan sebanyak 5 untuk menghilangkan tanggal:

0000000010100101

Sekarang kita bisa menggunakan operator and untuk mengambil 4 digit terakhir:

0000000010100101

And

0000000000001111

Hasilnya

0000000000000101

Jika kita hilangkan digit 0 di depan:

101 = 5 desimal (bulan 5).

Secara umum untuk mengekstraksi bit, kita perlu menggeser ke kanan untuk menghilangkan bit yang tidak kita inginkan, lalu di-andkan dengan deretan bit 1 sebanyak bit yang ingin kita ekstrak (dalam kasus ini: 4 bit).

Posting ini ditulis dengan wordpress for blackberry sambil tiduran di waktu libur.

Manipulasi bit bagian 3: bit shift

Di bagian ini saya akan menunjukkan apa artinya menggeser bit ke kiri dan ke kanan. Waktu saya belajar konversi biner, saya mendapati bahwa cara paling mudah bagi saya dalam konversi desimal dan biner adalah dengan membayangkan “tabel” seperti ini:

128

Misalnya saya ingin mengkonversi 1001 menjadi desimal, maka saya letakkan angka 1001 tersebut di bawah tabel:

128	64	32	16	8	4	2	1
				1	0	0	1

Kita lihat bit mana saja yang nilainya satu, lalu lihat angka di atas, dalam hal ini 8 dan 1, jika dijumlahkan, hasilnya adalah 9. Jadi 1001 biner = 9 desimal.

Dengan melihat tabel seperti itu, bisa kita bayangkan apa yang terjadi jika bit-bit biner semua digeser ke kiri satu posisi. Karena di geser satu posisi, maka kita menambahkan satu digit 0 di sebelah kanan, jadi 10010.

128	64	32	16	8	4	2	1
			1	0	0	1	0

Nilainya sekarang menjadi 16 + 2 = 18 atau dua kali 9. Cara lain untuk memahami ini adalah dalam desimal (basis 10), jika kita menambahkan 0 di kanan maka nilainya menjadi 10 kali lipat, misalnya 18 menjadi 180 menjadi 1800. Demikian juga dalam biner, jika kita menggeser bit ke kiri, artinya kita menambahkan digit 0 di kanan, dan nilainya menjadi dua kalinya.

Proses di atas bisa diulangi berkali-kali. Dan proses tersebut tentunya bisa dibalik, menggeser ke kanan, dalam desimal, jika kita potong satu digit terakhir, maka nilainya akan menjadi sepersepuluhnya, misalnya 180 menjadi 18. Atau tepatnya, sepersepuluh dengan pembulatan ke bawah, karena jika kita buang angka 5 dari 185 hasilnya adalah 18. Dalam notasi biner, jika kita geser ke kanan, maka nilainya akan menjadi setengahnya (juga dengan pembulatan ke bawah).

Jadi apa kegunaan bit shifting? Salah satu kegunaannya adalah untuk perkalian dan pembagian dengan dua. Kegunaan lainnya adalah untuk ekstraksi bit (mengambil bagian bit tertentu). Mengenai ekstraksi bit, akan saya bahas di bagian berikutnya.

Manipulasi bit bagian 2: operator bit

Dalam aljabar boolean kita berurusan dengan dua nilai: 0 dan 1 (atau false dan true). Dalam aljabar boolean, ada banyak operasi, tapi biasanya kita hanya peduli pada beberapa operasi dasar: AND, OR, NOT, dan XOR. Jika kita mengkonversi bilangan desimal ke dalam bentuk biner, maka kita akan mendapatkan banyak angka 0 dan 1 (tergantung berapa besar bilangannya).

Dalam operasi bit, kita akan melakukan operasi pada tiap-tiap bit pada posisi yang sama. Jadi jika kita melakukan sebuah operasi pada dua angka 8 bit A dan B, maka: ambil bit pertama dari A, operasikan dengan bit pertama di B, lalu berikutnya ambil bit kedua dari A, lalu operasikan dengan bit kedua dari B, demikian seterusnya.

Di hampir semua bahasa pemrograman, operasi bit dilakukan sekaligus pada semua bit di sebuah register atau variabel. Berikut ini definisi beberapa operator bit yang sifatnya binary (Operasi dilakukan pada posisi bit yang sama di kedua variabel atau register tersebut):

AND: jika ada dua bit di posisi yang sama nilainya 1, maka nilai bit di posisi tersebut menjadi 1, jika tidak maka 0 (1 AND 1 = 1, 1 AND 0 = 0, 0 AND 1 = 0, 0 AND 0 = 0).
OR: jika salah satu bit atau kedua bit nilainya 1 di posisi yang sama, maka nilai bit di posisi tersebut menjadi 1, jika tidak maka 0 (1 OR 1 = 1, 1 OR 0 = 1, 0 OR 1 = 1, 0 OR 0 = 0).
XOR: jika dua bit di posisi yang sama nilainya berbeda, maka nilai bit di posisi tersebut menjadi 1, jika tidak maka 0 (1 XOR 1 = 0, 1 XOR 0 = 1, 0 XOR 1 = 1, 0 XOR 0 = 0).

Ada juga operator unary, yaitu NOT: membalik bit 0 menjadi 1 dan sebaliknya.

Beberapa contoh:

5 desimal xor 3 desimal : 0101 xor 0011 = 0110 = 6 desimal.
5 desimal or 3 desimal : 0101 or 0011 = 0111 = 7 desimal.

Contoh lebih lengkap bisa dilihat di Wikipedia.

Mengetahui operator dasar AND sudah cukup untuk memeriksa apakah suatu bilangan sifatnya ganjil atau genap. Jika kita meng-AND-kan suatu bilangan dengan 1 dan hasilnya sama dengan 1 maka bilangan tersebut adalah ganjil, jika nol maka genap.

Di tulisan berikutnya saya akan membahas mengenai bit shift dan rotate.

Manipulasi bit bagian 1: representasi biner

Kemarin buku yang saya tunggu-tunggu akhirnya tiba juga: The Art of Computer Programming, Volumes 1-4A Boxed Set (Box Set). Dulu waktu kuliah, saya sudah membaca sebagian buku ini, tapi buku ini berat di matematika, jadi kebanyakan saya hanya membaca bagian algoritmanya saja, sambil mencoba-coba sedikit latihannya. Terinspirasi dari banyak programmer di buku Coders at work yang menyukai buku ini, dan minimal memakai buku ini sebagai referensi, maka saya sekarang berusaha membaca ulang koleksi buku Knuth, plus membaca volume yang baru: Volume 4a.

Sebagai catatan: dalam wawancara Knuth sendiri tidak menyarankan seseorang membaca buku ini dari sampul ke sampul sampai habis. Saya membaca buku ini pertama skimming dulu, mencari topik menarik, setelah itu baru saya baca teliti bagian-bagian yang saya perlukan. Jadi jika Anda merasa berat membaca buku ini: coba langsung skip ke bagian yang menarik.
Lanjutkan membaca Manipulasi bit bagian 1: representasi biner