给定一个整数，我该如何使用位旋转找到下一个最大的2的幂？

Question

如果我有一个整数n，我该如何找到下一个数字k > n，使之k = 2^i具有某些i元素的N按位移位或逻辑运算。示例：如果我有n = 123，我怎么能找到k = 128，它是2的幂，而不是124只能被2整除的值。这应该很简单，但这使我难以理解。

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位数。给该值加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的幂，则可以继续有效且无限地扩展此技术（例如，n >> 32为64位整数添加一行）。

Answer 2

实际上有一个汇编解决方案（自80386指令集起）。

您可以使用BSR（反向位扫描）指令扫描整数中的最高有效位。

bsr扫描双字操作数或第二个字中从最高有效位开始的位。如果这些位全为零，则清除ZF。否则，将设置ZF，并在反向扫描时将找到的第一个设置位的位索引加载到目标寄存器中

（摘自：http : //dlc.sun.com/pdf/802-1948/802-1948.pdf）

并且比用1增加结果。

所以：

bsr ecx, eax  //eax = number

jz  @zero

mov eax, 2    // result set the second bit (instead of a inc ecx)

shl eax, ecx  // and move it ecx times to the left

ret           // result is in eax

@zero:

xor eax, eax

ret

在较新的CPU中，您可以使用快得多的lzcnt指令（aka rep bsr）。lzcnt在一个周期内完成工作。

Answer 3

这是约翰·费米内拉（John Feminella）的答案，实现为循环，这样它就可以处理Python的长整数：

def next_power_of_2(n):

    """

    Return next power of 2 greater than or equal to n

    """

    n -= 1 # greater than OR EQUAL TO n

    shift = 1

    while (n+1) & n: # n+1 is not a power of 2 yet

        n |= n >> shift

        shift <<= 1

    return n + 1

如果n已经是2的幂，它也会更快返回。

对于大于2.7的Python，对于大多数N来说，这更简单，更快：

def next_power_of_2(n):

    """

    Return next power of 2 greater than or equal to n

    """

    return 2**(n-1).bit_length()