Bittimaskit: aseta, tyhjennä, vaihda ja tarkista
Toteuttakaa apufunktiot yksittäisten bittien asettamiseen, tyhjentämiseen, vaihtamiseen ja tarkistamiseen sekä käyttäkää bittimaskeja osajoukkojen esittämiseen osajoukkojen luettelointitehtävissä.
Bittimaskit: aseta, tyhjennä, vaihda ja tarkista on ilmainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti CoddyKitissä. Tämä on oppitunti 3/4. Voit lukea koko oppitunnin alta ilmaiseksi ja harjoitella sen jälkeen käytännössä selaimessa sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla. Oppitunti kuuluu Valmistautuminen ohjelmointihaastatteluihin-oppimispolkuun, ja edistymisesi synkronoituu verkon ja CoddyKit-sovelluksen välillä. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.
Mitä bittimaskit ovat
Bittimaski on kokonaisluku, jonka avulla toisesta kokonaisluvusta voidaan valita, muokata tai tarkistaa tiettyjä bittejä. Maskissa on ykköset niissä kohdissa, joista ollaan kiinnostuneita, ja nollat muualla. Bittikohtaisten operaattoreiden kanssa maskien avulla voidaan suorittaa tarkasti kohdennettuja bittioperaatioita vaikuttamatta muihin bitteihin.
Maskien neljä perusoperaatiota ovat asettaminen (bitin kytkeminen päälle), nollaaminen (bitin kytkeminen pois päältä), vaihtaminen (bitin kääntäminen) ja tarkistaminen (sen testaaminen, onko bitti 1). Kussakin käytetään eri operaattoria — vastaavasti OR-, AND-NOT-, XOR- ja AND-operaattoria — maskin 1 << k kanssa.
# 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)}')Bitin asettaminen: bitin kytkeminen päälle
Kun bitti k asetetaan eli pakotetaan arvoksi 1 sen nykyisestä arvosta riippumatta, luvulle suoritetaan OR-operaatio maskin 1 << k kanssa. Koska 0 OR 1 = 1 ja 1 OR 1 = 1, kohdebitti muuttuu ykköseksi. Kaikille muille biteille suoritetaan OR-operaatio nollan kanssa, joten niiden arvot säilyvät ennallaan.
Bitin asettaminen on idempotenttia: sen kutsuminen useita kertoja tuottaa saman tuloksen kuin yksi kutsu. Jos bitti k on jo 1, tulos ei muutu. Tämä ominaisuus on tärkeä lippujen hallinnassa, kun ominaisuus halutaan ottaa käyttöön ilman, että sen nykyisestä tilasta tarvitsee huolehtia.
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}')Bitin nollaaminen: bitin kytkeminen pois päältä
Kun bitti k nollataan eli pakotetaan arvoksi 0 sen nykyisestä arvosta riippumatta, luvulle suoritetaan AND-operaatio maskin komplementin kanssa: n & ~(1 << k). Komplementissa ~(1 << k) kaikkien muiden bittien arvo on 1 paitsi bitin k, jonka arvo on 0. AND-operaatio nollan kanssa pakottaa kohdebitin nollaksi, kun taas AND-operaatio ykkösen kanssa säilyttää kaikkien muiden bittien arvot.
Set-operaation tavoin myös nollaaminen on idempotenttia. Jo nollan olevan bitin nollaaminen ei muuta luvun arvoa. Pythonissa ~(1 << k) toimii oikein millä tahansa k:n arvolla, koska Python käsittelee etumerkin jatkamisen automaattisesti — komplementin kaikki ylemmät bitit ovat käsitteellisesti ykkösiä.
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 = 85Bitin vaihtaminen: bitin kääntäminen
Kun bitti k vaihdetaan eli käännetään arvosta 0 arvoon 1 tai arvosta 1 arvoon 0, luvulle suoritetaan XOR-operaatio maskin 1 << k kanssa. XOR-operaatio ykkösen kanssa kääntää bitin, kun taas XOR-operaatio nollan kanssa jättää sen ennalleen. Tämä on XOR:n perusominaisuus yksittäiseen bittiin sovellettuna.
Vaihtaminen on ainoa näistä neljästä operaatiosta, joka ei ole idempotentti: sen suorittaminen kahdesti palauttaa alkuperäisen arvon. Siksi se sopii erinomaisesti ominaisuuksiin, jotka vuorottelevat kahden tilan välillä, kuten päälle/pois-kytkimeen tai tiiviiseen kokonaislukuesitykseen tallennettuun totuusarvolippuun.
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))}')Bitin tarkistaminen: onko bitti asetettu
Kun tarkistetaan, onko bitti k asetettu, n:ää siirretään oikealle k paikkaa ja tulokselle suoritetaan AND-operaatio ykkösen kanssa: (n >> k) & 1. Näin bitti k tuodaan paikkaan 0 ja kaikki ylemmät bitit maskataan pois, jolloin jäljelle jää 0, jos bitti k oli 0, tai 1, jos se oli 1. Vaihtoehtoisesti voidaan käyttää lauseketta bool(n & (1 << k)), joka palauttaa True/False-arvon.
Bitin tarkistaminen ei muuta arvoa. Useita bittejä voidaan tarkistaa siirtämällä ja maskaamalla kukin paikka erikseen. Tämä muodostaa perustan luvun bittiesityksen läpikäynnille, jota käytetään osajoukkojen luetteloinnissa ja bittimaskitiloihin perustuvassa dynaamisessa ohjelmoinnissa.
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)}')Bittimaskit osajoukkojen esittämiseen
Kokonaisluku, jossa on n bittiä, voi esittää n-alkioisen joukon osajoukkoa: bitti k on 1, jos alkio k kuuluu osajoukkoon, ja muuten 0. Näin osajoukko tiivistetään yhdeksi kokonaisluvuksi, mikä mahdollistaa O(1)-operaatiot: jäsenyyden tarkistamisen (mask & (1 << k)), alkion lisäämisen (mask | (1 << k)), alkion poistamisen (mask & ~(1 << k)) sekä joukkojen unionin ja leikkauksen (mask1 | mask2 ja mask1 & mask2).
Kun alkioita on n, mahdollisia osajoukkoja on 2^n, ja jokainen niistä esitetään yksikäsitteisesti n-bittisenä kokonaislukuna väliltä 0–2^n - 1. Käymällä läpi kaikki kokonaisluvut väliltä 0–2^n - 1 luetellaan kaikki osajoukot.
# 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)}')Maskin kaikkien osajoukkojen läpikäynti
Bittimaskidynaamisessa ohjelmoinnissa on usein käytävä läpi tietyn maskin kaikki osamaskit. Yleinen tekniikka on aloittaa arvosta sub = mask ja jatkaa lausekkeella sub = (sub - 1) & mask, kunnes sub saavuttaa arvon 0. Jokaisella kierroksella saadaan eri osamaski. Kaikkien maskien yli tarkasteltuna aikavaativuus on O(3^n), koska jokainen alkio voi kuulua päämaskiin mutta ei osamaskiin, molempiin tai kumpaankaan.
Tätä tekniikkaa käytetään esimerkiksi ongelmissa, joissa ”taulukko jaetaan saman XOR:n osajoukoiksi” tai ”etsitään minkä tahansa osajoukon suurin AND”. Osamaskien tehokas luetteleminen on edistyneen bittimaskidynaamisen ohjelmoinnin tunnusmerkki.
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")})')Bittimaski-DP: katsaus kauppamatkustajan ongelmaan
Bittimaski-DP ratkaisee ongelmia, joissa tila sisältää käytyjen kohteiden osajoukon. Klassinen esimerkki on kauppamatkustajan ongelma (TSP): etsi kustannuksiltaan pienin kierros, joka käy kaikissa n kaupungissa. Tila on dp[mask][city] = pienin kustannus käydä maskissa olevissa kaupungeissa ja päätyä kaupunkiin city. Kun kaupunkeja on n, tiloja on 2^n × n, joten aikavaativuus on O(n^2 × 2^n) — tämä on toteuttamiskelpoinen, kun n ≤ 20.
Maski toimii tiiviinä käytyjen kohteiden joukon esityksenä. Bittien asettaminen, nollaaminen ja tarkistaminen vastaavat kaupungeissa käymistä, niistä poistumista ja niiden kyselyä. Bittimaski-DP:n ydin on käyttää bittejä tilan tiiviinä joukkona.
# 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 80Monibittinen maskaus: kentän poiminta
Joskus on tarpeen poimia yhden bitin sijaan monibittinen kenttä eli peräkkäisten bittien muodostama alue. Kun haluat poimia bitit positiosta start positioon start+length-1, luo maski, jossa on length peräkkäistä 1-bittiä: mask = (1 << length) - 1, ja käytä sitten lauseketta (n >> start) & mask.
Tätä tekniikkaa käytetään pakattujen kokonaislukumuotojen jäsentämiseen, kuten IP-osoitteissa, pikselitiedoissa tai laitteistorekistereissä, joissa useita pieniä arvoja tallennetaan yhteen kokonaislukuun. Esimerkiksi 16-bittinen RGB565-pikseli tallentaa punaisen bitteihin 15–11, vihreän bitteihin 10–5 ja sinisen bitteihin 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}')Bittimaskit haastattelutehtävissä
Bittimaskit ovat yleisiä seuraavanlaisissa haastattelutehtävissä:
- Osajoukkojen luetteleminen: käy läpi kaikki 2^n osajoukkoa käyttämällä maskeja 0:sta arvoon 2^n-1
- Tilan pakkaamiseen perustuva DP: koodaa käytyjen solmujen tai kohteiden joukko bittimaskiksi DP-tilassa
- Oikeusjärjestelmät: yhdistä READ-, WRITE- ja EXECUTE-liput OR-operaatiolla ja tarkista ne AND-operaatiolla
- Ruudukon käytyjen solujen seuranta: pienissä ruudukoissa pakkaa käydyt solut yhteen kokonaislukuun
Keskeinen merkki bittimaskien hyödyllisyydestä on, että ongelmassa käsitellään pientä joukkoa (n ≤ 20 kohdetta) ja jäsenyyksien yhdistelmiä on seurattava. Suuremmat joukot edellyttävät muita esitystapoja.
# 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 4Tehokkaita bittien luettelointitekniikoita
Kun maskin asetetut bitit käydään läpi, käytössä on kaksi yleistä tekniikkaa. Siirrä ja tarkista -menetelmässä siirretään maskia oikealle ja tarkistetaan LSB. Alimman asetetun bitin eristämisessä alin asetettu bitti eristetään lausekkeella n & -n, käsitellään se ja nollataan sitten lausekkeella n &= n - 1. Toinen menetelmä käy läpi vain asetetut bitit, joten se on nopeampi, kun maski on harva.
Pythonissa voidaan käyttää myös lausekkeita bin(n).count('1') tai n.bit_count() (3.10+) popcount-arvon laskemiseen. Kunkin asetetun bitin bittipaikan selvittämiseen käytetään korkeimman asetetun bitin kohdalla lauseketta n.bit_length() - 1.
# 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}')Pikatarkistus
Testatkaa ymmärrystänne tämän oppitunnin Data Structures & Algorithms — Coding Interview Prep -aiheen käsitteistä.
Oppitunnin kertaus
Tässä oppitunnissa opitte, että bittimaskin neljä perusoperaatiota ovat bitin asettaminen (OR), nollaaminen (AND-NOT), vaihtaminen (XOR) ja tarkistaminen (shift-AND), kokonaisluvuilla voidaan esittää osajoukkoja, joissa kukin bitti ilmaisee yhden alkion kuulumisen joukkoon, mikä mahdollistaa 2^n osajoukon luettelemisen ja monibittisten kenttien poiminta sekä bittimaski-DP hyödyntävät samoja maskausperiaatteita monimutkaisempaan tilan koodaukseen. Seuraavaksi tarkastelemme bittien laskemista, puuttuvia lukuja ja bittien kääntämistä tämän ja edellisen oppitunnin tekniikoilla.
Opi Valmistautuminen ohjelmointihaastatteluihin tekoälytuutorin avulla — ilmaiseksi
Kirjoita ja suorita oikeaa koodia selaimessa, saa välitöntä apua tekoälytuutorilta ympäri vuorokauden ja jatka siitä, mihin jäit, verkossa tai sovelluksessa.
- Kurssit
- 90
- Oppitunnit
- 360
Usein kysytyt kysymykset
Onko oppitunti ”Bittimaskit: aseta, tyhjennä, vaihda ja tarkista” ilmainen?
Kyllä – oppitunnin ”Bittimaskit: aseta, tyhjennä, vaihda ja tarkista” koko tekstin voi lukea täällä verkossa ilmaiseksi. Jos haluat harjoitella interaktiivisesti sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla sekä avata koko Valmistautuminen ohjelmointihaastatteluihin-kurssin, päivitä CoddyKit PROhon. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.
Mitä opin oppitunnilla ”Bittimaskit: aseta, tyhjennä, vaihda ja tarkista”?
Toteuttakaa apufunktiot yksittäisten bittien asettamiseen, tyhjentämiseen, vaihtamiseen ja tarkistamiseen sekä käyttäkää bittimaskeja osajoukkojen esittämiseen osajoukkojen luettelointitehtävissä. Harjoittelet Valmistautuminen ohjelmointihaastatteluihin-aihetta koodilla, jonka suoritat suoraan selaimessa. Ympäri vuorokauden käytettävissä oleva tekoälytuutori vastaa kysymyksiisi oppitunnin aikana.
Tarvitsenko kokemusta aloittaakseni Valmistautuminen ohjelmointihaastatteluihin-opiskelun?
Aiempi kokemus ei ole tarpeen. CoddyKitin Valmistautuminen ohjelmointihaastatteluihin-oppimispolku sopii vasta-alkajista edistyneisiin, joten voit aloittaa tästä tai alusta ja edetä omaan tahtiisi. Tämä on oppitunti 3/4.
Kuinka kauan ”Bittimaskit: aseta, tyhjennä, vaihda ja tarkista”-oppitunnin suorittaminen kestää?
Useimmat CoddyKitin oppitunnit kestävät noin 5–10 minuuttia. Jokainen oppitunti on lyhyt ja interaktiivinen, joten edistyt tasaisesti ja voit jatkaa siitä, mihin jäit – sekä verkossa että sovelluksessa.
Voinko kirjoittaa ja suorittaa koodia tällä Valmistautuminen ohjelmointihaastatteluihin-oppitunnilla?
Kyllä. Jokainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti sisältää sisäänrakennetun koodieditorin, joten voit kirjoittaa ja suorittaa oikeaa koodia suoraan selaimessa ja saada välitöntä palautetta tekoälyltä – paikallista asennusta ei tarvita.
Kaikki tämän kurssin oppitunnit
- Bittioperaattorit: AND, OR, XOR, NOT ja siirrot
- Single Number ja XOR:n ominaisuudet
- Bittimaskit: aseta, tyhjennä, vaihda ja tarkista
- Bittien laskeminen, puuttuva luku ja bittien kääntäminen