Maski bitowe: ustawianie, zerowanie, przełączanie i sprawdzanie
Implementować funkcje pomocnicze do ustawiania, zerowania, przełączania i sprawdzania pojedynczych bitów oraz stosować maski bitowe do reprezentowania podzbiorów w problemach wyliczania podzbiorów
Maski bitowe: ustawianie, zerowanie, przełączanie i sprawdzanie to bezpłatna lekcja DSA Interview Prep na CoddyKit. To lekcja 3 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej DSA Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs DSA Interview Prep zawiera 4 lekcji w sumie.
Czym są maski bitowe
Maska bitowa to liczba całkowita używana do wybierania, modyfikowania lub sprawdzania określonych bitów innej liczby całkowitej. Maska ma jedynki na interesujących nas pozycjach i zera na pozostałych. W połączeniu z operatorami bitowymi maski pozwalają wykonywać precyzyjne operacje na bitach bez zmieniania innych bitów.
Cztery podstawowe operacje z użyciem masek to: ustawianie (włączanie bitu), zerowanie (wyłączanie bitu), przełączanie (odwracanie bitu) i sprawdzanie (testowanie, czy bit ma wartość 1). Każda z nich używa innego operatora — odpowiednio OR, AND-NOT, XOR i AND — oraz maski 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)}')Ustawianie bitu: włączanie bitu
Aby ustawić bit k (wymusić jego wartość 1 niezależnie od bieżącej wartości), wykonaj OR liczby z maską 1 << k. Ponieważ 0 OR 1 = 1 oraz 1 OR 1 = 1, docelowy bit otrzymuje wartość 1. Dla wszystkich pozostałych bitów wykonywana jest operacja OR z 0, która pozostawia je bez zmian.
Ustawianie bitu jest idempotentne — wielokrotne wywołanie ma taki sam efekt jak jednokrotne. Jeśli bit k ma już wartość 1, wynik się nie zmieni. Ta właściwość jest ważna podczas zarządzania flagami, gdy chcą Państwo włączyć funkcję bez martwienia się o jej bieżący stan.
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}')Zerowanie bitu: wyłączanie bitu
Aby wyzerować bit k (wymusić jego wartość 0 niezależnie od bieżącej wartości), wykonaj AND liczby z dopełnieniem maski: n & ~(1 << k). Dopełnienie ~(1 << k) ma wszystkie bity ustawione na 1 poza bitem k, który ma wartość 0. Wykonanie AND z 0 wymusza wyzerowanie docelowego bitu, a wykonanie AND z 1 zachowuje wszystkie pozostałe bity.
Podobnie jak ustawianie, zerowanie jest idempotentne. Wyzerowanie bitu, który już ma wartość 0, nie zmienia liczby. W Pythonie ~(1 << k) działa poprawnie dla dowolnego k, ponieważ Python automatycznie obsługuje rozszerzanie znaku — dopełnienie ma koncepcyjnie wszystkie wyższe bity ustawione na 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 = 85Przełączanie bitu: odwracanie bitu
Aby przełączyć bit k (zmienić jego wartość z 0 na 1 lub z 1 na 0), wykonaj XOR liczby z maską 1 << k. XOR z 1 odwraca bit, a XOR z 0 pozostawia go bez zmian. Jest to podstawowa właściwość XOR zastosowana do pojedynczego bitu.
Przełączanie jest jedyną z czterech operacji, która nie jest idempotentna — dwukrotne wywołanie przywraca pierwotną wartość. Dzięki temu doskonale nadaje się do funkcji przełączających się między dwoma stanami, takich jak przełącznik włączania i wyłączania lub flaga logiczna w zwartej reprezentacji całkowitoliczbowej.
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))}')Sprawdzanie bitu: testowanie, czy bit jest ustawiony
Aby sprawdzić, czy bit k jest ustawiony, przesuń n w prawo o k pozycji i wykonaj AND z 1: (n >> k) & 1. Spowoduje to przeniesienie bitu k na pozycję 0 i zamaskowanie wszystkich wyższych bitów, pozostawiając 0 (bit k miał wartość 0) albo 1 (bit k miał wartość 1). Alternatywnie można użyć bool(n & (1 << k)), aby uzyskać wynik True/False.
Sprawdzanie bitu nie powoduje jego zmiany — nie modyfikuje n. Można sprawdzać wiele bitów, niezależnie przesuwając i maskując każdą pozycję. Jest to podstawa iterowania po reprezentacji bitowej liczby, wykorzystywanego przy wyliczaniu podzbiorów i programowaniu dynamicznym ze stanami reprezentowanymi przez maski bitowe.
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)}')Maski bitowe jako reprezentacja podzbiorów
Liczba całkowita zawierająca n bitów może reprezentować podzbiór zbioru n-elementowego: bit k ma wartość 1, jeśli element k należy do podzbioru, a w przeciwnym razie ma wartość 0. Pozwala to skompresować podzbiór do jednej liczby całkowitej i wykonywać operacje w czasie O(1): sprawdzanie przynależności (mask & (1 << k)), dodawanie elementu (mask | (1 << k)), usuwanie elementu (mask & ~(1 << k)) oraz sumę i część wspólną zbiorów (mask1 | mask2 i mask1 & mask2).
Dla n elementów istnieje 2^n możliwych podzbiorów, z których każdy jest jednoznacznie reprezentowany przez n-bitową liczbę całkowitą od 0 do 2^n - 1. Iterowanie po wszystkich liczbach od 0 do 2^n - 1 wylicza wszystkie podzbiory.
# 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)}')Iterowanie po wszystkich podzbiorach maski
W programowaniu dynamicznym z maskami bitowymi często trzeba iterować po wszystkich podzbiorach danej maski. Typowa sztuczka polega na rozpoczęciu od sub = mask i iterowaniu za pomocą sub = (sub - 1) & mask, aż sub osiągnie 0. Każda iteracja zwraca inną podmaskę. Łączna złożoność dla wszystkich masek wynosi O(3^n), ponieważ każdy element może należeć do maski zewnętrznej, ale nie do podmaski, należeć do obu masek albo nie należeć do żadnej z nich.
Technika ta pojawia się w zadaniach takich jak „podział tablicy na podzbiory o równym XOR” lub „znalezienie maksymalnego AND dowolnego podzbioru”. Możliwość wydajnego wyliczania podmasek jest charakterystyczną cechą zaawansowanego programowania dynamicznego z maskami bitowymi.
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")})')DP z maską bitową: wprowadzenie do problemu komiwojażera
DP z maską bitową rozwiązuje problemy, w których stan obejmuje podzbiór odwiedzonych elementów. Klasycznym przykładem jest problem komiwojażera (TSP): należy znaleźć trasę o minimalnym koszcie, odwiedzającą n miast. Stan to dp[mask][city] = minimalny koszt odwiedzenia miast znajdujących się w mask i zakończenia trasy w city. Dla n miast istnieje 2^n × n stanów, co daje czas O(n^2 × 2^n) — wystarczający dla n ≤ 20.
Maska pełni funkcję skompresowanego zbioru odwiedzonych elementów. Ustawianie, czyszczenie i sprawdzanie bitów odpowiada odwiedzaniu, opuszczaniu i sprawdzaniu miast. To istota DP z maską bitową: używanie bitów jako zwartego zbioru reprezentującego stan.
# 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 80Maskowanie wielu bitów: wyodrębnianie pola
Czasami trzeba wyodrębnić nie pojedynczy bit, lecz pole wielobitowe — spójny zakres bitów. Aby wyodrębnić bity od pozycji start do start+length-1, należy utworzyć maskę złożoną z length kolejnych bitów 1: mask = (1 << length) - 1, a następnie zastosować (n >> start) & mask.
Technikę tę stosuje się podczas analizowania spakowanych formatów liczb całkowitych, takich jak adresy IP, dane pikseli czy rejestry sprzętowe, w których kilka małych wartości przechowuje się w jednej liczbie całkowitej. Na przykład 16-bitowy piksel RGB565 przechowuje czerwień w bitach 15-11, zieleń w 10-5, a niebieski w 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}')Maski bitowe w zadaniach rekrutacyjnych
Maski bitowe często pojawiają się w następujących typach zadań rekrutacyjnych:
- Enumeracja podzbiorów: iterowanie po wszystkich 2^n podzbiorach za pomocą masek od 0 do 2^n-1
- DP z kompresją stanu: kodowanie zbioru odwiedzonych węzłów lub elementów jako maski bitowej w stanie DP
- Systemy uprawnień: łączenie flag READ/WRITE/EXECUTE operacją OR i sprawdzanie ich operacją AND
- Śledzenie odwiedzonych pól siatki: w przypadku małych siatek pakowanie informacji o odwiedzonych polach do jednej liczby całkowitej
Kluczową wskazówką, że warto użyć masek bitowych, jest mały zbiór (n ≤ 20 elementów) oraz konieczność śledzenia kombinacji przynależności elementów. Większe zbiory wymagają innych reprezentacji.
# 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 4Efektywne techniki enumeracji bitów
Podczas iterowania po ustawionych bitach maski stosuje się dwie popularne techniki. Metoda przesuwania i sprawdzania polega na przesuwaniu w prawo i sprawdzaniu bitu LSB. Metoda izolowania najmłodszego ustawionego bitu polega na wyodrębnieniu najmłodszego ustawionego bitu za pomocą n & -n, przetworzeniu go, a następnie wyczyszczeniu za pomocą n &= n - 1. Druga metoda odwiedza tylko ustawione bity, więc jest szybsza, gdy maska jest rzadka.
W Pythonie można również użyć bin(n).count('1') lub n.bit_count() (3.10+) do zliczania jedynek. Aby uzyskać pozycję najwyższego ustawionego bitu, należy użyć 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}')Szybki test
Sprawdź swoją znajomość zagadnień Data Structures & Algorithms — Coding Interview Prep z tej lekcji.
Podsumowanie lekcji
W tej lekcji nauczyli się Państwo, że: cztery podstawowe operacje na maskach bitowych to ustawianie (OR), czyszczenie (AND-NOT), przełączanie (XOR) i sprawdzanie (shift-AND), liczby całkowite mogą reprezentować podzbiory, w których każdy bit koduje przynależność jednego elementu, umożliwiając enumerację 2^n podzbiorów, a wyodrębnianie pól wielobitowych i DP z maską bitową wykorzystują te same zasady maskowania do bardziej złożonego kodowania stanu. W następnej części zajmiemy się zliczaniem bitów, brakującymi liczbami i odwracaniem bitów, wykorzystując techniki z tej oraz poprzedniej lekcji.
Często zadawane pytania
Czy lekcja „Maski bitowe: ustawianie, zerowanie, przełączanie i sprawdzanie” jest bezpłatna?
Tak — pełny tekst „Maski bitowe: ustawianie, zerowanie, przełączanie i sprawdzanie” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu DSA Interview Prep, przejdź na CoddyKit PRO. Kurs DSA Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „Maski bitowe: ustawianie, zerowanie, przełączanie i sprawdzanie”?
Implementować funkcje pomocnicze do ustawiania, zerowania, przełączania i sprawdzania pojedynczych bitów oraz stosować maski bitowe do reprezentowania podzbiorów w problemach wyliczania podzbiorów Ćwiczysz DSA Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć DSA Interview Prep?
Nie wymagamy żadnego doświadczenia. DSA Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 3 z 4.
Ile czasu zajmuje lekcja „Maski bitowe: ustawianie, zerowanie, przełączanie i sprawdzanie”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji DSA Interview Prep?
Tak. Każda lekcja DSA Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Operatory bitowe: AND, OR, XOR, NOT i przesunięcia
- Single Number i właściwości XOR
- Maski bitowe: ustawianie, zerowanie, przełączanie i sprawdzanie
- Zliczanie bitów, brakująca liczba i odwracanie bitów