给定一个整数，我怎样才能find使用bit-twiddling的下一个最大功耗？
如果我有一个整数n ，我怎样才能find下一个数k > n ，使得k = 2^i ，其中一些i元素是按位移或逻辑的。
例如：如果我有n = 123 ，我怎样才能findk = 128 ，这是2的幂，而不是124 ，只能被2整除。 这应该是简单的，但它逃避了我。
对于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.
这是一个更具体的例子。 我们以二进制数字11011101的数字221：
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行）。
实际上有一个汇编解决scheme（自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在一个循环中完成它的工作。
更math的方式，没有循环：
public static int ByLogs(int n) { double y = Math.Floor(Math.Log(n, 2)); return (int)Math.Pow(2, y + 1); }
这是一个逻辑答案：
function getK(int n) { int k = 1; while (k < n) k *= 2; return k; }
这里是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()
这是一个没有循环，但使用中间浮点的野生。
// 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;
在这里可以find这个，还有许多其他的一些捣乱的黑客，包括John Feminella提交的。
假设x不是负数。
int pot = Integer.highestOneBit(x); if (pot != x) { pot *= 2; }
如果您使用GCC，MinGW或Clang：
template <typename T> T nextPow2(T in) { return (in & (T)(in - 1)) ? (1U << (sizeof(T) * 8 - __builtin_clz(in))) : in; }
如果使用Microsoft Visual C ++，请使用函数_BitScanForward()replace__builtin_clz() 。
function Pow2Thing(int n) { x = 1; while (n>0) { n/=2; x*=2; } return x; }
有点扭曲，你说？
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位。 注意：这只适用于有符号数字以二进制补码编码。
那么这样的事情呢？
int pot = 1; for (int i = 0; i < 31; i++, pot <<= 1) if (pot >= x) break;
你只需要find最重要的位，并将其左移一次。 这是一个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 >>>
忘掉这个！ 它使用循环！
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 }
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; } }
大于/大于或等于
下面的片段是对于下一个数字k> n，使得k = 2 ^ i
（n = 123 => k = 128，n = 128 => k = 256）。
如果你想让2的最小次方大于或等于n，那么在上面的代码片段中用__builtin_clzll(n-1)代替__builtin_clzll(n) 。
使用GCC或Clang的C ++ 11（64位）
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以外的编译器，请访问维基百科页面，列出Count Leading Zeroes按位函数 ：
- Visual C ++ 2005 =>用
_BitScanForward()replace__builtin_clzl()_BitScanForward() - Visual C ++ 2008 =>用
__lzcnt()replace__builtin_clzl()__lzcnt() - icc =>用
_bit_scan_forwardreplace__builtin_clzl() - GHC（Haskell）=>用
countLeadingZeros()replace__builtin_clzl()countLeadingZeros()
欢迎贡献
请在评论中提出改进build议。 也build议替代您使用的编译器，或您的编程语言…
另请参阅类似的答案
- nulleight的答案
- ydroneaud的回答
// n is the number int min = (n&-n); int nextPowerOfTwo = n+min;
#define nextPowerOf2(x, n) (x + (n-1)) & ~(n-1)
甚至
#define nextPowerOf2(x, n) x + (x & (n-1))
