如何（我<< 48）| （（i＆0xffff0000L）<< 16) | ((i > >> 16）＆0xffff0000L）| （i >>> 48）工作？

Question

這裏是反向的長期實施：

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; 
} 

我能理解行1,2,3,4，而不是5！它是如何工作的？

我將64位分組爲8組，即1是前8位，2是後8位，依此類推。

4號線後然後，像4,3,2,1,8,7,6,5

和順序，我認爲5號線如下工作|操作前：

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) 

但是，我不知道在哪裏劑量錯了，還是這是錯誤的！幾乎要花一整天的時間思考它！

有人可以幫助我！謝謝。

哦，我犯了這樣一個錯誤：

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) 

但我ALSE認爲這是錯誤的！我認爲正確的順序是8,7,6,5,4,3,2,1

我很抱歉，我犯了一些錯誤！它的工作原理如下權利：

線4之後，正確的模式是：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

線路1個交換相鄰的單位對（0 < - > 1; 2 < - > 3;等）。第2-4行交換兩個位，4位和8位的相鄰序列。此時，原始值已被轉換爲四個16位的數據塊，每個數據塊與其開始時的相反。第5行然後重新排列這4個塊。基本上，第5行將兩個步驟合併爲一個：交換兩對16位塊並交換一對32位塊。的邏輯是：

• (i << 48)最右邊的16位塊移動到左側位置，而使其他所有位零
• ((i & 0xffff0000L) << 16)從是從左側的第二塊向右移動所述第二塊（所有其他位零）
• ((i >>> 16) & 0xffff0000L)移動從第二塊左邊是從右側的第二塊（其他所有位零）
• (i >>> 48)移動最左邊的塊到右位（其他所有位零）

然後這四個值是| - 一起產生最終的逆轉。如果分兩步完成，則會有兩條語句看起來像前四條語句，但是掩碼模式不同。

我認爲在第4行之後，模式是2,1,4,3,6,5,8,7，而不是您所假設的4,3,2,1,8,7,6,5。然後，四條線5是：

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

你的嘗試是不完全正確的。這裏的修正版本：

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) 

這裏的打破了中間的兩個步驟：

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) 

---

雖然我在爲什麼它沒有實現微微一驚如下：

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 

它保持模式一致。 我認爲它也減少了操作次數。

編輯：我明白了爲什麼它的實施方式。問題中的版本僅使用9次操作進行最後兩次逆轉。此處的版本（第5行和第6行）需要10個操作。

吉茲...談論微優化到極致...

---

編輯2：爲什麼我沒有想到呢？ 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