java - 使用位旋转计算大于参数的最接近的二的幂的说明

Question

这是一个众所周知的函数，用于计算正参数的下一个最接近的二的幂。然而，我没有太多的经验来理解其背后的逻辑/理论。您能解释一下为什么以及如何运作吗？特别是，选择 1,2,4,8,16 进行移位，如果参数的范围更大，例如，对于 long 会使用什么？为什么是逻辑移位而不是算术移位，最后，ORing 移位 arg 完成了什么？

static int lowestPowerOfTwoGreaterThan(int arg) {
    arg |= (arg >>>  1);
    arg |= (arg >>>  2);
    arg |= (arg >>>  4);
    arg |= (arg >>>  8);
    arg |= (arg >>> 16);
    return ++arg;
}

Answer 1

如果您跟踪值的变化，那就非常简单了。 2 的幂只有一个设置位，例如 100、10000000、10000000000，这意味着 2 的幂减一是的序列，例如10000 - 1 = 1111。因此，该函数的作用是将任何数字更改为一系列 1(不移动其最高 1 位)，然后加 1，例如它将 10000001000111001 (66105) 更改为 11111111111111111 (131071)，并加一以生成 100000000000000000 (131072)。

首先，它将值本身右移 1 位进行或运算。这具有延长值中 1 的所有运行的效果。

   10000001000111001
OR 01000000100011100
   =================
   11000001100111101

您现在注意到，每次运行的零前面至少有两个“1”，因此我们可以通过移位两位而不是一位来加快该过程，而不是再次移位一位。

   11000001100111101
OR 00110000011001111
   =================
   11110001111111111

现在，每次运行的 0 之前至少有 4 个 1，因此这次我们移动 4 个值，然后再次对这些值进行“或”操作。

   11110001111111111
OR 00001111000111111
   =================
   11111111111111111

重复此逻辑，下一个移位距离将是 8，然后是 16(对于 32 位值在此停止)，然后是 32(对于 64 位值在此停止)。对于此示例，由于它已经是一个序列，因此对于进一步的移位，结果保持不变。

此方法将任何二进制数更改为一序列。如前所述，加 1 会产生下一个最大的 2 的幂。