Apakah trik manipulasi bit yang umum?

Question

Accepted Answer

**Bit manipulation** beroperasi langsung pada representasi binari 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 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 bilangan tunggal (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 **waktu O(n), ruang O(1)**. ## Kapan digunakan / perangkap Gunakan untuk **bitmask** (enumerasi subset, DP atas keadaan), flag, matematika cepat, dan kode tingkat rendah/tertanam. Berhati-hati dengan bit tanda, perilaku shift spesifik bahasa, dan keterbacaan — berkomentar pada trik yang tidak jelas. ## Mengapa ini penting Manipulasi bit menghasilkan solusi O(1)-ruang yang elegan (seperti trik XOR bilangan tunggal) yang menakjubkan dalam wawancara. Bitmask DP membuat banyak masalah ruang keadaan kombinatorial dapat ditangani. Ia penting dalam sistem, grafis, kompresi, dan kode yang kritis terhadap kinerja di mana setiap siklus diperhitungkan.