¿Cómo funciona (i << 48) | ((i & 0xffff0000L) << 16) | ((i > >> 16) & 0xffff0000L) | (i >>> 48) trabajo?

Question

Aquí es la implementación de marcha atrás en Long:

public static long reverse(long i) { 
     // HD, Figure 7-1 
    i = (i & 0x5555555555555555L) << 1 | (i >>> 1) & 0x5555555555555555L;//1 
    i = (i & 0x3333333333333333L) << 2 | (i >>> 2) & 0x3333333333333333L;//2 
    i = (i & 0x0f0f0f0f0f0f0f0fL) << 4 | (i >>> 4) & 0x0f0f0f0f0f0f0f0fL;//3 
    i = (i & 0x00ff00ff00ff00ffL) << 8 | (i >>> 8) & 0x00ff00ff00ff00ffL;//4 
    i = (i << 48) | ((i & 0xffff0000L) << 16) | 
     ((i >>> 16) & 0xffff0000L) | (i >>> 48);//5 
    return i; 
} 

puedo entender línea de 1,2,3,4, pero no 5! ¿Como funciona?

Agrupo los 64 bits a 8 grupos, es decir, 1 son los primeros 8 bits, 2 son los segundos 8 bits, y así sucesivamente.

Luego, después de la línea 4, la secuencia como 4,3,2,1,8,7,6,5

y creo que la línea 5 que trabaja como abajo antes de la operación |:

6,5,0,0,0,0,0,0-->(i << 48) 
8,7,0,0,0,0,0,0-->((i & 0xffff0000L) << 16) 
0,0,0,0,4,3,2,1-->((i >>> 16) & 0xffff0000L) 
0,0,0,0,0,0,2,1-->(i >>> 48) 

Pero, no sé donde la dosis mal o si ¡está mal! ¡Pensando en eso casi todo un día!

¡Alguien me puede ayudar! Gracias.

oh, he cometido un error como este:

6,5,0,0,0,0,0,0-->(i << 48) 
0,0,8,7,0,0,0,0-->((i & 0xffff0000L) << 16) 
0,0,0,0,2,1,0,0-->((i >>> 16) & 0xffff0000L) 
0,0,0,0,0,0,4,3-->(i >>> 48) 

pero yo creo que es Alše mal! creo que la secuencia correcta es 8,7,6,5,4,3,2,1

lamento mucho que cometa algunos errores. funciona derecha como a continuación:

después de la línea 4, el patrón correcto es: 2,1,4,3,6,5,8,7

8,7,0,0,0,0,0,0-->(i << 48) 
0,0,6,5,0,0,0,0-->((i & 0xffff0000L) << 16) 
0,0,0,0,4,3,0,0-->((i >>> 16) & 0xffff0000L) 
0,0,0,0,0,0,2,1-->(i >>> 48) 

Answer 1

Line 1 swaps simples bits adyacentes en pares (0 <-> 1; 2 <-> 3; etc.) Las líneas 2 a 4 intercambian secuencias adyacentes de dos bits, 4 bits y 8 bits. En ese punto, el valor original se ha transformado en cuatro bloques de 16 bits con cada bloque al revés de lo que había sido al principio. La línea 5 luego reorganiza los 4 bloques. Básicamente, la línea 5 combina dos pasos en uno: intercambiando dos pares de bloques de 16 bits e intercambiando un par de bloques de 32 bits. La lógica es:

• (i << 48) mueve el bloque de más a la derecha de 16 bits a la posición izquierda, dejando todos los demás bits cero
• ((i & 0xffff0000L) << 16) mueve el segundo bloque de la derecha a ser el segundo bloque de la izquierda (todos los demás bits de cero)
• ((i >>> 16) & 0xffff0000L) mueve el segundo bloque de la izquierda a ser el segundo bloque de la derecha (todos los demás bits cero)
• (i >>> 48) mueve el bloque de más a la izquierda a la posición derecha (todos los demás bits cero)

Entonces estos cuatro valores son |-juntos para producir la inversión final. Si hubiera sido hecho en dos pasos, serían dos declaraciones que se parecen a las primeras cuatro declaraciones, pero con diferentes patrones de máscara.

Creo que después de la línea 4, el patrón es 2,1,4,3,6,5,8,7, no 4,3,2,1,8,7,6,5 como suponía.Las cuatro piezas de la línea 5 son:

8,7,0,0,0,0,0,0-->(i << 48) 
0,0,6,5,0,0,0,0-->((i & 0xffff0000L) << 16) 
0,0,0,0,4,3,0,0-->((i >>> 16) & 0xffff0000L) 
0,0,0,0,0,0,2,1-->(i >>> 48) 

Answer 2

Su intento no es del todo correcto. Aquí está la versión corregida:

2,1,4,3,6,5,8,7 --> i  // Assume this sequence after line 4 
8,7,0,0,0,0,0,0 --> (i << 48) 
0,0,6,5,0,0,0,0 --> ((i & 0xffff0000L) << 16) 
0,0,0,0,4,3,0,0 --> ((i >>> 16) & 0xffff0000L) 
0,0,0,0,0,0,2,1 --> (i >>> 48) 

Aquí está los dos pasos intermedios interrumpidas:

2,1,4,3,6,5,8,7 --> i  // Assume this sequence after line 4 
0,0,0,0,6,5,0,0 --> (i & 0xffff0000L) 
0,0,6,5,0,0,0,0 --> ((i & 0xffff0000L) << 16) 

2,1,4,3,6,5,8,7 --> i  // Assume this sequence after line 4 
0,0,2,1,4,3,6,5 --> (i >>> 16) 
0,0,0,0,4,3,0,0 --> ((i >>> 16) & 0xffff0000L) 

---

Aunque estoy un poco sorprendido de por qué no se lleva a cabo de la siguiente manera:

i = (i & 0x5555555555555555L) << 1 | (i >>> 1) & 0x5555555555555555L; // 1 
i = (i & 0x3333333333333333L) << 2 | (i >>> 2) & 0x3333333333333333L; // 2 
i = (i & 0x0f0f0f0f0f0f0f0fL) << 4 | (i >>> 4) & 0x0f0f0f0f0f0f0f0fL; // 3 
i = (i & 0x00ff00ff00ff00ffL) << 8 | (i >>> 8) & 0x00ff00ff00ff00ffL; // 4 
i = (i & 0x0000ffff0000ffffL) << 16 | (i >>> 16) & 0x0000ffff0000ffffL; // 5 
i = (i & 0x00000000ffffffffL) << 32 | (i >>> 32) & 0x00000000ffffffffL; // 6 

Mantiene el patrón consistente. Y creo que también reduce el número de operaciones.

EDIT: veo por qué se implementa la forma en que lo es. La versión en la pregunta usa solo 9 operaciones para las dos reversiones finales. La versión aquí (líneas 5 y 6) necesita 10 operaciones.

Caray ... hablando de micro-optimización al extremo ...

---

EDIT 2: ¿Por qué no se me había ocurrido esto? ¿Por qué java.lang.Long no usa esto?

i = (i & 0x5555555555555555L) << 1 | (i >>> 1) & 0x5555555555555555L; // 1 
i = (i & 0x3333333333333333L) << 2 | (i >>> 2) & 0x3333333333333333L; // 2 
i = (i & 0x0f0f0f0f0f0f0f0fL) << 4 | (i >>> 4) & 0x0f0f0f0f0f0f0f0fL; // 3 
i = (i & 0x00ff00ff00ff00ffL) << 8 | (i >>> 8) & 0x00ff00ff00ff00ffL; // 4 
i = (i & 0x0000ffff0000ffffL) << 16 | (i >>> 16) & 0x0000ffff0000ffffL; // 5 
i = (i << 32) | (i >>> 32)            // 6