Come funziona (i << 48) | ((i & 0xffff0000L) << 16) | ((i > >> 16) e 0xffff0000L) | (io >>> 48) lavoro?

Question

Qui è l'attuazione di inversione a 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; 
} 

posso capire la linea 1,2,3,4, ma non 5! Come funziona?

I raggruppa i 64 bit in 8 gruppi, ovvero 1 è il primo 8 bit, 2 è il secondo 8 bit e così via.

Poi, dopo la linea 4, la sequenza come 4,3,2,1,8,7,6,5

e penso che la linea 5 a lavorare come di seguito prima dell'operazione |:

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) 

Ma, io non so dove dose di sbagliato o se è sbagliato! Pensaci quasi un giorno intero!

Qualcuno può aiutarmi !! Grazie.

oh, ho fatto un errore come questo:

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) 

ma ho ALSE credo che sia sbagliato! Penso che la sequenza corretta sia 8,7,6,5,4,3,2,1

mi dispiace tanto che faccio degli errori! funziona a destra come sotto:

dopo la linea 4, il modello di destra è: 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

Linea 1 swap adiacenti singoli bit in coppia (0 <-> 1; 2 <-> 3; etc.). Le righe 2-4 scambiano sequenze adiacenti di due bit, 4 bit e 8 bit. A quel punto, il valore originale è stato trasformato in quattro blocchi di 16 bit con ciascun blocco al contrario di quello che era stato all'inizio. La linea 5 poi riorganizza i 4 blocchi. Fondamentalmente, la riga 5 combina due passaggi in uno: scambiando due coppie di blocchi a 16 bit e scambiando una coppia di blocchi a 32 bit. La logica è:

• (i << 48) sposta più a destra blocco 16 bit in posizione sinistra, lasciando tutti gli altri bit a zero
• ((i & 0xffff0000L) << 16) muove il secondo blocco dalla destra di essere il secondo blocco da sinistra (tutti gli altri bit zero)
• ((i >>> 16) & 0xffff0000L) muove il secondo blocco da sinistra per il secondo blocco da destra (tutti gli altri bit zero)
• (i >>> 48) sposta il blocco più a sinistra nella posizione destra (tutti gli altri bit zero)

Quindi questi quattro valori sono | -ed insieme per produrre l'inversione finale. Se fosse stato fatto in due passaggi, sarebbero due affermazioni che assomigliano alle prime quattro affermazioni, ma con diversi schemi di maschere.

Penso che dopo la riga 4, il modello è 2,1,4,3,6,5,8,7, non 4,3,2,1,8,7,6,5 come si è assunto.I quattro pezzi di linea 5 sono quindi:

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

Il tuo tentativo non è del tutto corretto. Ecco la versione corretta:

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) 

Ecco i due passaggi centrali interrotte:

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) 

---

Anche se sono un po 'sorpreso perché non è implementato come segue:

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 lo schema coerente. E penso che riduca anche il numero di operazioni.

MODIFICA: Capisco perché è implementato così com'è. La versione nella domanda utilizza solo 9 operazioni per le ultime due inversioni. La versione qui (righe 5 e 6) richiede 10 operazioni.

Accidenti ... si parla di micro-ottimizzazione alle estreme conseguenze ...

---

EDIT 2: Perché non ci ho pensato questo? Perché non lo usa java.lang.Long?

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