给定一个整数，我如何找到下一个最大的二次方位使用比特缠绕？

这里有一个合乎逻辑的答案:

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

function Pow2Thing(int n)
{
x = 1;
while (n>0)
{
n/=2;
x*=2;
}
return x;
}

对于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的次高次幂。

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

这样如何:

int pot = 1;
for (int i = 0; i < 31; i++, pot <<= 1)
if (pot >= x)
break;

一种更加数学化的方法，没有循环:

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


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

这里有一个没有循环，但使用中间浮点数的通配符。

//  compute k = nextpowerof2(n)


if (n > 1)
{
float f = (float) n;
unsigned int const t = 1U << ((*(unsigned int *)&f >> 23) - 0x7f);
k = t << (t < n);
}
else k = 1;

这一点，以及许多其他的小技巧，包括 John Feminella 提交的文章，都可以在 给你中找到。

你只需要找到最重要的部分然后把它往左移一次。下面是一个 Python 实现。我认为 x86有一个获取 MSB 的指令，但是在这里我使用直接的 Python 实现它。一旦你有 MSB 它很容易。

>>> def msb(n):
...     result = -1
...     index = 0
...     while n:
...         bit = 1 << index
...         if bit & n:
...             result = index
...             n &= ~bit
...         index += 1
...     return result
...
>>> def next_pow(n):
...     return 1 << (msb(n) + 1)
...
>>> next_pow(1)
2
>>> next_pow(2)
4
>>> next_pow(3)
4
>>> next_pow(4)
8
>>> next_pow(123)
128
>>> next_pow(222)
256
>>>

实际上有一个汇编解决方案(从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指令(又名 rep bsr)。lzcnt在一个周期内完成它的工作。

// n is the number
int min = (n&-n);
int nextPowerOfTwo = n+min;

假设 x 不是负数。

int pot = Integer.highestOneBit(x);
if (pot != x) {
pot *= 2;
}

下面是 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()

忘了这个吧! 它使用循环！

     unsigned int nextPowerOf2 ( unsigned int u)
{
unsigned int v = 0x80000000; // supposed 32-bit unsigned int


if (u < v) {
while (v > u) v = v >> 1;
}
return (v << 1);  // return 0 if number is too big
}

你说有点无聊？

long int pow_2_ceil(long int t) {
if (t == 0) return 1;
if (t != (t & -t)) {
do {
t -= t & -t;
} while (t != (t & -t));
t <<= 1;
}
return t;
}

每个循环直接去掉最低有效的1位。注意: 这只适用于有符号数字编码为2的补数的情况。

private static int nextHighestPower(int number){
if((number & number-1)==0){
return number;
}
else{
int count=0;
while(number!=0){
number=number>>1;
count++;
}
return 1<<count;
}
}

#define nextPowerOf2(x, n) (x + (n-1)) & ~(n-1)

甚至

#define nextPowerOf2(x, n)  x + (x & (n-1))

如果你使用 GCC，MinGW 或 Clang:

template <typename T>
T nextPow2(T in)
{
return (in & (T)(in - 1)) ? (1U << (sizeof(T) * 8 - __builtin_clz(in))) : in;
}

如果使用 MicrosoftVisualC + + ，请使用函数 _BitScanForward()替换 __builtin_clz()。

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

大于[大于或等于]

以下代码片段适用于 下一个数字 k > n 使得 k = 2 ^ i
(n = 123 = > k = 128，n = 128 = > k = 256).

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

使用 GCC 或 Clang (64位)的 C + + 11

#include <cstdint>  // uint64_t


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

根据 Martinec的建议，使用 CHAR_BIT进行增强

#include <cstdint>


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

C + + 17使用 GCC 或 Clang (从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 https://stackoverflow.com/a/40528716
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，请访问列出 < strong > Count Leadership Zero 按位函数的 Wikipedia 页面:

• Visual C + + 2005 = > 用 _BitScanForward()代替 __builtin_clzl()
• Visual C + + 2008 = > 将 __builtin_clzl()替换为 __lzcnt()
• Icc = > 以 _bit_scan_forward取代 __builtin_clzl()
• GHC (Haskell) = > 用 countLeadingZeros()替换 __builtin_clzl()

欢迎捐款

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

也可以看到类似的答案

• 零光的回答
• Ydroneaud 的回答