Vilka är vanliga bitmaniputrikot?

Question

Accepted Answer

**Bitmanipulation** opererar direkt på binär representation av heltal med AND, OR, XOR, NOT och skift. Det möjliggör kompakta, greningsfria och mycket snabba operationer. ## Kärnoperationer ```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 ``` ## Användbara trikot ```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) ``` ## Exempel: hitta det enda talet (XOR-trikt) ```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 ``` ## Komplexitet Bitoperationer är O(1); XOR-skanningen ovan är **O(n) tid, O(1) utrymme**. ## När du ska använda / fallgropar Använd för **bitmasks** (uppräkning av delmängder, DP över tillstånd), flaggor, snabb matematik och lågnivå/inbäddad kod. Akta dig för teckenbitar, språkspecifikt skiftbeteende och läsbarhet — kommentera icke-uppenbara trikot. ## Varför det är viktigt Bitmanipulation ger eleganta O(1)-utrymmeslösningar (som XOR-enkeltalsrikets) som imponerar på intervjuer. Bitmask DP gör många kombinatoriska tillståndsrymdproblem lösbara. Det är essentiellt i system, grafik, kompression och prestandakritisk kod där varje cykel räknas.