Conte Bits e o Bit Definido Mais Baixo
Use popcount e o truque n & -n.
Conte Bits e o Bit Definido Mais Baixo é uma aula grátis de Competitive Programming Academy no CoddyKit. Esta é a aula 3 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 Competitive Programming Academy, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Competitive Programming Academy inclui 4 aulas no total.
Contando os bits 1
Muitos problemas perguntam quantos bits estão definidos em um número, o que é chamado de contagem de bits 1. Isso aparece em tamanhos de subconjuntos, verificações de paridade e pontuação. 🔢
A contagem integrada do Python
A forma mais rápida de contar bits definidos é usar o método de inteiros bit_count(). Sem laços e sem complicação: apenas a quantidade de bits 1.
print((13).bit_count()) # 0b1101 has 3 onesContar convertendo para binário
Se você esquecer bit_count, converta o número em texto binário e conte os bits 1. É mais lento, mas claro e fácil de lembrar.
print(bin(13).count('1')) # 3O bit definido mais baixo
O bit definido mais baixo é o 1 mais à direita em um número. Isolá-lo é uma técnica fundamental para árvores de Fenwick e truques com subconjuntos mais adiante.
Isole-o com n e -n
O truque famoso n & -n mantém apenas o bit definido mais baixo. Os números negativos em complemento de dois fazem isso funcionar como mágica.
n = 12 # 0b1100
print(n & -n) # 4 = 0b100Por que n e -n funcionam
Negar inverte todos os bits e adiciona 1, portanto tudo abaixo do 1 mais baixo é invertido. Aplicar AND deixa apenas esse bit isolado.
Remover o bit definido mais baixo
Subtrair 1 faz um empréstimo através dos zeros finais, portanto n & (n - 1) apaga o bit definido mais baixo. Repita a operação para remover os bits 1 um a um.
n = 12 # 0b1100
print(n & (n - 1)) # 8 = 0b1000A contagem de Brian Kernighan
Repita enquanto o número for diferente de zero, limpando o bit mais baixo a cada vez. O laço é executado uma vez por bit definido, sendo rápido quando há poucos bits 1.
c = 0
while n:
n &= n - 1
c += 1Verificar se é uma potência de dois
Uma potência de dois positiva tem exatamente um bit definido, portanto n & (n - 1) é igual a 0. Uma operação AND permite verificar isso instantaneamente.
def is_pow2(n):
return n > 0 and (n & (n - 1)) == 0Paridade a partir da contagem de bits
A paridade de um número é simplesmente sua contagem de bits 1 módulo 2. Ela responde, em uma única etapa, às perguntas sobre uma quantidade ímpar ou par de bits 1.
parity = (13).bit_count() & 1 # 1Escolha a ferramenta mais rápida
Para obter a máxima velocidade, use bit_count; para percorrer os bits definidos, use o laço n & (n-1). Escolher a ferramenta certa ajuda a respeitar limites de tempo rigorosos. ⚡
Verificação rápida
Teste o truque do bit definido mais baixo.
Recapitulação: contando bits
Você pode contar bits 1 com bit_count, isolar o bit mais baixo usando n & -n e removê-lo com n & (n-1). São expressões curtas e poderosas. 🎉
Perguntas Frequentes
A aula “Conte Bits e o Bit Definido Mais Baixo” é grátis?
Sim — o texto completo de “Conte Bits e o Bit Definido Mais Baixo” é 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 Competitive Programming Academy, atualize para CoddyKit PRO. O curso de Competitive Programming Academy inclui 4 aulas no total.
O que vou aprender em “Conte Bits e o Bit Definido Mais Baixo”?
Use popcount e o truque n & -n. Você pratica Competitive Programming Academy 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 Competitive Programming Academy?
Nenhuma experiência prévia é necessária. Competitive Programming Academy 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 3 de 4.
Quanto tempo leva a aula “Conte Bits e o Bit Definido Mais Baixo”?
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 Competitive Programming Academy?
Sim. Cada aula de Competitive Programming Academy 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
- AND, OR, XOR e Deslocamentos
- Defina, Limpe e Alterne um Bit
- Conte Bits e o Bit Definido Mais Baixo
- Máscaras de Bits como Pequenos Conjuntos