Operasi bitwise adalah senjata rahasia pemrogram kompetitif. Sebuah operasi yang biasanya butuh O(log n) loop (mis. hitung bit set, cek power of two, cari MSB/LSB) dapat dilakukan dalam O(1) via instruksi CPU khusus. GCC menyediakan builtin functions (__builtin_popcount, __builtin_clz, __builtin_ctz) yang langsung compile ke instruksi hardware. Selain itu, trik-trik klasik seperti XOR swap, LSB isolasi (x & -x), dan power-of-2 check (x & (x-1)) adalah pengetahuan dasar yang penting untuk banyak algoritma (Fenwick tree, DSU bitmask, hash rolling). Pada Chapter ini kita membedah trik-trik bitwise yang paling berguna beserta implementasinya.

Aturan: Bit Manipulation Primitives #

Setiap operasi bitwise adalah O(1) pada CPU modern. Yang penting adalah identifikasi operasi mana yang efisien (builtin) vs yang butuh loop. Daftar operasi:

OperasiBuiltin / TrikKompleksitas
Count bit 1 (popcount)__builtin_popcount(x)O(1)
Count leading zeros__builtin_clz(x)O(1)
Count trailing zeros__builtin_ctz(x)O(1)
Lowest set bit (LSB isolasi)x & (-x)O(1)
Highest set bit (MSB)1 << (31 - __builtin_clz(x))O(1)
Hapus LSBx & (x - 1)O(1)
Cek power of 2x > 0 && (x & (x-1)) == 0O(1)
Toggle bit ix ^ (1 << i)O(1)
Set bit ix | (1 << i)O(1)
Clear bit ix & ~(1 << i)O(1)
Test bit i(x >> i) & 1O(1)
XOR swapa^=b; b^=a; a^=b;O(1)

Mekanisme: Builtin Functions dan Trik Klasik #

Popcount #

__builtin_popcount(x): jumlah bit 1 di x. CPU modern punya instruksi POPCNT langsung — jauh lebih cepat dari loop manual. C++20 menyediakan std::popcount di header <bit>.

Count Leading/Trailing Zeros #

  • __builtin_clz(x): jumlah bit 0 sebelum MSB (most significant bit). Untuk x = 1 (binary 0...01), clz = 31 (untuk 32-bit). Untuk x = 1024 = 2^10, clz = 21.
  • __builtin_ctz(x): jumlah bit 0 setelah LSB (least significant bit). Untuk x = 8 = 0b1000, ctz = 3.

Aplikasi: bit_width(x) = 32 - clz(x) memberi jumlah bit minimum untuk representasi x. log2_floor(x) = 31 - clz(x).

LSB Isolasi: x & (-x) #

Trik sakti untuk Fenwick tree. Representasi biner -x = ~x + 1 (two’s complement). x & (-x) mengisolasi LSB. Contoh: 12 = 0b1100, -12 = 0b...10100, 12 & -12 = 0b0100 = 4.

Hapus LSB: x & (x - 1) #

x - 1 memflip LSB dari x dan semua bit trailing 0 menjadi 1. x & (x-1) menghapus LSB. Aplikasi: cek power of 2 (x & (x-1) == 0 untuk x > 0), iterasi semua bit set dalam integer.

XOR Swap #

cpp 
a ^= b;
b ^= a;
a ^= b;

Tukar dua variabel tanpa temporary. Setelah baris pertama a = a ^ b. Baris kedua: b = b ^ (a ^ b) = a. Baris ketiga: a = (a ^ b) ^ a = b. Warning: jangan dipakai bila a dan b adalah alias ke variabel yang sama (a ^= a menghasilkan 0).

Implementasi: Trik Bitwise #

cpp 
#include <iostream>
#include <bitset>
#include <cstdint>

int main() {
    // popcount: jumlah bit 1
    std::cout << "Popcount (jumlah bit 1):\n";
    uint32_t nums[] = {0, 1, 7, 255, 0xFFFFFFFF, 0b10110101};
    for (uint32_t v : nums) {
        std::cout << "  popcount(" << v << ") = " << __builtin_popcount(v) << '\n';
    }

    // leading zeros: jumlah bit 0 di depan (sebelum MSB)
    std::cout << "\nCount leading zeros (clz):\n";
    for (uint32_t v : {1u, 2u, 4u, 8u, 16u, 1024u, 65536u}) {
        std::cout << "  clz(" << v << ") = " << __builtin_clz(v)
                  << " (32 - clz = " << 32 - __builtin_clz(v) << " bit width)\n";
    }

    // trailing zeros: jumlah bit 0 di belakang (sebelum LSB)
    std::cout << "\nCount trailing zeros (ctz):\n";
    for (uint32_t v : {1u, 2u, 4u, 8u, 16u, 0b10100u, 0b11000u}) {
        std::cout << "  ctz(" << v << ") = " << __builtin_ctz(v) << '\n';
    }

    // Lowest set bit (LSB isolasi)
    std::cout << "\nLowest set bit (a & -a):\n";
    for (uint32_t v : {12u, 24u, 7u, 40u, 0b101000u}) {
        uint32_t lsb = v & (-v);
        std::cout << "  LSB(" << v << ") = " << lsb << '\n';
    }

    // Highest set bit (1 << (31 - clz))
    std::cout << "\nHighest set bit:\n";
    for (uint32_t v : {12u, 24u, 7u, 40u, 0b101000u}) {
        uint32_t msb = 1u << (31 - __builtin_clz(v));
        std::cout << "  MSB(" << v << ") = " << msb << '\n';
    }

    // XOR swap (tanpa variabel temp)
    std::cout << "\nXOR swap:\n";
    int a = 42, b = 99;
    std::cout << "  Sebelum: a=" << a << ", b=" << b << '\n';
    a ^= b;
    b ^= a;
    a ^= b;
    std::cout << "  Sesudah: a=" << a << ", b=" << b << '\n';

    // Toggle bit
    std::cout << "\nToggle bit (XOR dengan 1<<i):\n";
    uint32_t x = 0b1010;
    std::cout << "  x = " << std::bitset<8>(x) << '\n';
    x ^= (1 << 1);
    std::cout << "  setelah toggle bit 1: " << std::bitset<8>(x) << '\n';
    x ^= (1 << 3);
    std::cout << "  setelah toggle bit 3: " << std::bitset<8>(x) << '\n';

    // Cek power of 2
    std::cout << "\nPower of 2 check (x > 0 && (x & (x-1)) == 0):\n";
    for (uint32_t v : {1u, 2u, 4u, 7u, 16u, 31u, 32u, 100u}) {
        bool is_pow2 = v > 0 && (v & (v - 1)) == 0;
        std::cout << "  " << v << (is_pow2 ? " is" : " is NOT") << " power of 2\n";
    }

    // Bitset untuk visualisasi
    std::cout << "\nBitset visualisasi:\n";
    std::cout << "  255 = " << std::bitset<8>(255) << '\n';
    std::cout << "  170 = " << std::bitset<8>(170) << " (checkerboard)\n";
    std::cout << "  85  = " << std::bitset<8>(85) << " (checkerboard inverted)\n";
    return 0;
}

Output yang Dihasilkan:

text 
Popcount (jumlah bit 1):
  popcount(0) = 0
  popcount(1) = 1
  popcount(7) = 3
  popcount(255) = 8
  popcount(4294967295) = 32
  popcount(181) = 5

Count leading zeros (clz):
  clz(1) = 31 (32 - clz = 1 bit width)
  clz(2) = 30 (32 - clz = 2 bit width)
  clz(4) = 29 (32 - clz = 3 bit width)
  clz(8) = 28 (32 - clz = 4 bit width)
  clz(16) = 27 (32 - clz = 5 bit width)
  clz(1024) = 21 (32 - clz = 11 bit width)
  clz(65536) = 15 (32 - clz = 17 bit width)

Count trailing zeros (ctz):
  ctz(1) = 0
  ctz(2) = 1
  ctz(4) = 2
  ctz(8) = 3
  ctz(16) = 4
  ctz(20) = 2
  ctz(24) = 3

Lowest set bit (a & -a):
  LSB(12) = 4
  LSB(24) = 8
  LSB(7) = 1
  LSB(40) = 8
  LSB(40) = 8

Highest set bit:
  MSB(12) = 8
  MSB(24) = 16
  MSB(7) = 4
  MSB(40) = 32
  MSB(40) = 32

XOR swap:
  Sebelum: a=42, b=99
  Sesudah: a=99, b=42

Toggle bit (XOR dengan 1<<i):
  x = 00001010
  setelah toggle bit 1: 00001000
  setelah toggle bit 3: 00000000

Power of 2 check (x > 0 && (x & (x-1)) == 0):
  1 is power of 2
  2 is power of 2
  4 is power of 2
  7 is NOT power of 2
  16 is power of 2
  31 is NOT power of 2
  32 is power of 2
  100 is NOT power of 2

Bitset visualisasi:
  255 = 11111111
  170 = 10101010 (checkerboard)
  85  = 01010101 (checkerboard inverted)

Bedah Kode Baris-per-Baris #

  1. __builtin_popcount(v): count bit 1. Implementasi GCC langsung compile ke instruksi POPCNT pada CPU modern. Jauh lebih cepat dari loop manual while (x) { count += x & 1; x >>= 1; }.
  2. __builtin_clz(v): count leading zeros. Untuk 32-bit unsigned, hasil di [0, 31]. Undefined behavior bila v == 0 — pastikan v > 0 sebelum panggil.
  3. __builtin_ctz(v): count trailing zeros. Untuk v = 8 = 0b1000, ctz = 3 (tiga trailing zeros). Juga UB untuk v = 0.
  4. 32 - __builtin_clz(v): hitung bit width minimum untuk merepresentasikan v. Mis. v = 1024 = 2^10 butuh 11 bit. C++20: std::bit_width(v).
  5. v & (-v): isolasi LSB. Contoh 12 = 0b1100 → -12 (two’s complement) = 0b...10100 → 12 & -12 = 0b0100 = 4. Inti dari Fenwick tree: idx += idx & (-idx) untuk navigasi ke parent.
  6. 1u << (31 - __builtin_clz(v)): isolasi MSB. Mis. v = 12 = 0b1100, clz = 28, 31 - 28 = 3, 1 << 3 = 8 = 0b1000. Ini adalah highest power of 2 yang ≤ v.
  7. v & (v - 1): clear LSB. Mis. 12 & 11 = 0b1100 & 0b1011 = 0b1000 = 8. Trik untuk iterasi bit set: while (v) { process LSB; v &= v - 1; } — loop hanya sebanyak popcount(v), bukan 32.
  8. XOR swap: tukar a dan b tanpa temporary. Implementasinya: a ^= b → a = a ^ b. b ^= a → b = b ^ (a ^ b) = a. a ^= b → a = (a ^ b) ^ a = b. Warning: jangan pakai bila a dan b adalah reference ke variabel yang sama.
  9. x ^= (1 << i): toggle bit i. Bila bit set, jadi 0. Bila clear, jadi 1. Berguna untuk DP bitmask (toggle elemen i dalam set).
  10. x > 0 && (x & (x-1)) == 0: cek power of 2. x & (x-1) menghapus LSB. Bila hasil = 0, artinya hanya ada 1 bit set → power of 2. Kondisi x > 0 karena 0 juga menghasilkan 0 di x & (x-1) tetapi bukan power of 2.
  11. Verifikasi:
    • popcount(255) = 8 (semua 8 bit set). ✓
    • clz(1024) = 21 (1024 = 2^10, butuh 11 bit, 32 - 11 = 21 leading zeros). ✓
    • ctz(8) = 3 (8 = 0b1000, tiga trailing zeros). ✓
    • LSB(12) = 4 (0b1100, LSB = bit value 4). ✓
    • MSB(12) = 8 (highest power of 2 ≤ 12). ✓
    • XOR swap: 42 ↔ 99 → a=99, b=42. ✓
    • Toggle bit: 0b1010 → toggle bit 1 → 0b1000 → toggle bit 3 → 0b0000. ✓
    • Power of 2: 1, 2, 4, 16, 32 adalah power of 2. 7, 31, 100 bukan. ✓

Aplikasi #

Fenwick Tree #

cpp 
// add(idx, val): iterasi dengan naik ke parent
for (++idx; idx <= n; idx += idx & (-idx)) bit[idx] += val;
// prefix(idx): iterasi dengan turun
for (++idx; idx > 0; idx -= idx & (-idx)) sum += bit[idx];

idx & (-idx) mengisolasi LSB untuk menentukan step ke parent/child.

Iterasi Bit Set #

cpp 
// Iterasi semua bit set di v, hanya loop sebanyak popcount(v) kali
while (v) {
    int bit = __builtin_ctz(v);
    // process bit
    v &= v - 1;  // clear LSB
}

Lebih cepat dari for (int i = 0; i < 32; ++i) if (v & (1 << i)) yang selalu loop 32 kali.

Round Up ke Power of 2 #

cpp 
uint32_t round_up_pow2(uint32_t v) {
    if (v <= 1) return 1;
    return 1u << (32 - __builtin_clz(v - 1));
}

Berguna untuk segment tree (ukuran 2^k), hash table (size power of 2), dsb.

Hash Combine #

cpp 
template<typename T>
void hash_combine(size_t& seed, const T& v) {
    seed ^= std::hash<T>(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}

Trik untuk combine hash beberapa value (mis. untuk unordered_map<pair<int,int>, ...>). Konstanta 0x9e3779b9 adalah golden ratio fractional part, memberi distribusi hash yang baik.

Ringkasan #

  • Bitwise operations adalah O(1) di CPU modern, dengan instruksi hardware khusus.
  • __builtin_popcount(x): count bit 1. UB untuk x=0 di beberapa compiler.
  • __builtin_clz(x): count leading zeros. UB untuk x=0.
  • __builtin_ctz(x): count trailing zeros. UB untuk x=0.
  • x & (-x): isolasi LSB. Inti dari Fenwick tree.
  • x & (x-1): hapus LSB. Trik cek power of 2.
  • XOR swap: tukar tanpa temp (warning: jangan pada alias ke variabel yang sama).
  • C++20 menyediakan std::popcount, std::countl_zero, std::countr_zero di <bit>.
  • Aplikasi: Fenwick tree, iterasi bit set, round-up power 2, hash combine.