Hva er vanlige bit-manipulasjonstricks?

Question

Accepted Answer

**Bitmanipulasjon** opererer direkte på binærrepresentasjonen av heltall ved hjelp av AND, OR, XOR, NOT og skift. Det muliggjør kompakte, grein-frie og svært raske operasjoner. ## Kjernoperasjoner ```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: finn det enkelte tallet (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 Bitoperasjoner er O(1); XOR-skanningen ovenfor er **O(n) tid, O(1) plass**. ## Når skal man bruke det / fallgruver Bruk for **bitmasks** (delmengdeopptelling, DP over tilstander), flagg, rask matematikk og kode på lavt nivå/embedded. Vær oppmerksom på fortegnsbit, språkspesifikk skiftoppførsel og lesbarhet — kommenter ikke-åpenbare tricks. ## Hvorfor det betyr noe Bitmanipulasjon gir elegante O(1)-plass-løsninger (som XOR single-number-tricket) som imponerer i intervjuer. Bitmask DP gjør mange kombinatoriske tillstandsrom-problemer håndterlige. Det er essensielt i systemer, grafikk, komprimering og ytelses-kritisk kode der hver syklus betyr noe.