Bitmasker: Sett, fjern, inverter og kontroller
Implementer hjelpefunksjoner for å sette, fjerne, invertere og kontrollere enkeltbiter, og bruk bitmasker til å representere delmengder i problemer med delmengdeenumerering.
Bitmasker: Sett, fjern, inverter og kontroller er en gratis leksjon i Forberedelse til kodeintervjuer på CoddyKit. Dette er leksjon 3 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i Forberedelse til kodeintervjuer, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
Hva er bitmasker?
En bitmaske er et heltall som brukes til å velge, endre eller kontrollere bestemte biter i et annet heltall. Masken har 1-biter i posisjonene som er relevante, og 0-biter ellers. Kombinert med bitvise operatorer gjør masker det mulig å utføre detaljerte bitoperasjoner uten å påvirke andre biter.
De fire grunnleggende maskeoperasjonene er: sette (slå på en bit), nullstille (slå av en bit), veksle (invertere en bit) og kontrollere (teste om en bit er 1). Hver operasjon bruker en annen operator — henholdsvis OR, AND-NOT, XOR og AND — sammen med masken 1 << k.
# The four fundamental bit mask operations
def set_bit(n, k): return n | (1 << k) # OR to set
def clear_bit(n, k): return n & ~(1 << k) # AND-NOT to clear
def toggle_bit(n, k): return n ^ (1 << k) # XOR to toggle
def check_bit(n, k): return (n >> k) & 1 # shift+AND to check
n = 0b10110101 # 181
print(f'n = {bin(n)}')
print(f'set bit 1: {bin(set_bit(n, 1))}')
print(f'clear bit 2: {bin(clear_bit(n, 2))}')
print(f'toggle bit 0: {bin(toggle_bit(n, 0))}')
print(f'check bit 4: {check_bit(n, 4)}')Sette en bit: slå på en bit
For å sette bit k (tvinge den til 1 uavhengig av den nåværende verdien) utføres OR på tallet og masken 1 << k. Siden 0 OR 1 = 1 og 1 OR 1 = 1, blir målbitten 1. OR med 0 lar alle andre biter være uendret.
Det å sette en bit er idempotent — å utføre operasjonen flere ganger har samme effekt som å utføre den én gang. Hvis bit k allerede er 1, endres ikke resultatet. Denne egenskapen er viktig ved flaggstyring, der en funksjon skal aktiveres uten at den nåværende tilstanden trenger å tas hensyn til.
def set_bit(n, k):
mask = 1 << k
return n | mask
# Set various bits
n = 0b00001010 # 10
print(f'Original: {bin(n)} = {n}')
for k in [0, 3, 6, 7]:
result = set_bit(n, k)
print(f'Set bit {k}: {bin(result)} = {result}')
# Idempotence: setting already-set bit does nothing
n = 0b1111
print(f'\nAlready set: {bin(set_bit(n, 2))} = {bin(n)} (unchanged)')
# Setting multiple bits at once with a combined mask
mask = (1 << 0) | (1 << 2) | (1 << 4) # bits 0, 2, 4
print(f'Set bits 0,2,4: {bin(0 | mask)} = {0 | mask}')Nullstille en bit: slå av en bit
For å nullstille bit k (tvinge den til 0 uavhengig av den nåværende verdien) utføres AND på tallet og komplementet til masken: n & ~(1 << k). Komplementet ~(1 << k) har alle biter satt til 1 bortsett fra bit k, som er 0. AND med 0 tvinger målbitten til 0, mens AND med 1 bevarer alle andre biter.
På samme måte som å sette en bit er nullstilling idempotent. Hvis en bit som allerede er 0 nullstilles, forblir tallet uendret. I Python fungerer ~(1 << k) korrekt for enhver k, fordi Python håndterer fortegnsutvidelsen automatisk — komplementet har konseptuelt alle høyere biter satt til 1.
def clear_bit(n, k):
mask = ~(1 << k) # all 1s except bit k
return n & mask
n = 0b11111111 # 255: all bits set
print(f'Original: {bin(n)} = {n}')
for k in [0, 3, 6, 7]:
result = clear_bit(n, k)
print(f'Clear bit {k}: {bin(result)} = {result}')
# Clear multiple bits with combined mask complement
def clear_bits(n, positions):
mask = 0
for k in positions:
mask |= (1 << k)
return n & ~mask
result = clear_bits(0b11111111, [1, 3, 5, 7])
print(f'Clear bits 1,3,5,7: {bin(result)} = {result}') # 0b01010101 = 85Veksle en bit: invertere en bit
For å veksle bit k (invertere den fra 0 til 1 eller fra 1 til 0) utføres XOR på tallet og masken 1 << k. XOR med 1 inverterer biten, mens XOR med 0 lar den være uendret. Dette er den grunnleggende egenskapen ved XOR anvendt på én enkelt bit.
Veksling er den eneste av de fire operasjonene som ikke er idempotent — hvis den utføres to ganger, kommer verdien tilbake til utgangspunktet. Dette gjør operasjonen perfekt for funksjoner som veksler mellom to tilstander, for eksempel en av/på-bryter eller et boolsk flagg i en kompakt heltallsrepresentasjon.
def toggle_bit(n, k):
return n ^ (1 << k)
n = 0b10101010 # 170
print(f'Original: {bin(n)}')
print(f'Toggle bit 0: {bin(toggle_bit(n, 0))}') # off->on: 10101011
print(f'Toggle bit 1: {bin(toggle_bit(n, 1))}') # on->off: 10101000
print(f'Toggle bit 7: {bin(toggle_bit(n, 7))}') # on->off: 00101010
# Toggle is its own inverse: two toggles = no change
result = toggle_bit(toggle_bit(n, 3), 3)
print(f'Double toggle bit 3: {bin(result)} == original {bin(n)}? {result == n}')
# Toggle all lower k bits
def toggle_lower_k(n, k):
mask = (1 << k) - 1 # k ones in the lowest positions
return n ^ mask
print(f'Toggle lower 4 bits of {bin(n)}: {bin(toggle_lower_k(n, 4))}')Kontrollere en bit: teste om den er satt
For å kontrollere om bit k er satt høyreskiftes n med k posisjoner, og resultatet AND-es med 1: (n >> k) & 1. Dette flytter bit k til posisjon 0 og maskerer bort alle høyere biter, slik at 0 blir igjen (bit k var 0) eller 1 (bit k var 1). Alternativt kan bool(n & (1 << k)) brukes for å få et True/False-resultat.
Kontroll av en bit er ikke-destruktiv — n endres ikke. Flere biter kan kontrolleres ved å skifte og maskere hver posisjon separat. Dette er grunnlaget for å iterere over bitrepresentasjonen til et tall, noe som brukes i enumerering av delmengder og dynamisk programmering med bitmasketilstander.
def check_bit(n, k):
return (n >> k) & 1
def is_bit_set(n, k):
return bool(n & (1 << k))
n = 0b10110101 # 181
print(f'n = {bin(n)} = {n}')
for k in range(8):
print(f'Bit {k}: {check_bit(n, k)} ({"set" if check_bit(n, k) else "clear"})')
# Count set bits using check_bit
def count_set_bits(n):
return sum(check_bit(n, k) for k in range(n.bit_length()))
print(f'\nSet bits in {n}: {count_set_bits(n)}')
# Get bit representation as list (LSB first)
def to_bit_list(n, width=8):
return [check_bit(n, k) for k in range(width)]
print(f'Bit list (LSB first): {to_bit_list(n)}')Bitmasker for representasjon av delmengder
Et heltall med n biter kan representere en delmengde av en mengde med n elementer: bit k er 1 hvis element k er med i delmengden, og ellers 0. Dette komprimerer en delmengde til ett enkelt heltall og muliggjør O(1)-operasjoner: medlemskapstest (mask & (1 << k)), legge til et element (mask | (1 << k)), fjerne et element (mask & ~(1 << k)) og union og snitt av mengder (mask1 | mask2 og mask1 & mask2).
Med n elementer finnes det 2^n mulige delmengder, og hver av dem representeres entydig av et n-bits heltall fra 0 til 2^n - 1. Ved å iterere over alle heltall fra 0 til 2^n - 1 enumereres alle delmengdene.
# Subset representation with bitmasks
elements = ['A', 'B', 'C', 'D']
n = len(elements)
def subset_from_mask(mask):
return [elements[k] for k in range(n) if (mask >> k) & 1]
# Enumerate all 2^n subsets
print('All subsets:')
for mask in range(1 << n): # 0 to 15 for n=4
print(f' {mask:04b}: {subset_from_mask(mask)}')
# Set operations
mask_ab = 0b0011 # {A, B}
mask_bc = 0b0110 # {B, C}
print(f'\nUnion: {subset_from_mask(mask_ab | mask_bc)}')
print(f'Intersection: {subset_from_mask(mask_ab & mask_bc)}')
print(f'Difference A\\B: {subset_from_mask(mask_ab & ~mask_bc & 0b1111)}')Iterere over alle delmengder av en maske
I dynamisk programmering med bitmasker er det ofte nødvendig å iterere over alle delmengder av en gitt maske. Et vanlig triks er å starte med sub = mask og iterere med sub = (sub - 1) & mask til sub når 0. Hver iterasjon gir en annen delmaske. Totalt er dette O(3^n) på tvers av alle masker, fordi hvert element kan være i den ytre masken, men ikke i delmasken, i begge, eller i ingen av dem.
Denne teknikken brukes i problemer som «dele en array inn i delmengder med lik XOR» eller «finne den største AND-verdien til en delmengde». Evnen til å enumerere delmasker effektivt er et kjennetegn på avansert bitmaske-DP.
def all_submasks(mask):
submasks = []
sub = mask
while sub > 0:
submasks.append(sub)
sub = (sub - 1) & mask
submasks.append(0) # empty subset
return submasks
mask = 0b1011 # {0, 1, 3}
elements = ['A', 'B', 'C', 'D']
def show(m): return '{' + ','.join(elements[k] for k in range(4) if (m>>k)&1) + '}'
print(f'All submasks of {bin(mask)} = {show(mask)}:')
for sub in all_submasks(mask):
print(f' {bin(sub):6s}: {show(sub)}')
print(f'Total: {len(all_submasks(mask))} submasks (should be 2^{bin(mask).count("1")} = {2**bin(mask).count("1")})')Bitmaske-DP: forhåndsvisning av det handelsreisende problemet
Bitmaske-DP løser problemer der tilstanden inkluderer en delmengde av besøkte elementer. Det klassiske eksempelet er det handelsreisende problemet (TSP): finn en tur med lavest mulig kostnad som besøker n byer. Tilstanden er dp[mask][city] = minste kostnad for å besøke byene i mask, med avslutning i city. Med n byer finnes det 2^n × n tilstander, noe som gir tidskompleksiteten O(n^2 × 2^n) — gjennomførbart for n ≤ 20.
Masken fungerer som et komprimert sett over besøkte elementer. Å sette, fjerne og kontrollere biter tilsvarer å besøke, forlate og undersøke byer. Dette er kjernen i bitmaske-DP: bruk biter som et kompakt sett i tilstanden.
# TSP with bitmask DP
import sys
def tsp(dist):
n = len(dist)
INF = float('inf')
# dp[mask][v] = min cost to reach v having visited cities in mask
dp = [[INF] * n for _ in range(1 << n)]
dp[1][0] = 0 # start at city 0, only city 0 visited (mask=1=0b0001)
for mask in range(1 << n):
for v in range(n):
if dp[mask][v] == INF: continue
if not (mask >> v) & 1: continue # v must be in mask
for u in range(n):
if (mask >> u) & 1: continue # u must not be visited
new_mask = mask | (1 << u)
dp[new_mask][u] = min(dp[new_mask][u], dp[mask][v] + dist[v][u])
full_mask = (1 << n) - 1
return min(dp[full_mask][v] + dist[v][0] for v in range(1, n))
dist = [[0,10,15,20],[10,0,35,25],[15,35,0,30],[20,25,30,0]]
print('TSP minimum tour cost:', tsp(dist)) # should be 80Maskering av flere biter: hente ut et felt
Noen ganger må du hente ut ikke bare én bit, men et felt med flere biter — et sammenhengende område med biter. For å hente ut bitene fra posisjon start til start+length-1 oppretter du en maske med length sammenhengende 1-biter: mask = (1 << length) - 1, og bruker deretter (n >> start) & mask.
Denne teknikken brukes ved tolking av pakkede heltallsformater, for eksempel IP-adresser, pikseldata eller maskinvareregistre, der flere små verdier lagres i ett heltall. En 16-biters RGB565-piksel lagrer for eksempel rød i bitene 15–11, grønn i 10–5 og blå i 4–0.
def extract_field(n, start, length):
mask = (1 << length) - 1 # e.g., length=3 => mask=0b111
return (n >> start) & mask
# RGB565 pixel format: RRRRRGGGGGGBBBBB
pixel = 0b1111100111001000 # 63432
red = extract_field(pixel, 11, 5) # bits 15-11
green = extract_field(pixel, 5, 6) # bits 10-5
blue = extract_field(pixel, 0, 5) # bits 4-0
print(f'Pixel: {hex(pixel)}')
print(f'Red: {red} ({bin(red)})')
print(f'Green: {green} ({bin(green)})')
print(f'Blue: {blue} ({bin(blue)})')
# Packing values back
def pack_rgb565(r, g, b):
return (r << 11) | (g << 5) | b
packe = pack_rgb565(red, green, blue)
print(f'Repacked: {hex(packed) if (packed := pack_rgb565(red,green,blue)) else 0}')Bitmasker i intervjuproblemer
Bitmasker dukker ofte opp i disse typene intervjuproblemer:
- Enumerering av delmengder: gå gjennom alle 2^n delmengder ved å bruke maskene 0 til 2^n-1
- DP med tilstandskompresjon: kod et sett med besøkte noder eller elementer som en bitmaske i DP-tilstanden
- Rettighetssystemer: kombiner READ/WRITE/EXECUTE-flagg med OR, og kontroller dem med AND
- Sporing av besøkte ruter i et rutenett: pakk besøkte celler inn i ett heltall for små rutenett
En viktig indikasjon på at bitmasker er nyttige, er at problemet omfatter et lite sett (n ≤ 20 elementer), og at kombinasjoner av medlemskap må spores. Større sett krever andre representasjoner.
# Subset sum with bitmask enumeration
def subset_sum_exists(nums, target):
n = len(nums)
for mask in range(1 << n):
total = sum(nums[k] for k in range(n) if (mask >> k) & 1)
if total == target:
subset = [nums[k] for k in range(n) if (mask >> k) & 1]
print(f'Found subset {subset} summing to {target}')
return True
return False
subset_sum_exists([3, 1, 4, 1, 5], 10) # finds a subset summing to 10
# Check if permutation covers all required elements (bitmask approach)
required = 0b11111 # need all 5 elements
visited = 0b01101 # visited elements 0, 2, 3
all_visited = (visited & required) == required
print(f'All required visited: {all_visited}') # False: missing bits 1 and 4Effektive triks for bitopplisting
Når du går gjennom bitene som er satt i en maske, brukes to vanlige teknikker. Skift-og-kontroller-metoden: skift mot høyre og kontroller LSB. Metoden for isolering av laveste satte bit: isoler den laveste satte biten med n & -n, behandle den, og fjern den deretter med n &= n - 1. Den andre metoden besøker bare biter som er satt, og er raskere når masken er spredt.
I Python kan også bin(n).count('1') eller n.bit_count() (3.10+) brukes til popcount. For bitposisjonen til hver bit som er satt brukes n.bit_length() - 1 for den høyeste satte biten.
# Iterate over set bit positions
def set_bit_positions(n):
positions = []
k = 0
while n:
if n & 1:
positions.append(k)
n >>= 1
k += 1
return positions
# Faster: use lowest-set-bit isolation
def set_bit_positions_fast(n):
positions = []
while n:
lsb = n & -n # isolate lowest set bit
k = lsb.bit_length() - 1 # position of that bit
positions.append(k)
n &= n - 1 # clear lowest set bit
return positions
mask = 0b10110101
print(f'Set positions (naive): {set_bit_positions(mask)}')
print(f'Set positions (fast): {set_bit_positions_fast(mask)}')
print(f'Bit count: {bin(mask).count("1")}')
print(f'Highest set bit: {mask.bit_length() - 1}')Hurtigsjekk
Test forståelsen av konseptene fra denne leksjonen i Data Structures & Algorithms — Coding Interview Prep.
Oppsummering av leksjonen
I denne leksjonen lærte du at: de fire grunnleggende bitmaskeoperasjonene er sette (OR), fjerne (AND-NOT), veksle (XOR) og kontrollere (skift-AND), heltall kan representere delmengder der hver bit angir medlemskapet til ett element, noe som muliggjør enumerering av 2^n delmengder, og uthenting av flerbitsfelt og bitmaske-DP bruker de samme maskeringsprinsippene for mer kompleks tilstandskoding. Deretter utforsker vi telling av biter, manglende tall og bitreversering ved hjelp av teknikkene fra denne og den forrige leksjonen.
Lær deg Forberedelse til kodeintervjuer med en AI-veileder – gratis
Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.
- Kurs
- 90
- Leksjoner
- 360
Ofte stilte spørsmål
Er leksjonen «Bitmasker: Sett, fjern, inverter og kontroller» gratis?
Ja – hele teksten i «Bitmasker: Sett, fjern, inverter og kontroller» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av Forberedelse til kodeintervjuer-kurset, kan du oppgradere til CoddyKit PRO. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
Hva lærer jeg i «Bitmasker: Sett, fjern, inverter og kontroller»?
Implementer hjelpefunksjoner for å sette, fjerne, invertere og kontrollere enkeltbiter, og bruk bitmasker til å representere delmengder i problemer med delmengdeenumerering. Du øver på Forberedelse til kodeintervjuer med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.
Trenger jeg erfaring for å begynne med Forberedelse til kodeintervjuer?
Ingen tidligere erfaring er nødvendig. Forberedelse til kodeintervjuer på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 3 av 4.
Hvor lang tid tar leksjonen «Bitmasker: Sett, fjern, inverter og kontroller»?
De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.
Kan jeg skrive og kjøre kode i denne Forberedelse til kodeintervjuer-leksjonen?
Ja. Alle Forberedelse til kodeintervjuer-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.
Alle leksjonene i dette kurset
- Bitvise operatorer: AND, OR, XOR, NOT og skift
- Single Number og XOR-egenskaper
- Bitmasker: Sett, fjern, inverter og kontroller
- Tell biter, manglende tall og inverterte biter