Apa trik-trik manipulasi bit yang umum?

Question

Accepted Answer

**Bit manipulation** beroperasi langsung pada representasi biner bilangan bulat menggunakan AND, OR, XOR, NOT, dan shift. Ini memungkinkan operasi yang ringkas, tanpa 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: cari 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 **waktu O(n), ruang O(1)**. ## Kapan digunakan / jebakan Gunakan untuk **bitmask** (enumerasi subset, DP atas keadaan), bendera, matematika cepat, dan kode tingkat rendah/tertanam. Hati-hati dengan bit tanda, perilaku shift spesifik bahasa, dan keterbacaan — beri komentar pada trik yang tidak jelas. ## Mengapa itu penting Manipulasi bit menghasilkan solusi yang elegan dengan ruang O(1) (seperti trik XOR angka tunggal) yang menakjubkan dalam wawancara. Bitmask DP membuat banyak masalah ruang keadaan kombinatorial dapat ditangani. Itu sangat penting dalam sistem, grafis, kompresi, dan kode yang kritis untuk kinerja di mana setiap siklus diperhitungkan.