0Pricing
Coding Interview Prep · Урок

Побитовые операторы: AND, OR, XOR, NOT и сдвиги

Повторите все шесть побитовых операторов с таблицами истинности и примерами на Python и разберитесь, как сдвиги влево и вправо связаны с умножением и делением на два

«Побитовые операторы: AND, OR, XOR, NOT и сдвиги» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 1 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.

Зачем нужна работа с битами

Работа с битами позволяет напрямую оперировать двоичным представлением целых чисел. Многие задачи, которые кажутся сложными, становятся тривиальными благодаря правильному побитовому приёму: например, поиск пропущенного числа за O(n) времени и O(1) дополнительной памяти, обмен значениями переменных без временной переменной или компактное кодирование подмножеств. На собеседованиях такие задачи проверяют понимание низкоуровневых принципов и умение творчески мыслить.

Целые числа Python имеют произвольную точность — они могут быть настолько большими, насколько позволяет память, — но побитовые операции на аппаратном уровне всегда следуют стандартной семантике дополнительного кода. Все шесть операторов побитово работают с двоичными представлениями целых чисел.

# All six bitwise operators in Python
a, b = 0b1010, 0b1100  # 10 and 12 in decimal
print(f'a = {bin(a)} = {a}')
print(f'b = {bin(b)} = {b}')
print(f'a & b  (AND) = {bin(a & b)} = {a & b}')   # 1000 = 8
print(f'a | b  (OR)  = {bin(a | b)} = {a | b}')   # 1110 = 14
print(f'a ^ b  (XOR) = {bin(a ^ b)} = {a ^ b}')   # 0110 = 6
print(f'~a     (NOT) = {~a}')                       # -11 (two's complement)
print(f'a << 1 (LSH) = {bin(a << 1)} = {a << 1}') # 10100 = 20
print(f'a >> 1 (RSH) = {bin(a >> 1)} = {a >> 1}') # 101 = 5

Оператор AND: маскирование битов

Оператор AND (&) выдаёт 1 только тогда, когда оба входных бита равны 1. Его основное применение — маскирование: выбор определённых битов числа с обнулением всех остальных. Чтобы проверить, установлен ли бит k в числе n, вычислите n & (1 << k) — если результат не равен нулю, бит k равен 1.

AND также используют, чтобы сбросить младший установленный бит: выражение n & (n - 1) удаляет крайнюю справа единицу. Это применяют для эффективного подсчёта установленных битов и проверки того, является ли число степенью двойки (у степени двойки ровно один установленный бит, поэтому n & (n-1) == 0).

n = 0b10110100  # 180

# Check if bit 5 is set (0-indexed from right)
bit_5 = (n >> 5) & 1
print(f'Bit 5 of {n}: {bit_5}')  # 1

# Clear lowest set bit
print(f'n = {bin(n)}')
print(f'n & (n-1) = {bin(n & (n-1))}')  # 10110000, removed the '100'

# Check power of two
for x in [16, 15, 8, 6, 1, 0]:
    is_pow2 = x > 0 and (x & (x - 1)) == 0
    print(f'{x}: power of 2 = {is_pow2}')

Оператор OR: установка битов

Оператор OR (|) выдаёт 1, если хотя бы один входной бит равен 1. Его основное применение — установка определённого бита в 1 без изменения остальных. Чтобы установить бит k в числе n, используйте n | (1 << k). Единица, сдвинутая в позицию k, включает этот бит; все остальные биты остаются без изменений, потому что операция OR с 0 сохраняет исходное значение.

OR также используют для объединения флагов: если представить флаги функций отдельными битами, несколько флагов можно включить с помощью OR. Например, READ | WRITE | EXECUTE объединяет три бита разрешений в одно целое число.

# Set bit k in n
def set_bit(n, k):
    return n | (1 << k)

n = 0b1000  # 8
print(f'Original: {bin(n)}')
print(f'Set bit 1: {bin(set_bit(n, 1))}')  # 1010
print(f'Set bit 0: {bin(set_bit(n, 0))}')  # 1001

# Flag combination example
READ    = 0b001  # 1
WRITE   = 0b010  # 2
EXECUTE = 0b100  # 4

perms = READ | EXECUTE
print(f'READ|EXECUTE permissions: {bin(perms)} = {perms}')
print(f'Has READ:    {bool(perms & READ)}')
print(f'Has WRITE:   {bool(perms & WRITE)}')
print(f'Has EXECUTE: {bool(perms & EXECUTE)}')

Оператор XOR: переключение и различие

Оператор XOR (^) выдаёт 1, когда входные биты различаются. У XOR есть три важных алгебраических свойства: a ^ a = 0 (одинаковые входы взаимно уничтожаются), a ^ 0 = a (ноль является нейтральным элементом), а сам XOR коммутативен и ассоциативен. Благодаря этим свойствам XOR особенно удобен для поиска единственных элементов.

XOR также используют, чтобы переключить определённый бит: выражение n ^ (1 << k) меняет бит k, оставляя остальные без изменений. Если бит k был равен 0, он становится равен 1; если был равен 1, становится равен 0.

# XOR properties
print(5 ^ 5)    # 0 — same values cancel
print(5 ^ 0)    # 5 — zero is identity
print(5 ^ 3 ^ 3)  # 5 — 3 cancels itself

# Toggle bit k
def toggle_bit(n, k):
    return n ^ (1 << k)

n = 0b1010
print(f'Toggle bit 3: {bin(toggle_bit(n, 3))}')  # 0010 (was 1)
print(f'Toggle bit 0: {bin(toggle_bit(n, 0))}')  # 1011 (was 0)

# XOR swap without temp variable
a, b = 7, 13
a = a ^ b
b = a ^ b   # b now gets original a
a = a ^ b   # a now gets original b
print(f'After XOR swap: a={a}, b={b}')  # a=13, b=7

Оператор NOT и дополнительный код

Оператор NOT (~) инвертирует все биты. В Python выражение ~n равно -(n+1) из-за представления в дополнительном коде. Это удивляет многих: ~5 = -6, а не наивно ожидаемое 0b11111010. Целые числа Python имеют бесконечную точность, поэтому инвертирование всех битов положительного числа даёт отрицательный результат в дополнительном коде.

На практике в Python редко используют ~ отдельно для работы с битами. Вместо этого его применяют вместе с AND для сброса определённых битов или вычисляют ~n & mask, где маска ограничивает разрядность конкретным числом битов (например, & 0xFFFFFFFF для 32-битного представления).

# NOT in Python: ~n = -(n+1)
for n in [0, 1, 5, 127]:
    print(f'~{n} = {~n}')   # all give -(n+1)

# Clear bit k using NOT
def clear_bit(n, k):
    return n & ~(1 << k)

n = 0b1111
print(f'Clear bit 2: {bin(clear_bit(n, 2))}')  # 1011
print(f'Clear bit 0: {bin(clear_bit(n, 0))}')  # 1110

# Limiting to 32-bit with mask
def bitwise_not_32(n):
    return ~n & 0xFFFFFFFF

print(f'32-bit NOT of 5: {bin(bitwise_not_32(5))}')  # 32 zeros then ones

Левый сдвиг: умножение на степени двойки

Оператор левого сдвига (<<) сдвигает все биты влево на k позиций, заполняя освободившиеся справа позиции нулями. Это эквивалентно умножению на 2^k. Сдвиг влево на 1 удваивает значение, а сдвиг на k умножает его на 2^k.

В задачах на собеседованиях левые сдвиги чаще всего используют для создания битовых масок: 1 << k создаёт число, в котором установлен только бит k. Это основа всех операций с битами — установка, сброс, переключение и проверка отдельных битов начинаются с 1 << k.

# Left shift = multiply by 2^k
n = 1
for k in range(8):
    print(f'1 << {k} = {1 << k}')   # 1,2,4,8,16,32,64,128

# Practical use: creating bitmasks
def bit_mask(k):
    return 1 << k

print(f'\nBitmask for bit 0: {bin(bit_mask(0))}')  # 1
print(f'Bitmask for bit 3: {bin(bit_mask(3))}')  # 1000
print(f'Bitmask for bit 7: {bin(bit_mask(7))}')  # 10000000

# Fast exponentiation: 2^10 = 1024
print(f'2^10 = {1 << 10}')  # 1024

Правый сдвиг: деление на степени двойки

Оператор правого сдвига (>>) сдвигает все биты вправо на k позиций, отбрасывая крайние справа k битов. Это эквивалентно целочисленному делению на 2^k. Правый сдвиг в Python всегда арифметический: крайние слева биты заполняются знаковым битом (0 для положительных чисел и 1 для отрицательных).

Распространённый приём на собеседованиях: чтобы извлечь бит k из числа n, используйте (n >> k) & 1. Это сдвигает бит k в позицию 0 и маскирует все остальные биты. Это самый простой способ проверить любой определённый бит без вычисления и сравнения полной маски.

# Right shift = integer division by 2^k
n = 64
for k in range(7):
    print(f'{n} >> {k} = {n >> k}')   # 64,32,16,8,4,2,1

# Extract bit k from n
def get_bit(n, k):
    return (n >> k) & 1

n = 0b10110101  # 181
print(f'\nBits of {n} ({bin(n)}):')
for k in range(8):
    print(f'  Bit {k}: {get_bit(n, k)}')

# Negative number right shift (arithmetic)
print(f'-8 >> 1 = {-8 >> 1}')   # -4 (fills with sign bit 1)

Шпаргалка по практическим приёмам работы с битами

Ниже собраны наиболее распространённые приёмы работы с битами, которые встречаются на собеседованиях. Запомните эти шаблоны — они снова и снова появляются в десятках задач:

  • n & 1 — проверить, является ли n нечётным
  • n & (n-1) — сбросить младший установленный бит
  • n & -n — выделить младший установленный бит
  • n | (1 << k) — установить бит k
  • n & ~(1 << k) — сбросить бит k
  • n ^ (1 << k) — переключить бит k
  • (n >> k) & 1 — проверить бит k
# Bit trick cheatsheet — all at once
n = 0b10110100  # 180

print(f'n = {bin(n)} = {n}')
print(f'n & 1       (odd check)         = {n & 1}')          # 0: even
print(f'n & (n-1)   (clear lowest bit)  = {bin(n & (n-1))}')
print(f'n & -n      (isolate lowest bit) = {bin(n & -n)}')
print(f'n | (1<<1)  (set bit 1)          = {bin(n | (1<<1))}')
print(f'n & ~(1<<2) (clear bit 2)        = {bin(n & ~(1<<2))}')
print(f'n ^ (1<<5)  (toggle bit 5)       = {bin(n ^ (1<<5))}')
print(f'(n>>4) & 1  (check bit 4)        = {(n>>4) & 1}')

Подсчёт установленных битов (попкаунт)

Подсчёт количества единичных битов в целом числе называется попкаунтом. Наивный подход перебирает все биты. Приём Брайана Кернигана работает быстрее: он многократно сбрасывает младший установленный бит с помощью n &= n - 1, подсчитывая число итераций, пока n не станет равным 0. Каждая итерация удаляет ровно один единичный бит, поэтому цикл выполняется ровно столько раз, сколько в числе единичных битов.

В Python 3.10+ есть int.bit_count(), который сразу возвращает это количество. В более старых версиях стандартным ручным подходом считается приём Кернигана. Этот приём также решает задачу «Вес Хэмминга» на LeetCode.

# Method 1: naive O(log n)
def count_bits_naive(n):
    count = 0
    while n:
        count += n & 1
        n >>= 1
    return count

# Method 2: Brian Kernighan O(k) where k = number of set bits
def count_bits_fast(n):
    count = 0
    while n:
        n &= n - 1   # clear lowest set bit
        count += 1
    return count

# Method 3: Python built-in (3.10+)
# n.bit_count()

for x in [0, 1, 7, 255, 180, 1024]:
    naive = count_bits_naive(x)
    fast  = count_bits_fast(x)
    print(f'{x:4d} ({bin(x):10s}): naive={naive}, fast={fast}')

Важные нюансы работы с битами в Python

В отличие от C/Java, целые числа Python могут иметь произвольный размер — переполнения 32- или 64-разрядного типа нет. Поэтому при решении задач, рассчитанных на 32-битное поведение, необходимо вручную ограничивать результаты маской фиксированной разрядности: используйте & 0xFFFFFFFF, чтобы оставить только младшие 32 бита.

Оператор NOT ~n в Python возвращает -(n+1), а не версию с инвертированными битами, которую можно было бы ожидать в C. В задачах с 32-битными числами используйте ~n & 0xFFFFFFFF или вычисляйте 0xFFFFFFFF ^ n, чтобы получить ожидаемое 32-битное дополнение. Эти различия часто становятся причиной ошибок у кандидатов, привыкших к работе с битами в стиле C.

# Python vs C gotchas
# In C: unsigned 32-bit NOT of 5 = 4294967290
# In Python: ~5 = -6
print(f'Python ~5 = {~5}')              # -6
print(f'32-bit ~5 = {~5 & 0xFFFFFFFF}') # 4294967290

# No integer overflow in Python
big = 1 << 100   # 2^100: huge number, no overflow
print(f'2^100 = {big}')  # works fine

# Right shift on negatives: arithmetic (sign-extending)
print(f'-1 >> 3 = {-1 >> 3}')   # -1 (all ones shifted in)

# Safe 32-bit mask for problems expecting C/Java semantics
MASK32 = 0xFFFFFFFF
result = (5 + 0xFFFFFFFE) & MASK32  # simulates 32-bit overflow
print(f'5 + (-2) in 32-bit = {result}')  # 3

Операторы сдвига и умножение

Левый и правый сдвиги позволяют чрезвычайно быстро умножать или делить на степени двойки. На аппаратном уровне сдвиги выполняются одной инструкцией, тогда как умножение и деление требуют нескольких тактов. В Python умножение целых чисел и так эффективно, но понимание этой связи помогает лучше видеть закономерности в битах.

Полезное тождество: чтобы проверить, кратно ли n числу 2^k, используйте (n & (2^k - 1)) == 0. Маска 2^k - 1 содержит единицы во всех младших k битах; операция AND с ней даёт остаток от деления на 2^k. Это эквивалентно n % (2^k), но быстрее в языках на основе C.

# Shift vs arithmetic equivalence
for k in range(1, 5):
    n = 48
    print(f'{n} * 2^{k} = {n * (2**k)} = {n << k} (left shift)')
    print(f'{n} // 2^{k} = {n // (2**k)} = {n >> k} (right shift)')
    print()

# Check divisibility by power of 2
def divisible_by_power_of_2(n, k):
    mask = (1 << k) - 1   # 2^k - 1: lower k bits all 1
    return (n & mask) == 0

for n in [16, 24, 32, 15, 100]:
    print(f'{n} divisible by 4? {divisible_by_power_of_2(n, 2)}')

Быстрая проверка

Проверьте своё понимание концепций курса «Структуры данных и алгоритмы — подготовка к собеседованию по программированию», изученных в этом уроке.

Итоги урока

В этом уроке вы узнали, что AND маскирует биты, OR устанавливает биты, XOR переключает биты и обнаруживает различия, NOT инвертирует биты (в Python даёт -(n+1)), а сдвиги умножают или делят на степени двойки, n & (n-1) сбрасывает младший установленный бит и лежит в основе проверок степеней двойки и подсчёта битов, а в Python нет переполнения фиксированной разрядности, поэтому задачи с 32-битными числами требуют явного маскирования с помощью & 0xFFFFFFFF. Далее мы изучим свойство сам обратимости XOR, чтобы решать задачи из семейства «единственное число».

Часто задаваемые вопросы

Урок «Побитовые операторы: AND, OR, XOR, NOT и сдвиги» бесплатный?

Да — полный текст урока «Побитовые операторы: AND, OR, XOR, NOT и сдвиги» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.

Чему я научусь в уроке «Побитовые операторы: AND, OR, XOR, NOT и сдвиги»?

Повторите все шесть побитовых операторов с таблицами истинности и примерами на Python и разберитесь, как сдвиги влево и вправо связаны с умножением и делением на два Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.

Нужен ли мне опыт, чтобы начать Coding Interview Prep?

Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 1 из 4.

Сколько времени занимает урок «Побитовые операторы: AND, OR, XOR, NOT и сдвиги»?

Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.

Можно ли писать и запускать код в этом уроке Coding Interview Prep?

Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.

Все уроки этого курса

  1. Побитовые операторы: AND, OR, XOR, NOT и сдвиги
  2. Единственное число и свойства XOR
  3. Битовые маски: установить, очистить, инвертировать и проверить
  4. Подсчёт битов, пропущенное число и разворот битов
← Назад к Coding Interview Prep