c - 此代码如何为任何给定数字找到下一个最高的 2 幂

Question

此代码如何为 32 位整数查找任何给定数字 [>1] 的 2 的下一个最高幂？

n--;
n = n | n>>1;
n = n | n>>2;
n = n | n>>4;
n = n | n>>8;
n = n | n>>16;
n++;

Answer 1

移位和按位或的序列保证了一个由所有1s 组成的数字，它比 2 的幂小一。将 1 添加到它会得到 2 的幂。

初始递减 1 是为了使其适用于n已经是 2 次方的值。

n（显然，如果最初是，则此代码不起作用0。）

Answer 2

递减将使 case 2 ^ n 给出结果 2 ^ n 而不是 2 ^ (n + 1)。它与末尾的增量不对应。

递减和递增之间的部分实际上试图填充所有比当前最高有效位 1 更重要的位。最高位 1 将在每一行之后逐渐传播，并将填充所有不那么重要的位最后一行。

增量是为了达到 2 的下一个最高幂的结果。