Битовые маски: установить, очистить, инвертировать и проверить
Реализуйте вспомогательные функции для установки, очистки, инвертирования и проверки отдельных битов и применяйте битовые маски для представления подмножеств в задачах их перечисления
«Битовые маски: установить, очистить, инвертировать и проверить» — бесплатный урок DSA Interview Prep на CoddyKit. Это урок 3 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения DSA Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс DSA Interview Prep содержит 4 уроков всего.
Что такое битовые маски
Битовая маска — это целое число, используемое для выбора, изменения или проверки определённых битов другого целого числа. В маске на нужных позициях стоят единицы, а в остальных — нули. В сочетании с побитовыми операторами маски позволяют выполнять точные побитовые операции, не затрагивая другие биты.
Четыре основные операции с масками: установка (включение бита), сброс (выключение бита), инвертирование (изменение бита на противоположный) и проверка (определение, равен ли бит 1). Для каждой используется свой оператор — OR, AND-NOT, XOR и AND соответственно — с маской 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)}')Установка бита: включение бита
Чтобы установить бит k (принудительно сделать его равным 1 независимо от текущего значения), выполните OR числа с маской 1 << k. Поскольку 0 OR 1 = 1 и 1 OR 1 = 1, целевой бит станет равен 1. Для всех остальных битов выполняется OR с 0, поэтому они не изменяются.
Установка бита идемпотентна: многократный вызов даёт тот же эффект, что и однократный. Если бит k уже равен 1, результат не изменится. Это свойство важно при управлении флагами, когда требуется включить функцию, не беспокоясь о её текущем состоянии.
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}')Сброс бита: выключение бита
Чтобы сбросить бит k (принудительно сделать его равным 0 независимо от текущего значения), выполните AND числа с дополнением маски: n & ~(1 << k). Дополнение ~(1 << k) содержит единицы во всех битах, кроме бита k, равного 0. AND с 0 принудительно устанавливает целевой бит в 0, а AND с 1 сохраняет все остальные биты.
Как и установка, сброс идемпотентен. Сброс уже равного 0 бита не изменяет число. В Питоне ~(1 << k) корректно работает для любого k, поскольку Питон автоматически обрабатывает знаковое расширение: концептуально во всех старших битах дополнения стоят единицы.
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 = 85Инвертирование бита: изменение бита на противоположный
Чтобы инвертировать бит k (изменить его с 0 на 1 или с 1 на 0), выполните XOR числа с маской 1 << k. XOR с 1 инвертирует бит, а XOR с 0 оставляет его без изменений. Это основное свойство XOR, применённое к одному биту.
Инвертирование — единственная из четырёх операций, которая не является идемпотентной: два вызова возвращают исходное значение. Поэтому оно идеально подходит для функций, переключающихся между двумя состояниями, например для переключателя включения/выключения или логического флага в компактном представлении целого числа.
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))}')Проверка бита: определение, установлен ли бит
Чтобы проверить, установлен ли бит k, сдвиньте n вправо на k позиций и выполните AND с 1: (n >> k) & 1. Это перемещает бит k на позицию 0 и отбрасывает все старшие биты, оставляя 0 (бит k был равен 0) или 1 (бит k был равен 1). Другой вариант — использовать bool(n & (1 << k)), чтобы получить результат True/False.
Проверка бита неразрушающа: она не изменяет n. Можно проверить несколько битов, независимо сдвигая и маскируя каждую позицию. Это основа перебора битового представления числа, используемого при перечислении подмножеств и в динамическом программировании с состояниями в виде битовых масок.
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)}')Битовые маски для представления подмножеств
Целое число из n битов может представлять подмножество множества из n элементов: бит k равен 1, если элемент k входит в подмножество, и 0 в противном случае. Это сжимает подмножество до одного целого числа и позволяет выполнять операции за O(1): проверку принадлежности (mask & (1 << k)), добавление элемента (mask | (1 << k)), удаление элемента (mask & ~(1 << k)), а также объединение и пересечение множеств (mask1 | mask2 и mask1 & mask2).
Для n элементов существует 2^n возможных подмножеств, каждое из которых однозначно представляется n-битным целым числом от 0 до 2^n - 1. Перебор всех целых чисел от 0 до 2^n - 1 перечисляет все подмножества.
# 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)}')Перебор всех подмножеств маски
В динамическом программировании с битовыми масками часто требуется перебрать все подмножества заданной маски. Распространённый приём: начните с sub = mask и повторяйте sub = (sub - 1) & mask, пока sub не достигнет 0. Каждая итерация даёт новую подмаску. Суммарная сложность для всех масок составляет O(3^n), поскольку каждый элемент может находиться во внешней маске, но не в подмаске, в обеих масках или ни в одной из них.
Этот приём встречается в задачах вроде «разбить массив на подмножества с одинаковым XOR» или «найти максимальный AND любого подмножества». Возможность эффективно перечислять подмаски — характерный признак продвинутого динамического программирования с битовыми масками.
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 с битовой маской: обзор задачи коммивояжёра
DP с битовой маской решает задачи, в которых состояние включает подмножество посещённых объектов. Классический пример — задача коммивояжёра (TSP): найти маршрут минимальной стоимости, посещающий n городов. the Состояние — это dp[mask][city] = минимальная стоимость посещения городов из mask с завершением в городе city. При n городах существует 2^n × n состояний, что даёт время O(n^2 × 2^n) — это подходит для n ≤ 20.
Маска служит сжатым множеством посещённых объектов. Установка, сброс и проверка битов соответствуют посещению, уходу и запросу сведений о городах. Это основа DP с битовой маской: использование битов как компактного множества для представления состояния.
# 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 80Маскирование нескольких битов: извлечение поля
Иногда требуется извлечь не только отдельный бит, но и поле из нескольких битов — непрерывный диапазон битов. Чтобы извлечь биты с позиции start по start+length-1, создайте маску из length последовательных единичных битов: mask = (1 << length) - 1, затем примените (n >> start) & mask.
Этот приём используется при разборе упакованных целочисленных форматов, таких как IP-адреса, данные пикселей или аппаратные регистры, где несколько небольших значений хранятся в одном целом числе. Например, 16-битный пиксель RGB565 хранит красный компонент в битах 15-11, зелёный — в битах 10-5, а синий — в битах 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}')Битовые маски в задачах на собеседовании
Битовые маски часто встречаются в следующих типах задач на собеседовании:
- Перебор подмножеств: перебор всех 2^n подмножеств с помощью масок от 0 до 2^n-1
- DP со сжатием состояния: кодирование множества посещённых узлов или объектов в виде битовой маски в состоянии DP
- Системы разрешений: объединение флагов READ/WRITE/EXECUTE с помощью OR, проверка с помощью AND
- Отслеживание посещённых клеток в сетке: для небольших сеток упаковка посещённых клеток в одно целое число
Ключевой признак того, что битовые маски будут полезны: задача связана с небольшим множеством (n ≤ 20 объектов), и требуется отслеживать комбинации принадлежности элементов множеству. Для больших множеств нужны другие представления.
# 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 4Эффективные приёмы перебора битов
При переборе установленных битов маски используются два распространённых приёма. Метод сдвига и проверки: сдвигать число вправо и проверять LSB. Метод изоляции младшего установленного бита: выделить младший установленный бит с помощью n & -n, обработать его, а затем сбросить с помощью n &= n - 1. Второй метод посещает только установленные биты и работает быстрее, когда маска разреженная.
В Python также можно использовать bin(n).count('1') или n.bit_count() (начиная с версии 3.10) для подсчёта единичных битов. Чтобы определить позицию каждого установленного бита, используйте 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}')Быстрая проверка
Проверьте своё понимание концепций «Структуры данных и алгоритмы — подготовка к собеседованию по программированию» из этого урока.
Итоги урока
В этом уроке Вы узнали: the четыре фундаментальные операции с битовыми масками — установить (OR), сбросить (AND-NOT), инвертировать (XOR) и проверить (сдвиг и AND), целые числа могут представлять подмножества, где каждый бит кодирует принадлежность одного элемента, что позволяет перебирать 2^n подмножеств, а также извлечение полей из нескольких битов и DP с битовой маской используют те же принципы маскирования для более сложного кодирования состояния. Далее мы рассмотрим подсчёт битов, пропущенные числа и разворот битов с помощью приёмов из этого и предыдущего урока.
Изучай Python с ИИ-репетитором — бесплатно
Пиши и запускай код прямо в браузере, получай мгновенную помощь от ИИ-репетитора 24/7 и продолжи учиться на сайте или в приложении.
- Курсы
- 30
- Уроки
- 120
Часто задаваемые вопросы
Урок «Битовые маски: установить, очистить, инвертировать и проверить» бесплатный?
Да — полный текст урока «Битовые маски: установить, очистить, инвертировать и проверить» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс DSA Interview Prep, подпишись на CoddyKit PRO. Курс DSA Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «Битовые маски: установить, очистить, инвертировать и проверить»?
Реализуйте вспомогательные функции для установки, очистки, инвертирования и проверки отдельных битов и применяйте битовые маски для представления подмножеств в задачах их перечисления Ты практикуешь DSA Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать DSA Interview Prep?
Предыдущий опыт не требуется. DSA Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 3 из 4.
Сколько времени занимает урок «Битовые маски: установить, очистить, инвертировать и проверить»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке DSA Interview Prep?
Да. Каждый урок DSA Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Побитовые операторы: AND, OR, XOR, NOT и сдвиги
- Единственное число и свойства XOR
- Битовые маски: установить, очистить, инвертировать и проверить
- Подсчёт битов, пропущенное число и разворот битов