Cantidad de bits distintos
La misión
Problema
Escribe dos enteros no negativos en binario, uno encima del otro y alineados a la derecha. Cuenta las posiciones en las que sus dígitos binarios no coinciden. Los dígitos que faltan a la izquierda del número más corto cuentan como ceros.
Ejemplos
Input: a = 1, b = 4
Output: 2
Por qué: 001 frente a 100 difiere en la primera y en la última posición
Input: a = 7, b = 10
Output: 3
Por qué: 0111 frente a 1010 difiere en todas partes excepto en la segunda posición desde la derecha
Input: a = 5, b = 5
Output: 0
Por qué: caso límite: un número nunca difiere de sí mismo
Pistas
0 / 3
Comparar los dos números dígito por dígito funciona, pero una sola operación a nivel de bits puede hacer todas las comparaciones a la vez.
Hay un operador que produce un 1 justo donde dos dígitos difieren y un 0 donde coinciden. Después de aplicarlo, la pregunta se convierte en una de conteo.
Aplica XOR a los dos números y luego cuenta los unos del resultado. Una forma rápida de contarlos es borrar repetidamente el uno más bajo haciendo AND del valor con él mismo menos uno, y sumar uno a un contador cada vez hasta que el valor llegue a cero.
- Tiempo objetivo
- O(log max(a, b))
- Espacio objetivo
- O(1)
Restricciones
- a and b are non-negative integers
Solución
XOR enciende un bit justo donde sus entradas no coinciden, así que la respuesta es simplemente la cantidad de unos en a XOR b. Contarlos con el truco de borrar el uno más bajo cuesta una vuelta del bucle por cada uno y no por cada dígito, porque restar uno invierte el uno más bajo y todo lo que está debajo de él, y luego el AND borra ese uno. Por lo tanto, el bucle se ejecuta tantas veces como vale la respuesta. El tiempo es O(cantidad de bits distintos), como máximo O(log de la entrada mayor), y el espacio es 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)) # -> 0¿Lo que te frena es la idea y no el código? Contar bits encendidos lo explica.