给定一个整数,如何使用bit-twiddling找到下一个最大的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位数.向该值添加一个会产生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的幂,则可以继续有效且无限地扩展此技术(例如,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

一种更加数学的方式,没有循环:

public static int ByLogs(int n)
{
    double y = Math.Floor(Math.Log(n, 2));

    return (int)Math.Pow(2, y + 1);
}

Answer 4

这是一个逻辑答案:

function getK(int n)
{
  int k = 1;
  while (k < n)
    k *= 2;
  return k;
}

Answer 5

这里的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的幂,它也会更快地返回.

对于Python> 2.7,对于大多数N来说这更简单,更快:

def next_power_of_2(n):
    """
    Return next power of 2 greater than or equal to n
    """
    return 2**(n-1).bit_length()

Answer 6

这个答案是基于constexpr防止函数参数传递为运行时的任何计算const

大于/大于或等于

以下片段适用于下一个数字 k > n，使得 k = 2^i
(n=123 => k=128, n=128 => k=256)，如 OP 所指定。

如果您想要2 的最小幂大于或等于 n，则只需在以下代码片段中替换__builtin_clzll(n)为即可。__builtin_clzll(n-1)

使用 GCC 或 Clang 的 C++11（64 位）

#include <cstdint>  // uint64_t

constexpr uint64_t nextPowerOfTwo64 (uint64_t n)
{
    return 1ULL << (sizeof(uint64_t) * 8 - __builtin_clzll(n));
}

CHAR_BIT按照martinec的建议进行增强使用

#include <cstdint>

constexpr uint64_t nextPowerOfTwo64 (uint64_t n)
{
    return 1ULL << (sizeof(uint64_t) * CHAR_BIT - __builtin_clzll(n));
}

使用 GCC 或 Clang 的 C++17（从 8 到 128 位）

#include <cstdint>

template <typename T>
constexpr T nextPowerOfTwo64 (T n)
{
   T clz = 0;
   if constexpr (sizeof(T) <= 32)
      clz = __builtin_clzl(n); // unsigned long
   else if (sizeof(T) <= 64)
      clz = __builtin_clzll(n); // unsigned long long
   else { // See /sf/answers/2837010151/
      uint64_t hi = n >> 64;
      uint64_t lo = (hi == 0) ? n : -1ULL;
      clz = _lzcnt_u64(hi) + _lzcnt_u64(lo);
   }
   return T{1} << (CHAR_BIT * sizeof(T) - clz);
}

其他编译器

如果您使用 GCC 或 Clang 以外的编译器，请访问列出了计数前导零按位函数的维基百科页面：

• Visual C++ 2005 => 替换__builtin_clzl()为_BitScanForward()
• Visual C++ 2008 => 替换__builtin_clzl()为__lzcnt()
• icc => 替换__builtin_clzl()为_bit_scan_forward
• GHC (Haskell) => 替换__builtin_clzl()为countLeadingZeros()

欢迎投稿

请在评论中提出改进建议。还为您使用的编译器或您的编程语言提出替代方案......

另请参阅类似答案

• 零八的回答
• 伊德罗诺的回答