Padrão 5: Técnicas com bits

Para fechar o módulo de bits, três técnicas que combinam o que você aprendeu com outras ideias: reaproveitar contagens (counting bits), inverter bits e somar sem o operador +.

Tentou? Contar os bits de cada número separadamente funciona, mas é O(n · largura). A teoria abaixo mostra como reusar respostas já calculadas e cair para O(n) — é DP encontrando bits.

Técnica 1 — Counting Bits (reaproveitar respostas)

"Para cada i de 0 a n, quantos bits 1 ele tem?" Calcular cada um do zero desperdiça: números próximos compartilham bits. A sacada (programação dinâmica, que você verá a fundo na última seção):

O número i tem os mesmos bits de i >> 1 (ele sem o último bit), mais o último bit (i & 1).

Ou seja, ans[i] = ans[i >> 1] + (i & 1). Como i >> 1 < i, a resposta menor já foi calculada — é só reusar. Pense em i = 13 (1101): tirando o último bit vira 110 (que é 6), e 6 tem 2 bits; somando o último bit (1), dá 3.

Por que O(n)? São n números e cada resposta sai em O(1) (um shift, um AND, uma soma — tudo reusando algo já pronto). Contar bit a bit cada número seria O(n · largura); reaproveitar derruba para O(n).

Técnica 2 — Reverse Bits (inverter a ordem dos bits)

"Inverta os 32 bits de um número." A ideia: construa o resultado bit a bit — puxe o último bit de n e empurre-o para dentro de res, que vai sendo deslocado para a esquerda. Depois de 32 vezes, res é o espelho de n.

Detalhe importante em JavaScript: use >>> (shift sem sinal) e >>> 0 no final, porque os operadores de bit do JS trabalham em 32 bits com sinal — sem isso, o bit mais alto seria lido como negativo.

Técnica 3 — Sum of Two Integers (somar sem +)

"Some a e b sem usar + ou -." Parece impossível, mas a adição binária é feita de bits:

• a ^ b soma os bits ignorando o vai-um (carry).
• (a & b) << 1 é exatamente o vai-um: onde os dois bits são 1, sobe um para a casa seguinte.

Repita "soma sem carry, depois adiciona o carry" até não sobrar carry — igual à conta de somar na mão, só que em binário.

Repare na diferença entre as linguagens: o JS opera nativamente em 32 bits com sinal, então a soma "simplesmente funciona". Python tem inteiros de tamanho ilimitado, então precisamos mascarar para 32 bits (& 0xFFFFFFFF) e reconstruir o sinal no final — senão o vai-um nunca acabaria para números negativos. É um ótimo lembrete de que "o mesmo algoritmo" pode exigir cuidados diferentes conforme como a linguagem representa os números.

Resumo

• Counting Bits: ans[i] = ans[i>>1] + (i&1), reaproveitando respostas → O(n).
• Reverse Bits: construa o espelho bit a bit; em JS, cuidado com 32 bits com sinal (>>>, >>> 0).
• Sum without +: a^b soma sem carry, (a&b)<<1 é o carry; repita. Em Python, mascare para 32 bits.
• O mesmo algoritmo de bits pode exigir cuidados diferentes por linguagem.

Última parada: a síntese da seção Binary e o quiz antes da prova.