Wat zijn veelgebruikte bit-manipulatietrucs?

Question

Accepted Answer

**Bit manipulation** werkt rechtstreeks op de binaire representatie van gehele getallen met behulp van AND, OR, XOR, NOT en shifts. Het maakt compacte, tak-vrije en zeer snelle operaties mogelijk. ## Core operations ```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 ``` ## Useful tricks ```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) ``` ## Example: find the single number (XOR trick) ```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 ``` ## Complexity Bit ops zijn O(1); de XOR scan hierboven is **O(n) tijd, O(1) ruimte**. ## When to use / pitfalls Gebeurik voor **bitmasks** (subset enumeration, DP over states), flags, snelle wiskunde, en low-level/embedded code. Zorg voor sign bits, taalspecifiek shift gedrag, en leesbaarheid — voeg opmerkingen toe bij niet-voor-de-hand-liggende trucs. ## Waarom het belangrijk is Bit manipulation levert elegante O(1)-space oplossingen op (zoals de XOR single-number trick) die indruk maken bij interviews. Bitmask DP maakt veel combinatorische state-space problemen hanteerbaar. Het is essentieel in systems, graphics, compressie, en performance-critical code waar elke cyclus telt.