Petunjuk Coding: Operasi Bit

Beberapa tulisan saya menyinggung tentang operasi pada bit, seperti pada struktur data Binary Indexed Tree dan teknik optimisasi konstanta. Tulisan ini akan membahas semua yang saya ketahui tentang operasi bit. Menguasainya akan membantu Anda dalam implementasi solusi.

---

Representasi Bit

Komputer merepresentasikan angka dalam bentuk bilangan basis 2, atau nama lainnya binary/biner. Representasi ini hanya memiliki angka 0 atau 1.
Sebuah digit pada bilangan biner disebut dengan bit.
Sebagai catatan, bilangan yang kita biasa gunakan adalah basis 10, dengan digit berkisar antara 0 sampai 9.

Perhatikan contoh bilangan biner berikut:

1001101

Digit paling kanan menyatakan banyaknya $2^0$, digit kedua dari kanan menyatakan banyaknya $2^1$, dan seterusnya. Kita dapat mengetahui nilai bilangan tersebut dalam basis 10 dengan menjumlahkan seluruh nilai yang dinyatakan setiap bit:

1 * 2^0 =  1
0 * 2^1 =  0
1 * 2^2 =  4
1 * 2^3 =  8
0 * 2^4 =  0
0 * 2^5 =  0
1 * 2^6 = 64
         ---- +
          77

Kini kita tahu hubungan antar representasi bilangan biner dan basis 10. Hubungan ini hanya berlaku untuk bilangan bulat (integer). Kita tidak membahas tentang bilangan riil, karena bentuk representasinya bergantung pada konteks.

Cara serupa dapat digunakan untuk mengubah bilangan basis 10 ke basis 2. Namun, ada algoritma yang lebih praktis:

?

1 2 3 4 5 6 7 8 9

string toBinary(int v) {   string s = "";   int x = v;   while (x > 0) {     s = to_string(x%2) + s;     x /= 2;   }   return s; }

Prinsip kerja algoritma ini akan Anda ketahui setelah memahami operasi shift right yang akan dibahas di bawah.

---

Integer 8, 16, 32, dan 64 Bit

Bahasa pemrograman yang mengharuskan tipe data variabel umumnya menyediakan tipe data bilangan bulat dalam 8 bit, 16 bit, 32 bit, dan 64 bit. Sebagai contoh, berikut tipe data pada C++:

• 8 bit: char
• 16 bit: short
• 32 bit: int
• 64 bit: long long

Jika suatu bilangan memiliki x bit, artinya tipe tersebut dapat merepresentasikan 2^x nilai yang berbeda. Oleh sebab itulah tipe data long long memiliki jangkauan bilangan yang lebih besar dari int.

Semakin banyak bit juga berarti semakin banyak memori yang diperlukan. Pada komputer, 1 byte dapat memuat 8 bit. Dengan demikian, kita dapat mengetahui berapa ukuran suatu variabel dengan tipe data bilangan bulat. Misalnya pada C++:

• char: 1 byte
• short: 2 byte
• int: 4 byte
• long long: 8 byte

Ada hal penting yang belum dibahas, yaitu cara merepresentasikan bilangan negatif. Pada tipe data yang disebutkan di atas, komputer menggunakan bit paling kiri untuk menyatakan positif atau negatif. Nilai 0 berarti positif, dan 1 berarti negatif. Fakta ini juga mengakibatkan setiap tipe data kehilangan 1 bit untuk merepresentasikan angkanya. Misalnya pada int, sebenarnya hanya ada 31 bit untuk merepresentasikan besaran angkanya.

Mari bahas lebih dalam tentang bilangan negatif. Selain memiliki bit paling kiri bernilai 1, biner dari suatu bilangan -x sebenarnya direpresentasikan dengan biner (x-1), tapi semua bitnya dibalik (0 menjadi 1 dan sebaliknya). Perhatikan representasi biner seluruh bilangan untuk tipe data integer bohongan dengan 4 bit berikut:

 7  0111
 6  0110
 5  0101
 4  0100
 3  0011
 2  0010
 1  0001
 0  0000
-1  1111
-2  1110
-3  1101
-4  1100
-5  1011
-6  1010
-7  1001
-8  1000

Misalnya untuk -6, selain memiliki bit paling kiri bernilai 1, besarannya direpresentasikan dengan biner dari 5 (101) yang bitnya dibalik (010). Sehingga representasi -6 = 1010. Hal menarik lainnya adalah bit dari -1 sampai -8 merupakan pencerminan dari 0 sampai 7, dengan 0 diganti menjadi 1 (dan sebaliknya).

Dengan memahami ini, kita jadi mengerti cara menghitung batas atas dan bawah suatu tipe data integer. Bila terdapat $x$ bit, maka tipe tersebut hanya dapat merepresentasikan $2^x$ nilai, yakni $-2^{x-1}$ sampai dengan $2^{x-1}-1$ . Sifat ini konsisten dengan batas bawah dan atas pada C++:

• int: $[-2^{31}, 2^{31}-1]$, atau $-2147483648 .. 2147483647$
• long long: $[-2^{63}, 2^{63}-1]$

Bahasa pemrograman seperti C++ menyediakan tipe data bilangan bulat yang menggunakan seluruh bit untuk merepresentasikan besaran angka:

• unsigned char
• unsigned short
• unsigned int
• unsigned long long

Karena tidak memiliki bit untuk menyatakan positif atau negatif, mereka hanya dapat meresentasikan bilangan non-negatif. Meskipun demikian, rentangnya lebih besar dari tipe data signed. Tipe data unsigned yang memiliki x bit mampu merepresentasikan bilangan dari 0 sampai  2^x-1.

Sampai tulisan ini dibuat, belum ada tipe data 128 bit. Mungkin suatu saat akan muncul, dan saya harap C++ tidak menamakannya long long long.

---

Operasi Bitwise

Terdapat 6 operasi bitwise yang didukung pada bahasa pemrograman umum.

not

Simbol C++: ~
Operasi ini akan membalik bit 0 menjadi 1, dan sebaliknya. Sebagai contoh, ~5 = -6.
Perhatikan kembali daftar bilangan biner 4 bit yang di bagian atas tulisan ini.

and

Simbol C++: &
Perhatikan bahwa simbolnya bukan &&, sebab && merupakan operator boolean and.
Operator ini melibatkan 2 bilangan, dan menghasilkan suatu bilangan. Bit ke-i pada hasil bernilai 1 apabila bit ke-i pada kedua bilangan operand juga 1. Selain daripada itu, nilainya 0. Sifat ini mirip dengan operator boolean and.

Sebagai contoh, berikut cara menghitung 6 & 3 pada tipe data int 8 bit:

6     : 00000110
3     : 00000011
-----------------
6 & 3 : 00000010

Jadi hasilnya adalah 2.

or

Simbol C++: |
Mirip dengan bitwise and, tapi bit ke-i pada hasil bernilai 1 kalau ada setidaknya satu operand-nya yang memiliki bit ke-i bernilai 1. Jadi syaratnya seperti operator boolean or.

Sebagai contoh, berikut cara menghitung 6 | 3 pada tipe data int 8 bit:

6     : 00000110
3     : 00000011
-----------------
6 | 3 : 00000111

Jadi hasilnya adalah 7.

xor

Simbol C++: ^
Mirip dengan bitwise or, tapi bit ke-i pada hasil bernilai 1 kalau hanya ada satu operand-nya yang memiliki bit ke-i bernilai 1.

Sebagai contoh, berikut cara menghitung 6 ^ 3 pada tipe data int 8 bit:

6     : 00000110
3     : 00000101
-----------------
6 ^ 3 : 00000101

Jadi hasilnya adalah 5.

shl

Simbol C++: <<
Shl adalah singkatan dari shift left. Operasi ini menerima 2 operand, dan berguna untuk menggeser operand pertama ke kiri sebanyak operand kedua. Bit paling kanan akan diisi dengan 0.
Misalkan kita akan melakukan shl pada 6, dengan representasi biner berikut:

6      : 00000110

Berikut adalah hasil shl dengan 1 dan 3:

6 << 1 : 00001100 = 12
6 << 3 : 00110000 = 36

Kalau shl mengakibatkan bit paling kiri bernilai 1, berarti hasilnya adalah bilangan negatif.

Sadari bahwa penggeseran sebanyak 1 bit ke kiri sama dengan perkalian dengan 2.
Jadi penggeseran sebanyak x bit sama dengan perkalian dengan 2^x.

shr

Simbol C++: >>
Shr adalah singkatan dari shift right. Bedanya dengan shl adalah operator ini menggeser bit ke kanan.
Berikut adalah hasil shr dengan 1 dan 3:

6 >> 1 : 00000011 = 3
6 >> 2 : 00000001 = 1

Sadari juga kalau penggeseran sebanyak 1 bit ke kanan sama dengan pembagian dengan 2, dibulatkan ke bawah. Jadi penggeseran sebanyak x bit sama dengan pembagian dengan 2^x, dibulatkan ke bawah.

Kini kita bisa memahami bagaimana algoritma mengubah bilangan basis 10 ke bentuk binernya. Pada setiap langkah, periksa sisa baginya terhadap 2. Kalau bernilai 1, dipastikan bit paling kanannya 1. Lalu buang bit paling kanannya dengan membaginya terhadap 2 dan dibulatkan ke bawah (setara dengan shr). Ulangi sampai bilangannya menjadi 0.

77: 1001101
38:  100110
19:   10011
 9:    1001
 4:     100
 2:      10
 1:       1
 0:       0

Koleksi bit paling kanan yang didapatkan setiap langkah dapat disusun menjadi representasi binernya. Untuk contoh 77, coba telusuri bit paling kanannya dari bawah ke atas, dan Anda akan mendapatkan binernya (yaitu 1001101).

Urutan pengerjaan operator bitwise adalah: not, shl/shr, and, or, xor.
Jika dipadukan dengan operator boolean, urutan pengerjaannya cukup memusingkan.
Contohnya untuk (6 & 2 == 0), operator == akan dikerjakan dulu, sehingga didapatkan (6 & false). Supaya aman, selalu gunakan tanda kurung seperti ((6 & 2) == 0). Ini adalah praktik yang disarankan Bu Inge, menurut ingatan zaman Pelatnas 1 saya.

---

Operasi Lanjutan dan Manipulasi Bit

Memeriksa nilai bit ke-i

Idenya adalah menggunakan and terhadap (1<<i). Jika nilainya lebih dari 0, artinya bit ke-i menyala.
Simak kedua contoh berikut.

5 & (1<<2) = 0

00000101
00000010
--------
00000000

5 & (1<<3) = 4

00000101
00000100
-------- &
00000100

Mengubah nilai bit ke-i

Untuk menyalakan bit ke-i, gunakan or terhadap (1<<i):

5 | (1<<2) = 7

00000101
00000010
-------- |
00000111

Untuk membalik bit ke-i, gunakan xor terhadap (1<<i):

5 ^ (1<<3) = 1

00000101
00000100
-------- ^
00000001

Sementara untuk mematikan bit ke-i, caranya dengan and terhadap biner yang sepenuhnya bernilai 1 kecuali bit ke-i. Bilangan tersebut adalah ~(1<<i).

5 & ~(1<<3) = 1

00000101
11111011
-------- &
00000001

Menghitung banyaknya bit 1

Cara berikut diajarkan Pak Suhendry, idenya membuang bit 1 paling kanan satu demi satu sambil menghitung berapa kali ini dilakukan.

?

1 2 3 4 5 6 7 8

int count1(int x){    int ret = 0;    while (x){       ret++;       x = x & (x-1);    }    return ret; }

Membuang bit terkanan yang menyala

Operasi x = x & (x-1) menjamin x kehilangan 1 bit paling kanan.

12 & (12-1) = 8
00001100
00001011
-------- &
00001000

Mengambil nilai bit terkanan yang menyala

Kalau operasi x = x & (x-1) menghapus bit 1 terkanan, operasi x & -x berguna untuk mengambil bit 1 terkanan.

12 & -12 = 4
00001100
11110100
-------- &
00000100

Operasi ini digunakan pada struktur data BIT.

Enumerasi subset

Diberikan N barang, yang dinomori dari 0 sampai N-1. Cetak semua kombinasi pemilihan barang!

Solusi yang langsung terpikir adalah dengan rekursi. Ada solusi lain dengan mengenumerasi seluruh bilangan dari $0$ sampai $2^N-1$, lalu periksa bit mana saja yang menyala.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

#include <bits/stdc++.h> using namespace std;   void enumerate(int n) {   for (int i = 0; i < (1<<n); i++) {     for (int j = 0; j < n; j++) {       if (i & (1<<j)) {         printf("%d ", j);       }     }     printf("\n");   } }   int main() {   int N;   scanf("%d", &N);   enumerate(N); }

Enumerasi subset dari subset

Cara ini juga diajarkan Pak Suhendry.
Diberikan bilangan biner P, cetak semua kombinasi biner tidak 0 yang ada, apabila hanya bit 1 pada P boleh dinyalakan atau dimatikan. Bit 0 haruslah tetap 0.

Misalnya untuk P=13, keluaran yang diharapkan adalah 7 kemungkinan berikut (bagian kanan menyatakan representasi binernya):

13         1101
12         1100
 9         1001
 8         1000
 5         0101
 4         0100
 1         0001

Solusinya adalah dengan menyimpan P ke dalam suatu variabel, misalnya x. Lalu kurangkan x dengan 1, dan and dengan P. Dengan demikian, bit 0 selalu tetap 0. Lakukan proses ini sampai x bernilai 0. Implementasinya ditunjukkan pada fungsi enumerate berikut:

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

#include <bits/stdc++.h> using namespace std;   string toBinary(int v) {   string s = "";   int x = v;   while (x > 0) {     s = to_string(x%2) + s;     x /= 2;   }   return s; }   void enumerate(int p) {   int x = p;   while (x) {     printf("%2d %12s\n", x, toBinary(x).c_str());     x = (x-1) & p;   } }   int main() {   int P;   scanf("%d", &P);   enumerate(P); }

Cara ini berguna kalau sewaktu-waktu Anda perlu mengenumerasi semua subset dari suatu subset.

---

Contoh Kegunaan

Manipulasi bit biasa digunakan untuk DP bitmask. Bila Anda belum tahu DP bitmask, sebenarnya dia hanyalah DP yang statenya berupa himpunan. Perhatikan contoh soal berikut:

• Ada N ekor bebek, yang dinomori dari 0 sampai dengan N-1.
• Pak Dengklek sedang melelang M barang, yang dinomori dari 0 sampai dengan M-1. 
• Bebek ke-i bersedia membeli barang lelangan ke-j dengan harga H[i][j] Rupiah.
• Jika setiap barang hanya bisa dibeli oleh paling banyak seekor bebek, dan setiap bebek hanya boleh membeli paling banyak 1 barang, maka berapa penghasilan maksimal Pak Dengklek yang mungkin?
• Batasan:
• 1 ≤ N ≤ 10
• 1 ≤ M ≤ 1000
• N ≤ M
• 1 ≤ H[i][j] ≤ 100000

Solusinya adalah mencoba semua kemungkinan untuk setiap barang:

1. Barang ini tidak dibeli bebek manapun
2. Barang ini dibeli salah satu bebek yang belum pernah membeli barang

Supaya pilihan di atas dapat dilaksanakan, kita perlu menyimpan state berupa: indeks barang yang sedang dicoba dan bebek mana saja yang sudah pernah membeli barang.  State kedua ini berupa himpunan, misalnya {0, 3, 4} menyatakan bebek nomor 0, 3, dan 4 sudah pernah membeli barang. 

Berikut formulasinya:

$f(x,S) = \left\{\begin{array}{lr} 0 & ,x=M\\ \displaystyle \max \left( f(x+1, S),  \max_{\substack{0 \leq i \le N \\ i \notin S}} f(x+1, S \cup \{i\}) + H[i][x] \right) &, x < M\\ \end{array}\right.$

Supaya mudah, kita akan merepresentasikan himpunan $S$ dalam bilangan biner. Bit ke-x bilangan ini bernilai 1 kalau bebek nomor x sudah pernah membeli. Jadi untuk {0, 3, 4}, nilainya adalah 11001 (atau 25 dalam basis 10). Sebab kita menggunakan bit untuk menyatakan himpunanlah yang membuat strategi ini dinamakan DP bitmask.

Berikut adalah implementasinya, dengan asumsi array dp awalnya diisi dengan nilai -1.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

int N, M; int H[10][1000]; int dp[1001][1<<10];   int f(int x, int mask) {   if (x == M) {     return 0;   } else if (dp[x][mask] != -1) {     return dp[x][mask];   } else {     // Coba barang x tidak dibeli siapapun     int dp[x][mask] = f(x+1, mask);       for (int i = 0; i < N; i++) {       // Periksa apakah bebek ke-i belum beli barang       if ((mask & (1<<i)) == 0) {         // Coba barang x dibeli bebek ke-i         dp[x][mask] = max(dp[x][mask], f(x+1, mask | (1<<i)) + H[i][x]);       }     }       return dp[x][mask];   } }   // Jawaban ada di f(0, 0)

---

Penutup

Anda dapat berlatih menggunakan operasi bitwise pada soal DP bitmask berikut:

• UVa 10651 - Pebble Solitaire
• UVa 10496 - Collecting Beepers
• UVa 10911 - Forming Quiz Teams

Demikianlah tulisan saya kali ini.
Semoga membantu pemahaman tentang biner, bit, operasinya, dan aplikasinya.