Penjelasan bit manipulation: operator, trik, dan contoh

Masalah yang diselesaikan bit manipulation

Integer adalah deretan bit, dan banyak masalah sebenarnya tentang bit-bit itu: izin file seperti rwx, feature flag, network mask, warna piksel, himpunan opsi yang ringkas, checksum, dan hash. Operator bitwise memungkinkan Anda membaca dan mengubah banyak bit sekaligus dalam satu operasi, yang hemat memori dan sangat cepat.

Soal wawancara juga memakai trik bit karena memberi solusi O(1) ruang yang elegan, misalnya menemukan satu bilangan yang muncul sekali ketika semua bilangan lain muncul dua kali.

Operator

Contoh memakai a = 12 (biner 1100) dan b = 10 (biner 1010).

a, b = 12, 10
print(bin(a), bin(b))         # 0b1100 0b1010
print(a & b, a | b, a ^ b)    # 8 14 6
print(~a, a << 1, a >> 2)     # -13 24 3
print(f"{a ^ b:04b}")         # 0110
print(int("1010", 2))         # 10

Operasi satu bit

Posisi bit dihitung dari 0 di sebelah kanan (least significant bit). Mask 1 << i hanya memiliki bit i yang aktif.

Contoh: menghitung set bit

Metode Brian Kernighan menghapus bit aktif terendah sampai tidak tersisa apa pun, sehingga loop-nya berjalan sekali per bit 1, bukan sekali per posisi bit. Penelusuran untuk x = 44 (biner 101100):

def count_bits(x):
    count = 0
    while x:
        x &= x - 1        # drop the lowest set bit
        count += 1
    return count

print(count_bits(44))     # 3
print((44).bit_count())   # 3
print((44).bit_length())  # 6

int.bit_count() tersedia sejak Python 3.10. int.bit_length() mengembalikan jumlah bit yang dibutuhkan untuk menulis bilangan dalam biner, tanpa tanda.

Trik klasik di Python

from functools import reduce
from operator import xor

# Every number appears twice except one: pairs cancel out with XOR.
print(reduce(xor, [4, 1, 2, 1, 2]))   # 4

# Swap two integers without a temporary variable (for illustration only).
x, y = 5, 9
x ^= y; y ^= x; x ^= y
print(x, y)                            # 9 5

# Bitmask as a set: enumerate all subsets of 3 items.
items = ["a", "b", "c"]
for mask in range(1 << len(items)):
    print(mask, [items[i] for i in range(len(items)) if mask >> i & 1])
# 0 []
# 1 ['a']
# 2 ['b']
# 3 ['a', 'b']
# 4 ['c']
# 5 ['a', 'c']
# 6 ['b', 'c']
# 7 ['a', 'b', 'c']

Mask 0 adalah himpunan kosong, 5 (biner 101) adalah ['a', 'c'], dan 7 adalah ketiga item. Bitmask dynamic programming memakai gagasan yang sama, dengan mask sebagai state, untuk masalah hingga sekitar 20 item, seperti traveling salesman problem pada input kecil.

Dua klasik lainnya: x & 1 bernilai 1 untuk bilangan ganjil, dan XOR dari semua bilangan 0 sampai n dengan semua nilai dalam list menemukan satu bilangan yang hilang.

Kompleksitas waktu dan ruang

Bitmask memakai satu bit per elemen yang mungkin, sehingga himpunan 64 flag muat dalam satu integer 64-bit, dibandingkan dengan 64 variabel boolean terpisah atau entri list.

Kesalahan umum

• Bilangan negatif: integer Python berperilaku seolah memiliki bit tanda yang tak terhingga banyaknya, sehingga ~5 adalah -6 dan bin(-5) adalah -0b101, bukan string two's complement. Untuk melihat pola 32-bit, mask nilainya: -5 & 0xFFFFFFFF.
• Right shift pada bilangan negatif di Python bersifat aritmetik: -8 >> 1 adalah -4, dan -1 >> 10 tetap -1.
• Overflow pada bahasa dengan lebar tetap: di Java atau C, 1 << 31 pada int 32-bit menjadi negatif atau tidak terdefinisi; gunakan tipe 64-bit dan 1L << 40 atau 1ULL << 40.
• Menyamakan operator logika dan bitwise: and dan or (&&, || di bahasa ala C) mengembalikan nilai kebenaran, sedangkan & dan | bekerja bit demi bit.
• Keterbacaan: mengganti x * 2 dengan x << 1 tidak memberi keuntungan kecepatan pada compiler modern maupun di Python, dan membuat kode lebih sulit dibaca.

Penggunaan di dunia nyata

• Izin file Unix: chmod 754 mengatur tiga grup 3-bit (rwx = 4 + 2 + 1).
• Jaringan: subnet mask IPv4, ketika ip & mask menghasilkan alamat jaringan sebuah blok CIDR.
• Flag dan opsi: re.IGNORECASE | re.MULTILINE dan enum.Flag di Python menggabungkan opsi dengan OR.
• Grafis dan warna: nilai RGB 24-bit mengemas merah, hijau, dan biru sebagai (r << 16) | (g << 8) | b.
• Struktur data dan algoritma: Bloom filter, bitset, Fenwick tree (yang memakai i & -i), hashing, dan checksum.
• Soal wawancara: single number, counting bits, power of two, reverse bits, missing number, subset dengan bitmask, sum of two integers without +.