Teknik Manipulasi Bit

Modul Dasar Bahasa memperkenalkan operator bitwise sebagai kelompok operator yang bekerja pada tingkat bit. Topik ini menyusun operator tersebut menjadi teknik yang utuh. Pembahasannya mencakup pembentukan mask, operasi menyalakan, mematikan, membalik, dan memeriksa satu bit, pergeseran bit untuk memecah nilai, serta beberapa trik yang sering muncul pada kode sistem. Studi kasusnya berupa register status, yaitu satu byte yang menyimpan banyak penanda sekaligus, pola yang dipakai luas pada perangkat keras dan format berkas.

Mask dan register status#

Mask adalah pola bit yang dipilih untuk mengisolasi bit tertentu, dan register status adalah byte yang setiap bitnya menyimpan satu penanda. Empat konstanta bit pada program berikut menyatakan penanda tersebut, lalu program menunjukkan empat operasi dasarnya satu per satu.

#include <stdio.h>

#define BIT_SIAP    0x01
#define BIT_AKTIF   0x02
#define BIT_ERROR   0x04
#define BIT_SELESAI 0x08

void laporkan(const char *kejadian, unsigned char status) {
    printf("%-22s", kejadian);
    for (int i = 7; i >= 0; i--) {
        printf("%d", (status >> i) & 1);
    }
    printf("\n");
}

int main(void) {
    unsigned char status = 0;

    status |= BIT_AKTIF;                  /* menyalakan bit */
    laporkan("set BIT_AKTIF", status);

    status |= BIT_ERROR;
    laporkan("set BIT_ERROR", status);

    status &= ~BIT_ERROR;                 /* mematikan bit */
    laporkan("clear BIT_ERROR", status);

    status ^= BIT_AKTIF;                  /* membalik bit */
    laporkan("toggle BIT_AKTIF", status);

    if (status & BIT_AKTIF) {
        printf("BIT_AKTIF menyala\n");
    } else {
        printf("BIT_AKTIF mati\n");
    }
    return 0;
}

set BIT_AKTIF         00000010
set BIT_ERROR         00000110
clear BIT_ERROR       00000010
toggle BIT_AKTIF      00000000
BIT_AKTIF mati

Empat operasi itu mengikuti pola tetap yang layak dihafal. Menyalakan bit memakai OR dengan masknya, yaitu status |= mask, karena OR menghasilkan 1 bila salah satu sisi bernilai 1. Mematikan bit memakai AND dengan kebalikan mask, yaitu status &= ~mask, karena AND dengan 0 memaksa hasilnya menjadi 0. Membalik bit memakai XOR, yaitu status ^= mask, dan memeriksa bit memakai AND biasa, yaitu status & mask yang hasilnya tidak nol bila bit menyala. Pemeriksaan tersebut bekerja bit demi bit sebagaimana diagram berikut.

Diagram di atas memeriksa bit BIT_ERROR pada status bernilai 0x64. Mask 0x04 hanya menyentuh satu bit, sehingga bit-bit lain tidak berpengaruh pada hasil, dan hasil yang tidak nol berarti BIT_ERROR menyala. Konstanta 0x04 dipilih agar pola bitnya terbaca, sedangkan penulisannya boleh berganti menjadi 0x02 atau 0x01 sesuai posisi bit yang diinginkan.

Seluruh contoh pada topik ini menyimpan bit dalam tipe tak bertanda seperti unsigned char. Alasannya, pergeseran kanan pada tipe bertanda yang bernilai negatif tidak menjanjikan hasil tertentu, dan operasi logika bit lebih aman tanpa bit tanda. Fungsi laporkan pada program pertama menampilkan pola bit dengan cara yang sering dipakai saat debugging, yaitu menggeser kanan setiap posisi lalu menyaringnya dengan & 1 sebelum dicetak. Pola yang sama dapat dipakai untuk menampilkan bilangan dalam basis dua tanpa bantuan penentu format printf.

Pergeseran bit#

Pergeseran menggerakkan seluruh bit ke kiri atau ke kanan sebanyak n posisi. Untuk bilangan tak bertanda, menggeser kiri sebanyak n posisi sama dengan mengalikan dengan $2^n$, sedangkan menggeser kanan sama dengan membagi bulat dengan $2^n$. Program berikut memperlihatkan pola tersebut beserta pemakaian praktisnya, yaitu memecah nilai dua byte menjadi bagian tinggi dan rendahnya.

#include <stdio.h>

int main(void) {
    for (int i = 0; i <= 4; i++) {
        printf("1 << %d = %2u\n", i, 1u << i);
    }

    unsigned int paket = 0xABCD;
    printf("Byte tinggi: 0x%02X\n", (paket >> 8) & 0xFF);
    printf("Byte rendah: 0x%02X\n", paket & 0xFF);
    return 0;
}

1 << 0 =  1
1 << 1 =  2
1 << 2 =  4
1 << 3 =  8
1 << 4 = 16
Byte tinggi: 0xAB
Byte rendah: 0xCD

Pemecahan paket memakai gabungan pergeseran dan mask, yaitu pola yang sama dengan pemeriksaan bit pada bagian sebelumnya. Geser kanan sebanyak 8 posisi memindahkan byte tinggi ke posisi byte rendah, lalu mask 0xFF membuang sisanya. Pergeseran juga menjadi alat menyusun mask dari posisinya, karena 1u << 3 menghasilkan 0x08. Dengan bentuk itu, konstanta BIT_SELESAI 0x08 pada program pertama dapat ditulis (1u << 3), sehingga posisi bitnya terbaca langsung.

Pergeseran pada tipe bertanda memerlukan kehati-hatian tambahan, karena bit paling kirinya menyimpan tanda. Menggeser kanan nilai bertanda yang positif memang setara pembagian. Hasil geser kanan untuk nilai negatif bergantung pada kompiler, sedangkan menggeser kiri nilai negatif berupa perilaku tak terdefinisi. Karena itu, seluruh pergeseran pada topik ini memakai operand tak bertanda, dan kebiasaan yang sama layak diikuti ketika menulis kode baru.

Trik umum pada bit#

Beberapa pola pendek muncul berulang pada kode sistem dan layak dikenali sejak awal. Program berikut menguji paritas dengan & 1, menggandakan dan membagi dengan pergeseran, menguji pangkat dua dengan x & (x - 1), dan menghitung banyaknya bit 1 dengan perulangan Brian Kernighan.

#include <stdio.h>

int banyak_bit_satu(unsigned int n) {
    int hitung = 0;
    while (n != 0) {
        n &= n - 1;             /* menghapus bit 1 yang paling rendah */
        hitung++;
    }
    return hitung;
}

int main(void) {
    printf("12 & 1  = %d, sehingga 12 genap\n", 12 & 1);
    printf("9 & 1   = %d, sehingga 9 ganjil\n", 9 & 1);
    printf("12 << 1 = %d, 12 >> 1 = %d\n", 12 << 1, 12 >> 1);
    printf("64 & 63 = %d, sehingga 64 pangkat dua\n", 64 & 63);
    printf("48 & 47 = %d, sehingga 48 bukan pangkat dua\n", 48 & 47);
    printf("Banyak bit 1 pada 255: %d\n", banyak_bit_satu(255));
    printf("Banyak bit 1 pada 100: %d\n", banyak_bit_satu(100));
    return 0;
}

12 & 1  = 0, sehingga 12 genap
9 & 1   = 1, sehingga 9 ganjil
12 << 1 = 24, 12 >> 1 = 6
64 & 63 = 0, sehingga 64 pangkat dua
48 & 47 = 32, sehingga 48 bukan pangkat dua
Banyak bit 1 pada 255: 8
Banyak bit 1 pada 100: 3

Uji pangkat dua bekerja karena bilangan pangkat dua memiliki tepat satu bit yang bernilai 1. Pengurangan satu membalik bit itu dan menyalakan seluruh bit di bawahnya, sehingga operasi & keduanya menghasilkan 0. Perulangan Brian Kernighan memakai sifat yang sama, yaitu n & (n - 1) menghapus bit 1 yang paling rendah. Karena itu, perulangannya hanya berputar sebanyak bit 1 yang ada, bukan sebanyak lebar tipenya. Kedua pola ini contoh bagaimana satu baris operasi bit menggantikan perulangan atau percabangan yang lebih panjang.

Teknik pada bagian sebelumnya juga langsung terpakai saat dua nilai kecil perlu dipadatkan ke satu byte, misalnya dua angka 0 sampai 15 yang disimpan sebagai dua nibble, yaitu kelompok empat bit.

// tidak-dijalankan
unsigned int paket = (tinggi << 4) | rendah;    /* tinggi, rendah: 0..15 */
unsigned int tinggi_kembali = paket >> 4;
unsigned int rendah_kembali = paket & 0x0F;

Pemadatan memakai pergeseran kiri untuk mengosongkan empat bit atas, lalu OR mengisi bagian rendahnya, sedangkan pembongkarannya mengulangi pola pemecahan byte pada bagian pergeseran. Pola padat-bongkar seperti ini mendasari format berkas biner, protokol, dan register perangkat keras yang menampung beberapa medan kecil ke dalam satu word.

Kesalahan umum#

• Menggeser sebanyak lebar tipe atau lebih. Pada int 32-bit, ungkapan x << 32 merupakan perilaku tak terdefinisi, begitu pula jumlah geser yang negatif. Jaga jumlah geser tetap pada rentang 0 sampai lebar tipe dikurangi satu.
• Memakai tipe bertanda untuk operasi bit. Pergeseran kanan pada nilai negatif bergantung pada kompiler, sehingga hasilnya tidak dapat diandalkan antarplatform. Gunakan tipe tak bertanda seperti unsigned int atau unsigned char untuk data yang diperlakukan sebagai kumpulan bit.
• Lalai pada prioritas operator. Ungkapan x & 1 == 0 dihitung sebagai x & (1 == 0) karena == lebih tinggi dari &, sehingga hasilnya selalu x & 0 yang bernilai 0. Apit setiap perbandingan dengan tanda kurung, misalnya (x & 1) == 0.
• Mengabaikan promosi tipe saat menggeser. Nilai bertipe unsigned char dipromosikan menjadi int terlebih dahulu sebelum digeser, sehingga hasil status << 8 bertipe int dan bisa mengejutkan ketika langsung disimpan kembali ke variabel asalnya. Tulis konversi tujuannya secara eksplisit agar maksudnya jelas.

Ringkasan#

• Mask memilih bit tertentu, dan empat operasinya adalah |= untuk menyalakan, &= ~ untuk mematikan, ^= untuk membalik, serta & untuk memeriksa.
• Pergeseran kiri mengalikan dengan $2^n$ dan pergeseran kanan membagi bulat untuk tipe tak bertanda, sekaligus menjadi alat menyusun mask dan memecah nilai.
• Uji pangkat dua dan perhitungan banyak bit 1 memanfaatkan sifat n & (n - 1) yang menghapus bit 1 paling rendah.
• Tipe tak bertanda dan tanda kurung pada perbandingan menjaga kode bit tetap portabel dan terbaca.

Referensi#

• Arithmetic operators — cppreference.com — Perilaku operator bitwise dan pergeseran, termasuk kasus yang tak terdefinisi.
• C operator precedence — cppreference.com — Urutan prioritas operator C yang menjadi penyebab jebakan x & 1 == 0.