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.

Ada satu bagian yang langsung menarik bagi saya di Volume 4A, judulnya: “Bitwise Tricks and Techniques”. Knuth menyatakan bahwa

“… Boolean operations on binary numbers deserve to be much better known. Indeed, they’re an important component of every good programmer’s toolkit.”

Kalau saya perhatikan di bangku kuliah, tidak banyak pelajaran mengenai manipulasi bit dan kegunaannya. Buat Anda yang tidak ingin membeli bukunya, Anda bisa mendapatkan bagian ini dari website Knuth (fascicle 1a).

Bagian buku itu menginspirasi saya untuk membuat beberapa tulisan tentang manipulasi bit, dan kegunaannya. Saya tidak akan mengulangi isi buku TAOCP, saya hanya akan menjelaskan beberapa hal dasar yang berguna sehari-hari. Di bagian pertama, saya hanya akan menjelaskan hal yang sangat dasar: representasi biner. Tujuannya: (1) untuk merefresh bagi yang sudah lupa (2) untuk mereka yang tidak mendapatkan pelajaran ini sama sekali.

Berbeda dari seri tutorial saya mengenai tutorial compiler, saya menuliskan ini dengan cepat, dan mungkin kurang teliti. Saya harapkan ada masukan, dan pertanyaan supaya tulisan ini lebih baik. Nantinya setelah seri ini selesai, baru akan saya pindahkan kontennya ke situs yohan.es. Dari dulu saya berniat menuliskan materi yang berhubungan dengan pemrograman, tapi jika saya menunggu sampai punya waktu untuk menulis lengkap dan baik, rasanya akan lama selesainya, jadi saya berusaha mendisiplinkan diri untuk menulis dengan cepat di blog ini.

Untuk teks yang berhubungan dengan formula matematika, saya akan menggunakan dua notasi, dengan kata, misalnya 2 pangkat N, dan dengan simbol yang dihasilkan menggunakan Latex (dalam contoh ini: ). Alasannya kenapa saya tidak menggunakan superscipt dan subscript HTML adalah: saya pernah mendapati salah satu isi blog saya dicopy paste, dan semua 2 pangkat N berubah menjadi 2N. Semoga dengan ini hal tersebut tidak terjadi (dan jika terjadi, teks masih bisa dimengerti).

Sebelum masuk bagian paling dasar, mungkin ada yang bertanya: apa sih gunanya mengetahui manipulasi bit? Jika Anda memprogram sangat high level, hanya membuat aplikasi bisnis dengan Java atau PHP, maka mungkin Anda akan sangat jarang menyentuh manipulasi bit. Tapi jika Anda memprogram low level, atau berusaha mengerti banyak algoritma, maka ini akan sangat berguna. Contoh penggunaan manipulasi bit adalah dalam enkripsi (misalnya permutasi bit) dan kompresi (misalnya huffman code, bit packing). Beberapa struktur data, misalnya bloom filter juga membutuhkan manipulasi bit dalam implementasinya.

Manipulasi bit dilakukan di level biner, jadi Anda perlu mengkonversi bilangan desimal menjadi biner untuk memahami apa yang terjadi. Saya buatkan beberapa daftar angka dari biner dari 1 sampai 10:

Biner	Desimal
0001	1
0010	2
0011	3
0100	4
0101	5
0110	6
0111	7
1000	8
1001	9
1010	10

Dalam komputer modern, satu byte terdiri dari 8 bit (ini distandarkan sekitar tahun 1975). Untuk memudahkan pembacaan, saya akan memecah setiap 8 bit menjadi masing-masing 4 bit dengan spasi, misalnya angka 5 desimal dalam 8 bit: “0000 0101”. Dalam seri tulisan ini, saya akan menggunakan asumsi bahwa kita menggunakan urutan byte “little endian“. Urutan ini digunakan di Intel yang digunakan oleh kebanyakan orang saat ini.

Untuk menyatakan bilangan negatif, biasanya kita menggunakan two’s complement. Caranya adalah mengurangi 2 pangkat N () dengan bilangan yang ingin kita negatifkan, dengan N adalah jumlah bit. Misalnya kita memakai satu byte (jumlah bit = N = 8), maka untuk menyatakan -1, kita menyimpannya sebagai ( 2 pangkat 8 ) minus 1, sama dengan 255 (), atau dalam bit biner “1111 1111”. Di memori, angka yang tercantum adalah 255, tapi bisa dipandang sebagai 255 atau -1 tergantung dari interpretasi kita. Lihat contoh program berikut ini:

#include <stdio.h>

int main()
{
        unsigned char x  = 255;
        char y = (char)x;
        printf("x = %d y = %d\n", x, y);
        return 0;
}

Jika kita kompilasi dan jalankan akan terlihat bahwa output x yang dideklarasikan sebagai unsigned char adalah 255 dan output y, yang nilainya disalin dari x, tapi dideklarasikan sebagai char adalah -1.

yohanes@koala:~$ gcc -Wall neg.c -o neg
yohanes@koala:~$ ./neg
x = 255 y = -1

Dengan cara yang sama, kita bisa mendapatkan bahwa -2 adalah 256-2 = 254. Secara umum, jika kita punya bilangan N bit yang sifatnya “signed”, kita bisa merepresentasikan −((2 pangkat (N−1))) sampai (2 pangkat (N−1))−1 atau: ( sampai ).

Perlu diperhatikan bahwa representasi two’s complement ini bergantung pada jumlah bit. Dalam bahasa C, sebuah char selalu 1 byte (standar), tapi sebuah int bisa 16 bit (2 byte), 32 bit (4 byte), dan sekarang 64 bit (8 byte), hal ini tergantung pada prosessor dan compiler yang digunakan. Misalnya C di DOS pada prosesor 8086 memakai ukuran int 16 bit.

Jika kita memakai sistem 32 bit, dengan satu int berukuran 32 bit, maka -1 adalah (2 pangkat 32) minus 1 = 4294967295 (), atau dalam biner “1111 1111 1111 1111 1111 1111 1111 1111“. Jika kita ubah program sebelumnya menjadi seperti ini:

#include <stdio.h>

int main()
{
        unsigned char x  = 255;
        char y = (char)x;
        int z = (int)y;
        int z2 = (int)x;
        unsigned int z3 = (unsigned int)z;
        printf("x = %d y = %d z= %d z2=%d\n", 
                x, y, z, z2);
        printf("z3 = %u\n", z3);
        return 0;
}

Output program adalah:

x = 255 y = -1 z= -1 z2=255
z3 = 4294967295

Ajaib bukan, tidak pernah ada angka 4294967295 di dalam program, tapi nilai itu bisa keluar. Ini yang terjadi:

pernyataan pertama baik-baik saja, , nilai x adalah 255

x = 255;

Pada yang kedua, y menjadi -1 karena y adalah signed char (8 bit)

y = x; 

Untuk pernyataan berikutnya, perlu diingat: z adalah signed, y adalah signed. Karena menyalin dari signed ke signed compiler melakukan

sign extension

compiler tahu bahwa y bernilai -1 supaya nilainya tetap -1, maka compiler membuat z bernilai -1 (dalam versi 32 bit)

z = y;

Untuk pernyataan berikutnya, z2 adalah signed, tapi 32 bit. Nilai x adalah 255, dan ini masih dalam range integer 32 bit. Nilai z2 menjadi 255, karena nilai 255 bisa ditampung oleh integer 32 bit

z2 = x;

Tambah satu variabel lagi: z3 adalah unsigned int, nilai -1 dari z di salin ke z3, tapi dinterpretasikan sebagai “unsigned” 32 bit. Artinya nilainya adalah 4294967295 (minus 1 dalam representasi 32 bit):

z3 = z; 

Sifat yang Anda lihat itu adalah sifat dalam bahasa C, dan sifat ini sangat dekat dengan sifat kebanyakan mesin. Saya tekankan bahwa itu adalah sifat C, karena berbagai bahasa punya sifat yang berbeda dalam menangani bilangan dan interpretasi bit. Di Java tidak ada tipe “unsigned”, jadi kita harus memanipulasi dengan cara lain (akan dibahas di bagian lain, karena melibatkan operator yang belum dibahas). Bahasa lain, seperti misalnya JavaScript hanya memiliki satu jenis tipe (namanya Number).

Demikian bagian pertama mengenai manipulasi bit, di bagian berikutnya saya akan membahas mengenai operator bit dasar (AND, OR, XOR, dan NOT) dan bit shifting.