Posterior a de una larga selección de datos resolvimos este conflicto que presentan algunos de nuestros usuarios. Te regalamos la respuesta y esperamos servirte de mucha ayuda.
Solución:
Entonces sí, es un poco difícil y necesita dibujarse en papel. Una vez que tienes la idea es simple. Comenzaré con explicaciones en inglés y luego un ejemplo simple. Lo más importante es liberar su mente del hecho de que estamos analizando dos números y pensar en los números intermedios.
Primero, digamos algunas reglas: 1) Si dos números son iguales, no habrá ningún número entre ellos. 2) Si dos números no son iguales, el número consecutivo entre ellos contendrá CERO en cada dígito, por lo que su AND bit a bit será CERO.
Antes de entrar en el ejemplo, debemos explicar el algoritmo simple anterior.
1) Cada división por dos medios quita un dígito binario de la derecha de los números. (Así es como la división por dos medios en binario). 2) Cada vez que dividimos, duplicamos la variable de paso. Simple, la variable de paso es más como un contador que contiene el valor del dígito superior justo antes de que los dos números se igualen.
Supongamos que tenemos el siguiente ejemplo:
L : 11110001 D : 11110011
S=1 (00000001 en binario)
Aplicando su algoritmo en estos valores:
Dado que L y R aún no son iguales, corte un solo dígito binario de cada uno (divida cada uno por 2) y multiplique S por 2; En la primera ronda se convierten
L : 1111000 D : 1111001
S=2 (00000010 en binario)
Como todavía no son iguales, hazlo de nuevo y el resultado es:
L : 111100 D : 111100
Ahora son iguales, el bucle se rompe y el resultado
es el número de la izquierda (o la derecha ya que son iguales) * valor S.
Cuando multiplicamos en binario, agregamos un cero a la derecha. Aquí necesitamos 3 ceros ya que S es 00000010
11110000 que es como se esperaba.
Conclusión: Sigue cortando dividiendo hasta que ambos sean iguales y no quede nada entre ellos. Mientras haces eso, sigue actualizando en qué paso te encuentras 🙂
Primero pensemos qué hace AND bit a bit con dos números, por ejemplo (0b significa base 2)
4 & 7 = 0b100 & 0b111 = 0b100
5 & 7 = 0b101 & 0b111 = 0b101
5 & 6 = 0b101 & 0b110 = 0b100
El operador & mantiene los bits establecidos en ambos números.
Para varios números, el operador & mantiene esos bits, que es 1 en cada número.
En otras palabras, un bit es 0 en cualquier número dará como resultado 0 en el bit correspondiente de la respuesta.
Ahora considere un rango
[m = 0bxyz0acd, n=0bxyz1rst]
aquí xyzpacdrst todos son dígitos en base 2.
Podemos encontrar dos números que son especiales en el rango [m, n]
(1) m’ = 0bxyz0111 (2) n’ = 0bxyz1000 El AND bit a bit de todos los números en el rango [m, n] es solo el AND bit a bit de los dos números especiales
rangeBitwiseAnd(m, n) = m’ & n’ = 0bxyz0000 Esto nos dice que el bit a bit y del rango mantiene los bits comunes de m y n de izquierda a derecha hasta el primer bit que son diferentes, rellenando ceros para el descansar.
Finalizando este artículo puedes encontrar las anotaciones de otros programadores, tú de igual manera puedes insertar el tuyo si lo deseas.