Jaké jsou běžné triky bitové manipulace?

Question

Accepted Answer

**Bitová manipulace** pracuje přímo s binární reprezentací celých čísel pomocí operací AND, OR, XOR, NOT a posunů. Umožňuje kompaktní, větvení-free a velmi rychlé operace. ## Základní operace ```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 ``` ## Užitečné triky ```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) ``` ## Příklad: najít jedinečné číslo (XOR trik) ```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 ``` ## Složitost Bitové operace jsou O(1); výše uvedené XOR prohledávání je **O(n) čas, O(1) prostor**. ## Kdy použít / úskalí Verejné pro **bitmasks** (výčet podmnožin, DP nad stavy), příznaky, rychlou matematiku a nízkoúrovňový/vložený kód. Pozor na znakové bity, chování posunů specifické pro jazyk a čitelnost — komentujte neobvyklé triky. ## Proč na to záleží Bitová manipulace poskytuje elegantní O(1)-prostorová řešení (jako XOR trik na jediné číslo), která v pohovorech udivují. Bitmask DP činí mnoho kombinatorických problémů stavového prostoru řešitelnými. Je nezbytná v systémech, grafice, kompresi a kódu, kde je kritická výkon a každý cyklus se počítá.