Padrão 3: Fundamentos de bits
Começa o segundo módulo da seção. Aqui paramos de pensar em números como quantidades e passamos a vê-los como o que são por dentro: sequências de bits (0s e 1s). Operar nesses bits resolve certos problemas com elegância imbatível.
Tente primeiro: Number of 1 Bits
Antes de ler a teoria, tente resolver. Pode começar pela força bruta, pode errar — a ideia é sentir o problema. A teoria vem logo abaixo.
Dado um inteiro não-negativo n, conte quantos bits 1 há na sua representação binária (o "peso de Hamming").
Exemplo: n = 11 (binário 1011) → 3. n = 128 (binário 10000000) → 1.
Tentou? Você pode ter convertido o número para uma string binária e contado os '1' — funciona! A teoria abaixo mostra como fazer isso operando direto nos bits, e apresenta um truque que vale ouro:
n & (n-1).
A teoria: pensando em binário
Um número inteiro é guardado como bits. 13 é 1101 em binário:
8 + 4 + 0 + 1. Cada posição é uma potência de 2. As operações bit a bit
trabalham em todas as posições ao mesmo tempo:
| Operador | Nome | Faz | Exemplo (4 bits) |
|---|---|---|---|
a & b | AND | 1 só onde ambos são 1 | 1100 & 1010 = 1000 |
a | b | OR | 1 onde algum é 1 | 1100 | 1010 = 1110 |
a ^ b | XOR | 1 onde são diferentes | 1100 ^ 1010 = 0110 |
~a | NOT | inverte todos os bits | ~1100 = ...0011 |
a << k | shift esq. | empurra k casas (× 2ᵏ) | 0011 << 1 = 0110 |
a >> k | shift dir. | puxa k casas (÷ 2ᵏ) | 0110 >> 1 = 0011 |
Veja na prática (edite e experimente outros valores):
Os três truques que você mais vai usar
A partir dos operadores, nascem padrões prontos:
| Quero... | Faço | Por quê |
|---|---|---|
| testar o último bit | n & 1 | isola o bit 0; dá 1 se ímpar |
| olhar o bit i | (n >> i) & 1 | traz o bit i para a posição 0 |
| ligar o bit i | n | (1 << i) | OR com uma máscara de um bit |
| apagar o bit 1 mais à direita | n & (n - 1) | a estrela desta aula 👇 |
Exemplo — Number of 1 Bits (com o truque n & (n-1))
"Quantos bits 1 há em n?" A solução direta: olhar bit a bit (n & 1,
depois n >>= 1), 32 vezes — O(número de bits). Funciona. Mas há algo mais
esperto.
O truque: n & (n - 1) apaga exatamente o bit 1 mais à direita de n.
Por quê? Subtrair 1 vira aquele bit em 0 e todos os 0s à direita dele em 1; o
AND com n zera justamente aquele bit (e mantém o resto). Então cada
n = n & (n-1) remove um bit 1 — basta contar quantas vezes até n zerar.
Observe os bits de n sumindo um a um:
Por que isso é eficiente?
A versão bit-a-bit faz sempre 32 passos (a largura do inteiro). A versão
n & (n-1) faz exatamente tantos passos quantos bits 1 existem — se n
tem só 3 bits ligados, são 3 iterações, não 32. Em ambos os casos é O(largura
do inteiro) = O(1) para inteiros de tamanho fixo, mas o truque costuma fazer
bem menos trabalho. Espaço O(1).
🧠 Quiz de fixação
0/41. Qual operador resulta em 1 apenas nas posições onde os dois bits são diferentes?
2. Como você testa se o último bit de n está ligado (n é ímpar)?
3. O que n & (n - 1) faz com n?
4. Contar bits 1 com n & (n-1) faz quantas iterações para n = 11 (binário 1011)?
Resumo
- Números são bits;
& | ^ ~ << >>operam em todas as posições de uma vez. - Truques essenciais:
n & 1(testar último bit),(n>>i)&1(olhar bit i),n | (1<<i)(ligar bit i),n & (n-1)(apagar o bit 1 mais à direita). - Contar bits 1 com
n & (n-1)faz só tantos passos quantos bits ligados.
Próxima aula: o operador que merece uma aula só pra ele — XOR.