Contagem de bits, número ausente e inversão de bits
Calcule as contagens de bits para 0..n usando DP e o truque do bit definido menos significativo, encontre um número ausente por meio de XOR e inverta os bits de um inteiro de 32 bits.
Contagem de bits, número ausente e inversão de bits é uma aula grátis de Coding Interview Prep no CoddyKit. Esta é a aula 4 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Coding Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Coding Interview Prep inclui 4 aulas no total.
Visão Geral do Problema de Contagem de Bits
O problema de Contagem de Bits (LeetCode 338) solicita: dado n, retorne uma matriz ans de tamanho n+1, na qual ans[i] é a quantidade de bits 1 em i. A abordagem ingênua tem complexidade O(n log n) — conte os bits de cada número individualmente. A abordagem com DP tem complexidade O(n), aproveitando a relação entre i e sua metade ou seu bit 1 menos significativo.
Duas observações importantes fundamentam a DP: (1) i >> 1 remove o bit menos significativo, portanto bits[i] = bits[i >> 1] + (i & 1). (2) Limpar o bit 1 menos significativo: bits[i] = bits[i & (i-1)] + 1. Ambas oferecem tempo O(n) e espaço O(n), usado pela matriz de saída.
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))Por Que as Relações de Recorrência da DP Funcionam
Para a relação de recorrência com deslocamento à direita dp[i] = dp[i >> 1] + (i & 1): dividir por 2, ou deslocar à direita, remove o último bit. Se o último bit era 1, a contagem aumenta em 1; se era 0, não há alteração. Portanto, bits[i] = bits[i // 2] + (i mod 2).
Para a relação de recorrência do bit 1 menos significativo dp[i] = dp[i & (i-1)] + 1: i & (i-1) limpa o bit 1 mais à direita, portanto tem um bit definido a menos que i. A contagem é, consequentemente, a contagem desse valor reduzido mais 1. Ambas as relações de recorrência processam i em ordem crescente, de modo que os subproblemas menores sempre sejam resolvidos primeiro.
# 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)Número Ausente: Abordagens com XOR e Soma
O problema do Número Ausente (LeetCode 268) fornece uma matriz com n números distintos no intervalo [0, n], com exatamente um número ausente. A abordagem com XOR: aplique XOR a todos os índices de 0 a n e a todos os valores da matriz. Os pares se cancelam, restando the número ausente. A abordagem com soma: expected = n*(n+1)//2; retorne expected - sum(nums).
Ambas têm tempo O(n) e espaço O(1). A abordagem com XOR é mais robusta em linguagens com inteiros de largura fixa, pois evita um possível estouro. Em Python, ambas funcionam bem, já que os inteiros têm precisão arbitrária.
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)}')Inversão de Bits de um Inteiro de 32 Bits
O problema de Inversão de Bits (LeetCode 190) solicita que você inverta a representação binária de um inteiro sem sinal de 32 bits. A abordagem iterativa: processe cada um dos 32 bits, da direita para a esquerda na entrada, colocando-os da esquerda para a direita na saída. A cada iteração, extraia o bit mais à direita com n & 1, desloque a saída para a esquerda para abrir espaço, aplique OR ao bit e depois desloque n para a direita.
Após 32 iterações, o inteiro de saída contém the 32 bits de n na ordem invertida. Isso resulta em O(32) = O(1) por chamada, ou O(1) amortizado com armazenamento em cache para chamadas repetidas usando blocos de 8 bits.
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)) # 1Inversão de Bits: Divisão e Conquista
Uma abordagem mais rápida, O(log 32) = O(1), inverte bits usando uma troca por divisão e conquista. Primeiro, troque bits adjacentes; depois, grupos adjacentes de 2 bits; em seguida, grupos de 4 bits; e assim por diante. Cada nível de trocas usa máscaras para separar grupos alternados e deslocamentos para entrelaçá-los. Após 5 trocas, todos os 32 bits são invertidos.
Essa abordagem usa O(1) operações fixas, independentemente da entrada, e é usada em implementações de componentes físicos. As máscaras são constantes: 0x55555555 (padrão alternado 01), 0x33333333 (padrão alternado 0011), 0x0f0f0f0f (padrão alternado 00001111) e assim por diante.
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}')Número de Bits 1 (Peso de Hamming)
O problema do Número de Bits 1 (LeetCode 191) solicita o peso de Hamming, ou contagem de bits 1, de um inteiro sem sinal. Há três abordagens, com diferentes compromissos: laço ingênuo (O(32)), Brian Kernighan (O(k), em que k = bits definidos) e o recurso integrado do Python n.bit_count() (3.10 ou posterior).
O método de Brian Kernighan é preferido em entrevistas porque demonstra a compreensão da técnica n & (n-1). Cada iteração remove o bit 1 menos significativo, portanto o laço executa exatamente tantas vezes quantos forem os bits 1 — muito mais rápido que uma varredura completa de 32 bits para inteiros esparsos.
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}')Soma de Bits Consecutivos: Abordagem com Prefixos
Às vezes, você precisa contar bits 1 rapidamente em um intervalo [l, r]. Construa uma soma de prefixos dos bits definidos para 0..n: prefix[i] = prefix[i-1] + bin(i).count('1'). Então, a contagem para o intervalo [l, r] é prefix[r] - prefix[l-1]. Isso permite consultas de intervalo em O(1) após um pré-processamento de O(n).
Essa técnica se generaliza para qualquer agregado baseado em bits sobre um intervalo. Por exemplo, para contar números em [l, r] com uma quantidade par de bits definidos, use the mesma técnica de prefixos, mas com uma função de acumulação diferente.
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)}')Inversão de Bits para Números Negativos
Em Python, os inteiros têm sinal e largura arbitrária. Ao inverter bits para o problema do LeetCode, precisamos tratar a entrada como um inteiro sem sinal de 32 bits. Aplique a máscara & 0xFFFFFFFF à entrada antes do processamento para garantir que apenas 32 bits sejam considerados. A saída também deve ser um inteiro sem sinal de 32 bits, isto é, não negativo.
Se você receber um inteiro Python que possa ser negativo, no sentido de complemento de dois, aplique primeiro & 0xFFFFFFFF para obter a representação sem sinal de 32 bits e depois inverta-a. O resultado é sempre um inteiro não negativo entre 0 e 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 de Manipulação de Bits: Padrões de Contagem de Bits
O problema de contagem de bits revela um padrão geral para DP de bits: se você conhece a resposta para uma versão menor de i, pode calculá-la para i usando uma operação de bits de tempo constante. Esse padrão se generaliza para outros problemas de contagem de bits, como contar números com exatamente k bits definidos em [0, n], usando enumeração binária, ou encontrar a maior potência de dois que divide cada número.
Outra observação útil: a contagem de bits definidos de i segue um padrão repetitivo dentro de cada intervalo de potência de dois. O padrão para [2^k, 2^(k+1) - 1] é the mesmo que para [0, 2^k - 1], com cada valor incrementado em 1, porque o bit k está sempre definido nesse intervalo.
# 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]}')Combinando os Três: um Exercício Integrado
Muitos problemas de entrevistas combinam contagem de bits, lógica de números ausentes e inversão de bits em uma única questão. Por exemplo: dada uma matriz cujos elementos são inteiros de n bits e na qual um elemento está ausente, encontre o valor ausente. Ou: dado um fluxo de contagens de bits, reconstrua o inteiro ausente. Esses problemas exigem reconhecer qual subtécnica se aplica.
Pratique a construção de um mapa mental: se um problema mencionar a busca por elementos ausentes, pense em XOR ou soma. Se disser ‘conte bits 1 com eficiência’, pense em Kernighan ou DP. Se disser ‘inverta bits’, pense em uma abordagem iterativa ou de divisão e conquista. Essas são as três ferramentas centrais da manipulação de bits em entrevistas.
# 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}')Armazenamento em Cache para Inversão de Bits
Para chamadas repetidas de inversão de bits, por exemplo, em uma simulação de componentes físicos, armazene em cache os resultados para blocos de 8 bits. Como cada byte pode assumir apenas 256 valores, pré-calcule o byte invertido para cada valor de 0 a 255. Para inverter um inteiro de 32 bits, divida-o em quatro blocos de 8 bits, inverta cada um e remonte-os na ordem inversa.
Isso reduz cada chamada a quatro consultas à tabela e operações de bits — muito mais rápido que um laço de 32 iterações para processamento em lote. O cache é construído uma vez em tempo O(256 × 8) e reutilizado em todas as chamadas posteriores em 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}')Verificação rápida
Teste sua compreensão dos conceitos de Estruturas de Dados e Algoritmos — Preparação para Entrevistas de Programação desta lição.
Resumo da Lição
Nesta lição, você aprendeu: a contagem de bits usa DP com dp[i] = dp[i >> 1] + (i & 1) ou dp[i] = dp[i & (i-1)] + 1, com tempo O(n); o número ausente é resolvido em O(n)/O(1) aplicando XOR a todos os índices e valores ou usando a fórmula da soma aritmética; e a inversão de 32 bits é feita iterativamente em O(32) ou com the técnica de máscara de divisão e conquista. A seguir, exploraremos pilhas monotônicas, começando pelo invariante crescente versus decrescente e pelas consultas do próximo elemento maior.
Perguntas Frequentes
A aula “Contagem de bits, número ausente e inversão de bits” é grátis?
Sim — o texto completo de “Contagem de bits, número ausente e inversão de bits” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Coding Interview Prep, atualize para CoddyKit PRO. O curso de Coding Interview Prep inclui 4 aulas no total.
O que vou aprender em “Contagem de bits, número ausente e inversão de bits”?
Calcule as contagens de bits para 0..n usando DP e o truque do bit definido menos significativo, encontre um número ausente por meio de XOR e inverta os bits de um inteiro de 32 bits. Você pratica Coding Interview Prep com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar Coding Interview Prep?
Nenhuma experiência prévia é necessária. Coding Interview Prep no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 4 de 4.
Quanto tempo leva a aula “Contagem de bits, número ausente e inversão de bits”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de Coding Interview Prep?
Sim. Cada aula de Coding Interview Prep inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- Operadores bit a bit: AND, OR, XOR, NOT e deslocamentos
- Número único e propriedades de XOR
- Máscaras de bits: definir, limpar, alternar e verificar
- Contagem de bits, número ausente e inversão de bits