Contagem de bits diferentes
A missão
Problema
Escreva dois números inteiros não negativos em binário, um acima do outro e alinhados à direita. Conte as posições em que os seus dígitos binários divergem. Dígitos que faltam à esquerda do número mais curto contam como zeros.
Exemplos
Input: a = 1, b = 4
Output: 2
Por quê: 001 contra 100 diverge na primeira e na última posição
Input: a = 7, b = 10
Output: 3
Por quê: 0111 contra 1010 diverge em todas as posições, exceto na segunda a partir da direita
Input: a = 5, b = 5
Output: 0
Por quê: edge case: um número nunca diverge de si mesmo
Dicas
0 / 3
Comparar os dois números dígito a dígito funciona, mas uma única operação bit a bit consegue fazer todas as comparações de uma vez.
Existe um operador que produz 1 exatamente onde dois dígitos diferem e 0 onde eles coincidem. Depois de aplicá-lo, a pergunta vira um problema de contagem.
Faça o XOR dos dois números e depois conte os 1s do resultado. Um jeito rápido de contar é zerar repetidamente o 1 mais baixo fazendo o AND do valor com ele mesmo menos um, somando um a um contador a cada vez, até o valor chegar a zero.
- Tempo-alvo
- O(log max(a, b))
- Espaço-alvo
- O(1)
Restrições
- a and b are non-negative integers
Solução
O XOR liga um bit exatamente onde as entradas divergem, então a resposta é simplesmente o número de 1s em a XOR b. Contá-los com o truque de zerar o 1 mais baixo custa uma volta do loop por 1, e não por dígito, porque subtrair um inverte o 1 mais baixo e tudo abaixo dele, e o AND então apaga esse 1. Assim, o loop roda tantas vezes quanto o valor da resposta. O tempo é O(número de bits diferentes), no máximo O(log da maior entrada), e o espaço é O(1).
def differing_bits(a, b):
x = a ^ b # a 1 wherever the two numbers disagree
count = 0
while x:
x &= x - 1 # clear the lowest remaining 1
count += 1
return count
print(differing_bits(1, 4)) # -> 2
print(differing_bits(7, 10)) # -> 3
print(differing_bits(5, 5)) # -> 0Travou na ideia, e não no código? Contando bits ligados explica isso.