Bit manipulation adalah teknik memanipulasi nilai integer pada level bit individual. Operasi ini sangat penting di pemrograman low-level: device driver yang mengatur register, protokol jaringan yang mempacking data, enkripsi, kompresi, dan struktur data probabilistik seperti Bloom filter. C menyediakan enam bitwise operator: & (AND), | (OR), ^ (XOR), ~ (NOT), << (left shift), >> (right shift). Pada chapter ini kita akan membangun macro dasar untuk set, clear, toggle, dan check bit, lalu mempelajari operasi lanjutan seperti popcount dan posisi bit tertinggi.

Operasi Dasar: Set, Clear, Toggle, Check #

Empat operasi dasar bit manipulation paling sering muncul di kode low-level. Pola umumnya melibatkan mask 1u << i yang menandai bit ke-i. Operator yang dipakai bergantung pada aksi yang diinginkan.

c 
#include <stdio.h>

/* Set bit ke-i menjadi 1 */
#define SET_BIT(x, i)    ((x) |  (1u << (i)))
/* Clear bit ke-i menjadi 0 */
#define CLR_BIT(x, i)    ((x) & ~(1u << (i)))
/* Toggle bit ke-i */
#define TOGGLE_BIT(x, i) ((x) ^  (1u << (i)))
/* Cek bit ke-i (1 atau 0) */
#define GET_BIT(x, i)    (((x) >> (i)) & 1u)

int main(void) {
    unsigned int x = 0;

    x = SET_BIT(x, 3);
    x = SET_BIT(x, 5);
    printf("set bit 3 dan 5: 0x%X (%u)\n", x, x);

    x = TOGGLE_BIT(x, 4);
    printf("toggle bit 4: 0x%X (%u)\n", x, x);

    x = CLR_BIT(x, 3);
    printf("clear bit 3: 0x%X (%u)\n", x, x);

    printf("bit 5 = %u\n", GET_BIT(x, 5));
    printf("bit 3 = %u\n", GET_BIT(x, 3));

    return 0;
}

Output yang Dihasilkan:

text 
set bit 3 dan 5: 0x28 (40)
toggle bit 4: 0x38 (56)
clear bit 3: 0x30 (48)
bit 5 = 1
bit 3 = 0

Mari kita telaah baris-baris kode di atas:

  1. Baris 5 (SET_BIT(x, i) -> (x) | (1u << i)): left-shift 1u sebanyak i posisi menghasilkan mask dengan hanya bit ke-i yang bernilai 1. OR dengan x menyet bit ke-i menjadi 1 tanpa mengubah bit lain.
  2. Baris 7 (CLR_BIT(x, i) -> (x) & ~(1u << i)): mask 1u << i dinegasikan dengan ~ sehingga bit ke-i menjadi 0 dan sisanya 1. AND dengan x menghapus bit ke-i.
  3. Baris 9 (TOGGLE_BIT(x, i) -> (x) ^ (1u << i)): XOR dengan mask membalik bit ke-i (1 jadi 0, 0 jadi 1). Bit lain tidak terpengaruh.
  4. Baris 11 (GET_BIT(x, i) -> ((x) >> i) & 1u): geser x ke kanan sebanyak i posisi sehingga bit ke-i berada di posisi 0, lalu AND dengan 1u untuk mengisolasi bit tersebut.
  5. Baris 16-18: set bit 3 dan 5 menghasilkan 0b101000 = 0x28 = 40. Toggle bit 4 mengubah 0b101000 menjadi 0b111000 = 0x38 = 56. Clear bit 3 mengubahnya kembali menjadi 0b110000 = 0x30 = 48.

Operasi Lanjutan: Popcount dan Bit Position #

Banyak algoritma memerlukan informasi tentang jumlah bit 1 (popcount) atau posisi bit tertentu. C11 menyediakan fungsi __builtin_popcount di GCC/Clang untuk popcount hardware, tetapi implementasi portable juga mudah ditulis.

c 
#include <stdio.h>

/* Hitung jumlah bit 1 (popcount) */
static int popcount(unsigned int x) {
    int count = 0;
    while (x) {
        count += x & 1u;
        x >>= 1;
    }
    return count;
}

/* Cari posisi bit paling rendah yang 1 (ffs-like) */
static int lowest_set_bit(unsigned int x) {
    if (x == 0) return -1;
    int pos = 0;
    while ((x & 1u) == 0) {
        x >>= 1;
        pos++;
    }
    return pos;
}

/* Cari posisi bit paling tinggi yang 1 (fls-like) */
static int highest_set_bit(unsigned int x) {
    if (x == 0) return -1;
    int pos = 0;
    while (x > 1) {
        x >>= 1;
        pos++;
    }
    return pos;
}

int main(void) {
    unsigned int vals[] = {0, 1, 7, 0xFF, 0x1010, 0xDEADBEEF};
    int n = sizeof(vals) / sizeof(vals[0]);

    for (int i = 0; i < n; i++) {
        unsigned int v = vals[i];
        printf("0x%08X: popcount=%d lowest=%d highest=%d\n",
               v, popcount(v), lowest_set_bit(v), highest_set_bit(v));
    }

    /* Bitwise swap (xor swap) */
    int a = 5, b = 9;
    a ^= b;
    b ^= a;
    a ^= b;
    printf("setelah xor swap: a=%d b=%d\n", a, b);

    return 0;
}

Output yang Dihasilkan:

text 
0x00000000: popcount=0 lowest=-1 highest=-1
0x00000001: popcount=1 lowest=0 highest=0
0x00000007: popcount=3 lowest=0 highest=2
0x000000FF: popcount=8 lowest=0 highest=7
0x00001010: popcount=2 lowest=4 highest=12
0xDEADBEEF: popcount=24 lowest=0 highest=31
setelah xor swap: a=9 b=5

Fungsi popcount menghitung jumlah bit 1 dengan iterasi sederhana—setiap iterasi memeriksa bit paling kanan lalu menggeser x. Implementasi ini memiliki kompleksitas O(n) di mana n adalah lebar tipe (32 untuk unsigned int). Algoritma Brian Kernighan yang lebih cepat: while (x) { count++; x &= x - 1; }—setiap iterasi menghapus satu bit 1, sehingga loop berjalan sebanyak popcount itself.

lowest_set_bit dan highest_set_bit mengembalikan indeks bit. Bila input 0, kedua fungsi mengembalikan -1 sebagai sentinel “tidak ada bit set”. Fungsi __builtin_ffs (GCC) dan __builtin_clz (count leading zeros) menyediakan operasi serupa dengan dukungan hardware instruction bsf/bsr di x86.

XOR swap di akhir contoh menukar nilai a dan b tanpa variabel sementara. Trik ini berguna di assembly programming tetapi jarang dipakai di C modern—compiler mengoptimasi swap biasa sama baiknya, dan XOR swap bisa gagal bila a dan b adalah alias dari variabel yang sama.

Aplikasi Bit Manipulation #

Bit manipulation banyak dipakai di:

  • Flag bitmask: kumpulan boolean dipadatkan menjadi satu integer. flags |= FLAG_READ | FLAG_WRITE mengaktifkan dua flag.
  • Register perangkat keras: bit individual mengatur konfigurasi. reg |= (1 << 7) menyalakan bit 7.
  • Hashing dan Bloom filter: popcount digunakan untuk menghitung jumlah bit yang tersset.
  • Kompresi: bit-packing memadatkan data (misal 4-bit nibble) ke dalam byte.