Operasi Bit

Seperti kita tahu, operasi bit sangat penting dalam pengembangan embedded system. Banyak sekali kasus yang melibatkan pengetahuan dasar ini. Pengetahuan ini juga sangat berguna dalam operasi matematika yang kadang tidak memungkinkan dilakukan dengan cara konvensional pada lingkungan embedded system yang terbatas. Misal, operasi perkalian, atau logaritma, perpangkatan, dan beberapa kasus lain.

Set/Clear Bit

Mari kita mulai dari operasi paling sederhana, yaitu set/clear bit. Operasi ini adalah operasi untuk mengaktifkan/menonaktifkan satu bit dari sebuah nilai. Ambil contoh satu tipe data char (8 bit) dengan nilai 5.

char val = 5;

representasi biner 5 = 00000101
lalu kita akan mengeset bit ke 4

val |= (1 << 4);

hasil = 00010101; 21
untuk menge-clear bit ke 2 dari 21, maka hasilnya: 00010001

val &= ~(1 << 2);

Operator >> dan << disebut precedence operator di dalam bahasa C. Fungsi dari operator tersebut adalah untuk menggeser bit. Ekuivalen dengan perintah RR (Rotate Right) dan RL (Rotate Left) pada bahasa assembly Intel 8051.

Menghitung Bit Set

Ada kalanya kita akan butuh untuk mengetahui berapa bit set dari sebuah nilai. Berikut adalah cara yang ditemukan oleh Bryan Kernighan (The C Programming Language 2nd Ed. (by Brian W. Kernighan and Dennis M. Ritchie) latihan 2-9):

for (x = 0; i; x++) {
    i &= i - 1;
}

Iterasi akan dilakukan sebanyak jumlah bit `1′ dari sebuah nilai. Mari perhatikan kode berikut:

unsigned int bits_set(unsigned int i)
{
    unsigned int x = 0;
    for (x = 0; i; x++) {
        i &= i - 1;
    }
    return x;
}

void main(void)
{
    unsigned int v = 0;
    unsigned int c;

    for (v = 0; v < 0xFFFF; v++) {
        printf("nilai: %d bitset: %dn", v, bits_set(v));
    }
}

Kode di atas akan menghitung jumlah bit set dari sebuah nilai, mulai dari 0 hingga 0xFFFF.

nilai: 0 bitset: 0 00000000 -> 0 bit set
nilai: 1 bitset: 1 00000001 -> 1 bit set
nilai: 2 bitset: 1 00000010 -> 1 bit set
nilai: 3 bitset: 2 00000011 -> 2 bit set
nilai: 4 bitset: 1 00000100 -> 1 bit set
nilai: 5 bitset: 2 00000101 -> 2 bit set
nilai: 6 bitset: 2 00000110 -> 2 bit set
nilai: 65532 bitset: 14 FFFC -> 14 bit set
nilai: 65533 bitset: 15 FFFD -> 15 bit set
nilai: 65534 bitset: 15 FFFE -> 15 bit set

Power Of Two

Dalam sistem bilangan, kita mengenal istilah power of two. Deret bilangan power of two tampak seperti berikut:

1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, ...

secara matematis:

20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 210, 211, ...

Notasi matematis dari 23 dalam bahasa program adalah (1 << 3), yang dijabarkan sebagai berikut:

(1 << 3) = 1 * 23

(x << y) = x * 2y

sebaliknya:

(x >> y) = x / 2y

Misal diberikan sebuah nilai dari bilangan tersebut, kemudian kita ingin memperoleh nilai pangkatnya. Kita kenal metode untuk memperoleh pangkat dengan nama logaritma (log). Pada kasus di atas kita gunakan logaritma basis 2. Secara umum, notasi logaritma adalah sebagai berikut:

alog ab = b

2log 25 = 5

Untuk memperoleh nilai log basis dua dari sebuah nilai, dapat dilakukan sebagai berikut:

unsigned int n; // nilai power of two
unsigned int c; // 2log 2c
while (n >>=1) {
    c++;
}

Untuk n = 32, c = 5

Kasus lain yang lazim ditanyakan adalah, apakah sebuah bilangan/nilai adalah power of two? Bilangan power of two, memiliki susunan bit yang unik. Hanya satu bit set (1) sedangkan sisanya adalah bit clear (0).

 1: 00000001
 2: 00000010
 4: 00000100
 8: 00001000
16: 00010000
32: 00100000
64: 01000000
dst

Untuk menjawab pertanyaan ini, bilangan tersebut dapat diuji dengan metode sebagai berikut:

unsigned int n;
unsigned int r; /* hasil, apakah power of two atau bukan*/
r = n & (n - 1); /* 0: power of two, lain bukan */

Akan tetapi dengan metode di atas, 0 juga akan dianggap sebagai power of two. Maka kita ganti sebagai berikut:

r = n && !(n & (n - 1)); /* 0: bukan power of two, selain nol: ya */

Masih banyak hacking tentang manipulasi bit dalam dunia komputasi. Tulisan di atas tidak sepenuhnya sempurna, malah cenderung naif dalam penerapannya dan jauh dari optimisasi kode.

Pos ini dipublikasikan di Embedded dan tag , , , , , . Tandai permalink.

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s