Like (i << 48) | ((i & 0xffff0000L) << 16) | ((i >>> 16) & 0xffff0000L) | (i >>> 48) work?

Question

Here is the implementation of the converse in 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; } 

I can understand the line 1,2,3,4, but not 5! How it works?

I group 64 bits into 8 groups, that is, 1 is the first 8 bits, 2 is two 8 bits, etc.

Then after line 4, a sequence similar to 4,3,2,1,8,7,6,5

and I think line 5 works like below before operation | :

 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) 

But, I do not know where the dose is wrong or wrong! Thinking about it almost the whole day!

Can anyone help me !! Thanks.

oh, I made a mistake as follows:

 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) 

but I think this is wrong! I think the correct sequence is 8,7,6,5,4,3,2,1

I am very sorry that I am wrong! It works correctly as shown below:

after line 4, correct pattern: 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 adjacent individual bits into pairs (0 ± 1; 2 - 3, etc.). Lines 2-4 swap adjacent sequences of two bits, 4 bits and 8 bits. At this point, the original value was converted into four 16-bit blocks with each block opposite to what it was at the beginning. Line 5 then rebuilds 4 blocks. Basically, line 5 combines two steps into one: replacing two pairs of 16-bit blocks and replacing one pair of 32-bit blocks. The logic is this:

• (i << 48) moves the rightmost 16-bit block to the left position, leaving all other bits zeros
• ((i & 0xffff0000L) << 16) moves the second block to the right to be the second block to the left (all other bits are zero)
• ((i >>> 16) & 0xffff0000L) moves the second block on the left to be the second block on the right (all other bits are zero)
• (i >>> 48) moves the leftmost block to the desired position (all other bits are zero)

Then these four meanings | is together to make the final U-turn. If this were done in two stages, these would be two statements that would look the same as the first four operators, but with different mask templates.

I think that after line 4 the pattern is 2,1,4,3,6,5,8,7 , not 4,3,2,1,8,7,6,5 , as you expected. Then the four parts of line 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

Your attempt is not entirely correct. Here's the adjusted version:

 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) 

Here two middle steps are broken:

 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) 

---

Although I'm a little surprised why it is not implemented as follows:

 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 

Keeps pattern matching. And I think this reduces the number of operations.

EDIT: I understand why it is implemented as it is. The version in question uses only 9 operations for the last two turns. The version here (lines 5 and 6) requires 10 operations .

Geez ... speaking of micro-optimization to the extreme ...

---

EDIT 2: Why didn't I think about it? Why doesn't java.lang.Long use this?

 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