Подсчёт битов, пропущенное число и разворот битов
Вычислите количество битов для чисел от 0 до n с помощью DP и приёма с младшим установленным битом, найдите пропущенное число через XOR и разверните биты 32-битного целого числа
«Подсчёт битов, пропущенное число и разворот битов» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 4 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.
Обзор задачи «Подсчёт битов»
Задача «Подсчёт битов» (LeetCode 338) требует: по заданному n вернуть массив ans размера n+1, где ans[i] — количество единичных битов в i. Наивный подход занимает O(n log n): он отдельно подсчитывает биты в каждом числе. Подход DP работает за O(n), используя связь между i и его половиной или младшим установленным битом.
В основе DP лежат два ключевых наблюдения: (1) i >> 1 удаляет младший бит, поэтому bits[i] = bits[i >> 1] + (i & 1). (2) Сброс младшего установленного бита: bits[i] = bits[i & (i-1)] + 1. Оба подхода работают за O(n) времени и используют O(n) памяти для выходного массива.
def count_bits_v1(n):
# O(n log n): naive individual count
return [bin(i).count('1') for i in range(n + 1)]
def count_bits_dp(n):
# O(n): DP using right shift
dp = [0] * (n + 1)
for i in range(1, n + 1):
dp[i] = dp[i >> 1] + (i & 1) # i >> 1 drops last bit
return dp
def count_bits_dp2(n):
# O(n): DP using lowest-set-bit trick
dp = [0] * (n + 1)
for i in range(1, n + 1):
dp[i] = dp[i & (i - 1)] + 1 # i & (i-1) clears lowest set bit
return dp
n = 10
print('Naive:', count_bits_v1(n))
print('DP v1:', count_bits_dp(n))
print('DP v2:', count_bits_dp2(n))Почему работают рекуррентные формулы DP
Для the рекуррентной формулы сдвига вправо dp[i] = dp[i >> 1] + (i & 1): деление на 2 (сдвиг вправо) удаляет последний бит. Если the последний бит равен 1, количество увеличивается на 1; если равен 0, оно не изменяется. Поэтому bits[i] = bits[i // 2] + (i mod 2).
Для the рекуррентной формулы младшего установленного бита dp[i] = dp[i & (i-1)] + 1: i & (i-1) сбрасывает крайний справа единичный бит, поэтому в полученном числе на один установленный бит меньше, чем в i. Следовательно, количество равно количеству битов в уменьшенном числе плюс 1. Обе рекуррентные формулы обрабатывают i в возрастающем порядке, поэтому меньшие подзадачи всегда решаются первыми.
# Trace both recurrences for i = 0..8
print('i | i>>1 | i&1 | dp[i>>1]+(i&1) | i&(i-1) | 1+dp[i&(i-1)]')
print('-' * 60)
dp = [0] * 9
for i in range(1, 9):
# Right shift method
v1 = dp[i >> 1] + (i & 1)
# Lowest set bit method
v2 = dp[i & (i - 1)] + 1
dp[i] = v1 # either works
print(f'{i:2d} ({bin(i)[2:]:4s}) | {i>>1:2d} | {i&1} | {v1} | {i&(i-1):2d} | {v2}')
print('\nFinal dp:', dp)Пропущенное число: подходы XOR и суммы
Задача «Пропущенное число» (LeetCode 268) задаёт массив из n различных чисел в диапазоне [0, n], в котором отсутствует ровно одно число. Подход XOR: применить XOR ко всем индексам от 0 до n и ко всем значениям массива. Одинаковые пары сократятся, и останется пропущенное число. Подход с суммой: expected = n*(n+1)//2, вернуть expected - sum(nums).
Оба подхода работают за O(n) времени и используют O(1) памяти. Подход XOR надёжнее в языках с целыми числами фиксированной разрядности, поскольку позволяет избежать возможного переполнения. В Python оба подхода работают корректно, так как целые числа имеют произвольную точность.
def missing_xor(nums):
n = len(nums)
result = n
for i, val in enumerate(nums):
result ^= i ^ val # each index i cancels its matching value
return result
def missing_sum(nums):
n = len(nums)
return n * (n + 1) // 2 - sum(nums)
test_cases = [
[3, 0, 1], # missing 2
[0, 1], # missing 2
[9,6,4,2,3,5,7,0,1], # missing 8
[0], # missing 1
]
for nums in test_cases:
print(f'{nums} => XOR={missing_xor(nums)}, Sum={missing_sum(nums)}')Разворот битов 32-битного целого числа
Задача «Разворот битов» (LeetCode 190) требует развернуть двоичное представление 32-битного беззнакового целого числа. Итеративный подход: обработать каждый из 32 битов справа налево во входном числе и разместить их слева направо в выходном. На каждой итерации: извлечь крайний справа бит с помощью n & 1, сдвинуть результат влево, чтобы освободить место, применить OR к биту, затем сдвинуть n вправо.
После 32 итераций выходное целое число содержит все 32 бита n в обратном порядке. Это O(32) = O(1) на один вызов или O(1) амортизированно при кэшировании для повторных вызовов с 8-битными фрагментами.
def reverse_bits(n):
result = 0
for _ in range(32):
result = (result << 1) | (n & 1) # shift result left, OR in rightmost bit
n >>= 1 # move to next bit
return result
# Test with known values
print(reverse_bits(0b00000010100101000001111010011100)) # 964176192
print(reverse_bits(0b11111111111111111111111111111101)) # 3221225471
print(reverse_bits(0)) # 0
print(reverse_bits(1)) # 2147483648 (bit 0 goes to bit 31)
print(reverse_bits(0b10000000000000000000000000000000)) # 1Разворот битов: разделяй и властвуй
Более быстрый подход O(log 32) = O(1) разворачивает биты с помощью обмена по принципу «разделяй и властвуй». Сначала меняются местами соседние биты, затем соседние группы по 2 бита, затем группы по 4 бита и так далее. На каждом уровне обмена маски отделяют чередующиеся группы, а сдвиг перемежает их. После 5 обменов все 32 бита оказываются развёрнутыми.
Этот подход использует O(1) фиксированных операций независимо от входных данных и применяется в аппаратных реализациях. Маски являются константами: 0x55555555 (чередующийся шаблон 01), 0x33333333 (чередующийся шаблон 0011), 0x0f0f0f0f (чередующийся шаблон 00001111) и т. д.
def reverse_bits_dc(n):
# Treat n as 32-bit unsigned
n &= 0xFFFFFFFF
# Swap adjacent bits
n = ((n & 0x55555555) << 1) | ((n >> 1) & 0x55555555)
# Swap adjacent 2-bit groups
n = ((n & 0x33333333) << 2) | ((n >> 2) & 0x33333333)
# Swap adjacent 4-bit groups
n = ((n & 0x0f0f0f0f) << 4) | ((n >> 4) & 0x0f0f0f0f)
# Swap adjacent bytes
n = ((n & 0x00ff00ff) << 8) | ((n >> 8) & 0x00ff00ff)
# Swap adjacent 16-bit halves
n = ((n & 0x0000ffff) << 16) | ((n >> 16) & 0x0000ffff)
return n & 0xFFFFFFFF
# Verify against iterative version
def reverse_bits_iter(n):
result = 0
for _ in range(32):
result = (result << 1) | (n & 1); n >>= 1
return result
for test in [0b10110100, 0b11111111, 0, 1, 0xDEADBEEF]:
assert reverse_bits_dc(test) == reverse_bits_iter(test)
print(f'{test:#010x} reversed: {reverse_bits_dc(test):#010x}')Число единичных битов (вес Хэмминга)
Задача «Число единичных битов» (LeetCode 191) требует найти вес Хэмминга (количество единичных битов) беззнакового целого числа. Есть три подхода с разными компромиссами: наивный цикл (O(32)), метод Брайана Кернигана (O(k), где k = количество установленных битов) и встроенный метод Python n.bit_count() (начиная с версии 3.10).
Метод Брайана Кернигана предпочтителен на собеседованиях, поскольку демонстрирует понимание приёма n & (n-1). Каждая итерация удаляет младший установленный бит, поэтому the цикл выполняется ровно столько раз, сколько единичных битов, — это значительно быстрее полного перебора 32 битов для разреженных целых чисел.
def hamming_weight_naive(n):
count = 0
while n:
count += n & 1
n >>= 1
return count
def hamming_weight_kernighan(n):
count = 0
while n:
n &= n - 1 # clear lowest set bit
count += 1
return count
# Python 3.10+
# def hamming_weight_builtin(n): return n.bit_count()
for n in [0, 1, 11, 128, 255, 0xDEADBEEF]:
naive = hamming_weight_naive(n)
kern = hamming_weight_kernighan(n)
bits = bin(n).count('1')
print(f'{n:#012b} ({n:10d}): naive={naive}, kern={kern}, bin={bits}')Сумма последовательных битов: префиксный подход
Иногда требуется быстро подсчитать единичные биты на отрезке [l, r]. Постройте префиксную сумму установленных битов для диапазона от 0 до n: prefix[i] = prefix[i-1] + bin(i).count('1'). Тогда количество битов на отрезке [l, r] равно prefix[r] - prefix[l-1]. После предварительной обработки за O(n) это позволяет выполнять запросы по диапазонам за O(1).
Этот подход обобщается на любой агрегат, основанный на битах, для некоторого диапазона. Например, для подсчёта чисел на отрезке [l, r] с чётным количеством установленных битов используется тот же префиксный подход, но с другой функцией накопления.
def build_bit_prefix(n):
prefix = [0] * (n + 2)
for i in range(1, n + 1):
prefix[i] = prefix[i - 1] + bin(i).count('1')
return prefix
def count_bits_range(prefix, l, r):
return prefix[r] - prefix[l - 1]
# Build prefix for 0..15
prefix = build_bit_prefix(15)
print('Prefix sums (set bit counts up to i):')
for i in range(16):
print(f' i={i:2d} ({bin(i)[2:]:4s}): bits={bin(i).count("1")}, prefix={prefix[i]}')
# Range queries
print(f'\nSet bits in [5, 10]: {count_bits_range(prefix, 5, 10)}')
print(f'Set bits in [1, 15]: {count_bits_range(prefix, 1, 15)}')Разворот битов отрицательных чисел
В Python целые числа знаковые и имеют произвольную разрядность. При развороте битов для задачи LeetCode необходимо рассматривать входное значение как 32-битное беззнаковое целое число. Перед обработкой примените к входному значению маску & 0xFFFFFFFF, чтобы учитывать только 32 бита. Результат также должен быть 32-битным беззнаковым целым числом, то есть неотрицательным.
Если дано целое число Python, которое может быть отрицательным в смысле дополнительного кода, сначала примените & 0xFFFFFFFF, чтобы получить его беззнаковое 32-битное представление, а затем разверните биты. Результат всегда является неотрицательным целым числом от 0 до 2^32 - 1.
def reverse_bits_signed_safe(n):
n &= 0xFFFFFFFF # treat as 32-bit unsigned
result = 0
for _ in range(32):
result = (result << 1) | (n & 1)
n >>= 1
return result & 0xFFFFFFFF
# Python treats -1 as all 1s in two's complement
print(f'-1 as 32-bit unsigned: {-1 & 0xFFFFFFFF:#010x}') # 0xffffffff
print(f'Reversed: {reverse_bits_signed_safe(-1):#010x}') # 0xffffffff (all 1s reversed = all 1s)
# -2 in 32-bit = 0xFFFFFFFE = 11...10
print(f'-2 as 32-bit unsigned: {-2 & 0xFFFFFFFF:#010x}') # 0xfffffffe
print(f'Reversed: {reverse_bits_signed_safe(-2):#010x}') # 0x7fffffffDP с битовыми операциями: закономерности подсчёта битов
Задача подсчёта битов показывает общую закономерность битового DP: если известен ответ для меньшего значения i, его можно вычислить для i с помощью битовой операции за постоянное время. Эта закономерность обобщается на другие задачи подсчёта битов, например на подсчёт чисел с ровно k установленными битами в диапазоне [0, n] с помощью двоичного перебора или на поиск наибольшей степени двойки, на которую делится каждое число.
Есть и другое полезное наблюдение: количество установленных битов для i образует повторяющуюся закономерность внутри каждого интервала, ограниченного степенями двойки. Закономерность для [2^k, 2^(k+1) - 1] совпадает с закономерностью для [0, 2^k - 1], но каждое значение увеличено на 1, поскольку бит k всегда установлен в этом диапазоне.
# Visualise the repeating pattern
def show_bit_pattern(n):
bits = [bin(i).count('1') for i in range(n + 1)]
print('i | bits | pattern')
for i, b in enumerate(bits):
block = i.bit_length() - 1 if i > 0 else 0
print(f'{i:2d} ({bin(i)[2:]:4s}) | {b} | block {block}')
return bits
bits = show_bit_pattern(15)
# Verify the pattern: bits[i] = bits[i - highest_power] + 1 for i >= 2^k
print('\nVerify pattern:')
for i in range(1, 16):
highest_pow = 1 << (i.bit_length() - 1)
if highest_pow < i:
prev_i = i - highest_pow
print(f'bits[{i}] = bits[{prev_i}] + 1 = {bits[prev_i]} + 1 = {bits[i]}')Объединяем все три подхода: комплексное упражнение
Многие задачи на собеседованиях объединяют подсчёт битов, логику поиска пропущенного числа и разворот битов в одном вопросе. Например, дан массив, элементы которого являются n-битными целыми числами и в котором отсутствует один элемент; требуется найти пропущенное значение. Или дан поток результатов подсчёта битов, по которому нужно восстановить пропущенное целое число. Для решения необходимо распознать, какой вспомогательный приём применить.
Тренируйтесь строить мысленную карту: если в задаче говорится о поиске пропущенных элементов, думайте об XOR или сумме. Если требуется «эффективно считать единичные биты», вспоминайте метод Кернигана или DP. Если требуется «развернуть биты», используйте итеративный подход или подход «разделяй и властвуй». Это три основных инструмента работы с битами на собеседованиях.
# Integrated exercise: given bit-count array, find the missing number
# arr[i] = number of 1 bits in i, for all i in 0..n except one
# Reconstruct the missing number
def find_missing_from_bit_counts(bit_counts, n):
# Rebuild full count array
full = [bin(i).count('1') for i in range(n + 1)]
# Find which index is missing by comparing
for i, count in enumerate(bit_counts):
if full[i] != count:
return i - 1 # the entry before the mismatch is missing
return n # last element missing
# Simpler: use XOR on indices matching bit counts
# (This is simplified for illustration)
bits = [0,1,1,2,1,2,2,3,0,1] # bit counts for 0..9 with 8 missing
# Normal: [0,1,1,2,1,2,2,3,1,2]
# Missing is index 8
full = [bin(i).count('1') for i in range(10)]
missing_idx = None
for i in range(10):
if i >= len(bits) or bits[i] != full[i]:
missing_idx = i
break
print(f'Missing number: {missing_idx}')Кэширование битов для их разворота
При повторных вызовах разворота битов, например при моделировании аппаратуры, кэшируйте результаты для 8-битных фрагментов. Поскольку каждый байт может принимать только 256 значений, заранее вычислите развёрнутый байт для каждого значения от 0 до 255. Чтобы развернуть 32-битное целое число, разделите его на четыре 8-битных фрагмента, разверните каждый и соберите их обратно в обратном порядке.
Это сводит каждый вызов к четырём обращениям к таблице и битовым операциям — намного быстрее, чем цикл из 32 итераций при пакетной обработке. Кэш создаётся один раз за O(256 × 8) времени и затем повторно используется для всех вызовов за O(1).
# Build 8-bit reverse cache
def build_reverse_byte_cache():
cache = [0] * 256
for i in range(256):
n, result = i, 0
for _ in range(8):
result = (result << 1) | (n & 1)
n >>= 1
cache[i] = result
return cache
cache = build_reverse_byte_cache()
def reverse_bits_cached(n):
return (cache[n & 0xFF] << 24 |
cache[(n >> 8) & 0xFF] << 16 |
cache[(n >> 16) & 0xFF] << 8 |
cache[(n >> 24) & 0xFF])
# Test
for test in [0b10110100, 0b11111111, 0x12345678]:
cached = reverse_bits_cached(test)
# Reference: iterative
n, result = test, 0
for _ in range(32): result = (result << 1) | (n & 1); n >>= 1
assert cached == result
print(f'{test:#010x} => {cached:#010x}')Быстрая проверка
Проверьте своё понимание концепций «Структуры данных и алгоритмы — подготовка к собеседованию по программированию» из этого урока.
Итоги урока
В этом уроке Вы узнали: подсчёт битов использует DP с формулой dp[i] = dp[i >> 1] + (i & 1) или dp[i] = dp[i & (i-1)] + 1, что даёт время O(n), пропущенное число находится за O(n)/O(1) с помощью применения XOR ко всем индексам и значениям или арифметической формулы суммы, а также разворот 32 битов выполняется итеративно за O(32) или с помощью техники масок «разделяй и властвуй». Далее мы рассмотрим монотонные стеки, начав с инварианта возрастания и убывания и запросов следующего большего элемента.
Часто задаваемые вопросы
Урок «Подсчёт битов, пропущенное число и разворот битов» бесплатный?
Да — полный текст урока «Подсчёт битов, пропущенное число и разворот битов» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «Подсчёт битов, пропущенное число и разворот битов»?
Вычислите количество битов для чисел от 0 до n с помощью DP и приёма с младшим установленным битом, найдите пропущенное число через XOR и разверните биты 32-битного целого числа Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Coding Interview Prep?
Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 4 из 4.
Сколько времени занимает урок «Подсчёт битов, пропущенное число и разворот битов»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Coding Interview Prep?
Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Побитовые операторы: AND, OR, XOR, NOT и сдвиги
- Единственное число и свойства XOR
- Битовые маски: установить, очистить, инвертировать и проверить
- Подсчёт битов, пропущенное число и разворот битов