(i << 48) | ((i & 0xffff0000L) << 16) | ((i >>> 16) & 0xffff0000L) | (i >>> 48) 这段代码如何工作？

Question

以下是 Long 类型中 reverse 方法的实现：

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)

但我认为这是错误的！我认为正确的顺序应该是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)

- liuxiaori

---

那听起来令人头疼，希望那不是一个面试问题！ - Jerome

@Jerome 如果在面试中被问到这个问题，我宁愿离开这个公司。 - Amit

不是面试问题。它是Long.java中reverse方法的含义。 - liuxiaori

在Java中5行代码，我相信我可以把这一切都写在C语言的一行里 :) - Jesus Ramos

@Jesus Ramos，你能为我解释一下吗？我有犯错吗？ - liuxiaori

Answer 1

第一行将相邻的单个位按对交换(0 <-> 1；2 <-> 3；等等)。第二至四行交换相邻的两位、4位和8位序列。这时，原始值已被转化为四个16位块，每个块与开始时相反。第五行重新排列这四个块。基本上，第五行将两个步骤合并为一个：交换两个16位块对和交换一个32位块对。逻辑是：

- (i << 48) 将最右边的16位块移动到左侧位置，其余所有位都是零 - ((i & 0xffff0000L) << 16) 将右侧第二个块移到左侧第二个位置（其余所有位都是零） - ((i >>> 16) & 0xffff0000L) 将左侧第二个块移到右侧第二个位置（其余所有位都是零） - (i >>> 48) 将最左边的块移到右侧位置（其余所有位都是零）

然后将这四个值用 | 运算符连接起来，生成最终的反转。如果分成两个步骤完成，它将是两个语句，看起来与前四个语句类似，但具有不同的掩码模式。

我认为在第四行之后，模式是2,1,4,3,6,5,8,7，而不是像您假设的4,3,2,1,8,7,6,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)

- Ted Hopp

---

嗨，我错了，在第4行之后，模式是2、1、4、3、8、7、6、5。非常感谢！ - liuxiaori

@liuxiaori - 你确定第四行后面的模式是这样的吗？我认为应该是 2,1,4,3,6,5,8,7。 - Ted Hopp

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

- Mysticial

---

关于您的编辑：6,5,8,7,2,1,4,3 是正确的输出。前四行已经交换到8位粒度。第五行进行了最终的16位和32位交换。 - Mysticial

我认为正确的输出应该是8,7,6,5,4,3,2,1。 我也认为代码本身是正确的。 除了您指出的错误之外，第4行后的模式不是OP想象的那样，而是2,1,4,3,6,5,8,7（每个16位块都被反转，而不是每个32位块）。 - Ted Hopp

我和你一样有同样的问题，为什么它要按照你所写的方式实现。 - liuxiaori

它保持相同的模式。因此，一旦你理解了其中一行，你就理解了所有行。所以没有必要“破译”最后一行。编辑：我明白为什么它被实现成这样。它可以节省一个操作数。我给出的版本需要10个，而你问题中的版本只有9个...天啊... - Mysticial

你是 Long.java 的作者吗？是你吗？！ - liuxiaori

不，我没有参与Java开发。你为什么这么想？实际上，我已经有一段时间没有使用Java了。 - Mysticial