Supongamos que tengo una mano de 8 cartas:
7 8 9 10 J Q K A
¿Cómo podemos revertir? Una manera es cambiar pares adyacentes:
8 7 10 9 Q J A K
grupos Entonces, intercambio adyacentes de 2: intercambio 8 7 y 10 9, etc:
10 9 8 7 A K Q J
Finalmente, grupos de intercambio de cuatro, que es la mitad de la tamaño de 8:
A K Q J 10 9 8 7
Listo.
Puede hacer esto en diferentes órdenes. ¿Por qué? Porque los intercambios son estables entre sí. Cuando intercambiamos la mitad superior de las tarjetas con la mitad inferior, por ejemplo, las parejas permanecen en el mismo orden. O cuando intercambiamos pares, las mitades permanecen en el mismo orden.
Esto es lo que el código está haciendo con las operaciones de bits. Por ejemplo para intercambiar pares podemos usar la máscara 01010101 de seleccionar los bits pares, y 10101010 de seleccionar los bits impares, utilizando el bit a bit y funcionamiento:
ABCDEFGH ABCDEFGH
& 01010101 & 10101010
---------- ----------
= 0B0D0F0H A0C0E0G0
Recuerde, la regla para y es la que da cierta valor de bit X, X & 1 = X y X & 0 = 0. Los 1 bits en la máscara conservan el valor, y los 0 bits en la máscara producen 0. Esto se denomina enmascaramiento porque se ve exactamente como una máscara utilizada en aerosol -pintura, etc. Los 1 bits "cubren" los lugares que no desea "pintar" con cero.
A continuación, el resultado de la izquierda se desplaza un bit a la izquierda y el resultado de la derecha se desplaza a la derecha.Esto provoca el cambio:
B0D0F0H0 0A0C0E0G
Finalmente, los dos se combinan con OR lógico. La regla para O es que X o 0 es X. Las dos partes tienen cada uno 0, donde el otro tiene distinto de cero, y así los bits simplemente Merge:
B0D0F0H0
| 0A0C0E0G
----------
= BADCFEHG
Y ahora se intercambian los pares.
de intercambio, cuartos de intercambio, ochos de intercambio ... –
@pst por favor explique más – Eight
¿Por qué no trabajar hacia fuera con lápiz y papel? Usa un número de 8 bits y solo sube a 0x0F/0xF0. – Kaz