Hvad er almindelige bit-manipulations-tricks?

Question

Accepted Answer

**Bit-manipulation** opererer direkte på den binære repræsentation af heltal ved hjælp af AND, OR, XOR, NOT og skift. Det muliggør kompakte, grenløse og meget hurtige operationer. ## Kerneoperationer ```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 ``` ## Nyttige 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) ``` ## Eksempel: find det enkelte tal (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 ``` ## Kompleksitet Bit-operationer er O(1); XOR-scanningen ovenfor er **O(n) tid, O(1) rum**. ## Hvornår bruges det / faldgruber Brug til **bitmasks** (delmængde-enumeration, DP over tilstande), flag, hurtig matematik og lav-niveau/embedded-kode. Vær opmærksom på fortegn-bit, sprogets specifikke skift-adfærd og læsbarhed — kommenter ikke-åbenlyse tricks. ## Hvorfor det betyder noget Bit-manipulation giver elegante O(1)-rum-løsninger (som XOR-single-number-tricket), der imponerer under interviews. Bitmask DP gør mange kombinatoriske tilstands-rum-problemer praktiske. Det er væsentligt i systemer, grafik, kompression og ydelses-kritisk kode, hvor hver cyklus tæller.