Apa saja trik manipulasi bit yang umum?

Question

Accepted Answer

**Manipulasi bit** beroperasi langsung pada representasi biner bilangan bulat menggunakan AND, OR, XOR, NOT, dan shift. Ini memungkinkan operasi yang ringkas, bebas cabang, dan sangat cepat. ## Operasi inti ```python x & 1 # is x odd? (lowest bit) x << 1 # multiply by 2 x >> 1 # integer divide by 2 x & (1 << k) # is bit k set? x | (1 << k) # set bit k x & ~(1 << k) # clear bit k x ^ (1 << k) # toggle bit k ``` ## Trik yang berguna ```python x & (x - 1) # clears the lowest set bit x & (x - 1) == 0 # is x a power of two? (x>0) x & (-x) # isolates the lowest set bit bin(x).count('1') # popcount (number of set bits) ``` ## Contoh: temukan satu angka (trik XOR) ```python def single_number(nums): result = 0 for n in nums: result ^= n # pairs cancel: a ^ a == 0 return result # the lone unpaired value remains single_number([4, 1, 2, 1, 2]) # -> 4 ``` ## Kompleksitas Operasi bit adalah O(1); pemindaian XOR di atas adalah **O(n) waktu, O(1) ruang**. ## Kapan digunakan / perangkap Gunakan untuk **bitmask** (enumerasi subset, DP atas state), flag, matematika cepat, dan kode tingkat rendah/tertanam. Hati-hati dengan bit tanda, perilaku shift khusus bahasa, dan keterbacaan — beri komentar pada trik yang tidak jelas. ## Mengapa ini penting Manipulasi bit menghasilkan solusi O(1)-ruang yang elegan (seperti trik XOR single-number) yang menakjubkan dalam wawancara. Bitmask DP membuat banyak masalah ruang-state kombinatorial dapat dikelola. Ini sangat penting dalam sistem, grafis, kompresi, dan kode yang kritis terhadap kinerja di mana setiap siklus penting.