language-agnostic - 给定一个整数，如何使用位旋转找到下一个最大的二的幂？

Question

如果我有一个整数n，我怎样才能找到下一个数字k > n使得k = 2^i，通过按位移位或逻辑处理 N 的某个 i 元素。

示例:如果我有 n = 123，如何找到 k = 128(2 的幂)，而不是 124 > 只能被二整除。这应该很简单，但我却搞不懂。

<小时/>

某些特定语言的相关问题:

• C: Rounding up to next power of 2
• C++: Algorithm for finding the smallest power of two that's greater or equal to a given value (包括 C++20 std::bit_ceil())

Answer 1

对于 32 位整数，这是一个简单直接的途径:

unsigned int n;

n--;
n |= n >> 1;   // Divide by 2^k for consecutive doublings of k up to 32,
n |= n >> 2;   // and then or the results.
n |= n >> 4;
n |= n >> 8;
n |= n >> 16;
n++;           // The result is a number of 1 bits equal to the number
               // of bits in the original number, plus 1. That's the
               // next highest power of 2.

这是一个更具体的例子。我们以数字 221 为例，二进制表示为 11011101:

n--;           // 1101 1101 --> 1101 1100
n |= n >> 1;   // 1101 1100 | 0110 1110 = 1111 1110
n |= n >> 2;   // 1111 1110 | 0011 1111 = 1111 1111
n |= n >> 4;   // ...
n |= n >> 8;
n |= n >> 16;  // 1111 1111 | 1111 1111 = 1111 1111
n++;           // 1111 1111 --> 1 0000 0000

第九位有一位，代表2^8，或者256，它确实是下一个最大的2的幂。每次移位都会将数字中所有现有的 1 位与一些先前未触及的零重叠，最终产生与原始数字中的位数相等的 1 位数量。该值加一会产生 2 的新幂。

另一个例子；我们将使用 131，即二进制的 10000011:

n--;           // 1000 0011 --> 1000 0010
n |= n >> 1;   // 1000 0010 | 0100 0001 = 1100 0011
n |= n >> 2;   // 1100 0011 | 0011 0000 = 1111 0011
n |= n >> 4;   // 1111 0011 | 0000 1111 = 1111 1111
n |= n >> 8;   // ... (At this point all bits are 1, so further bitwise-or
n |= n >> 16;  //      operations produce no effect.)
n++;           // 1111 1111 --> 1 0000 0000

事实上，256 是 131 中下一个最大的 2 次幂。

如果用于表示整数的位数本身就是 2 的幂，您可以继续高效且无限地扩展此技术(例如，为 64 添加 n >> 32 行位整数)。