Given an integer, how do I find the next largest power of two using bit-twiddling?

If I have a integer number n, how can I find the next number k > n such that k = 2^i, with some i element of N by bitwise shifting or logic.

Example: If I have n = 123, how can I find k = 128, which is a power of two, and not 124 which is only divisible by two. This should be simple, but it eludes me.

For 32-bit integers, this is a simple and straightforward route:

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.

Here's a more concrete example. Let's take the number 221, which is 11011101 in binary:

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

There's one bit in the ninth position, which represents 2^8, or 256, which is indeed the next largest power of 2. Each of the shifts overlaps all of the existing 1 bits in the number with some of the previously untouched zeroes, eventually producing a number of 1 bits equal to the number of bits in the original number. Adding one to that value produces a new power of 2.

Another example; we'll use 131, which is 10000011 in binary:

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

And indeed, 256 is the next highest power of 2 from 131.

If the number of bits used to represent the integer is itself a power of 2, you can continue to extend this technique efficiently and indefinitely (for example, add a n >> 32 line for 64-bit integers).

There is actually a assembly solution for this (since the 80386 instruction set).

You can use the BSR (Bit Scan Reverse) instruction to scan for the most significant bit in your integer.

> bsr scans the bits, starting at the > most significant bit, in the > doubleword operand or the second word. > If the bits are all zero, ZF is > cleared. Otherwise, ZF is set and the > bit index of the first set bit found, > while scanning in the reverse > direction, is loaded into the > destination register

(Extracted from: http://dlc.sun.com/pdf/802-1948/802-1948.pdf)

And than inc the result with 1.

so:

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

In newer CPU's you can use the much faster lzcnt instruction (aka rep bsr). lzcnt does its job in a single cycle.

A more mathematical way, without loops:

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

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

Here's a logic answer:

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

Here's John Feminella's answer implemented as a loop so it can handle Python's long integers:

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

It also returns faster if n is already a power of 2.

For Python >2.7, this is simpler and faster for most N:

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

Greater than / Greater than or equal to

The following snippets are for the next number k > n such that k = 2^i
(n=123 => k=128, n=128 => k=256) as specified by OP.

If you want the smallest power of 2 greater than OR equal to n then just replace __builtin_clzll(n) by __builtin_clzll(n-1) within the above snippets.

C++11 using GCC or Clang (64 bits)

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

Enhancement using CHAR_BIT as proposed by martinec

#include <cstdint>

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

C++17 using GCC or Clang (from 8 to 128 bits)

#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);
}

Other compilers

If you use a compiler other than GCC or Clang, please visit the Wikipedia page listing the Count Leading Zeroes bitwise functions:

• Visual C++ 2005 => Replace __builtin_clzl() by _BitScanForward()
• Visual C++ 2008 => Replace __builtin_clzl() by __lzcnt()
• icc => Replace __builtin_clzl() by _bit_scan_forward
• GHC (Haskell) => Replace __builtin_clzl() by countLeadingZeros()

Contribution welcome

Please propose improvements within the comments. Also propose alternative for the compiler you use, or your programming language...

See also similar answers

• nulleight's answer
• ydroneaud's answer

Here's a wild one that has no loops, but uses an intermediate float.

//  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;

This, and many other bit-twiddling hacks, including the on submitted by John Feminella, can be found here.

assume x is not negative.

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

If you use GCC, MinGW or Clang:

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

If you use Microsoft Visual C++, use function _BitScanForward() to replace __builtin_clz().

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

Bit-twiddling, you say?

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;
}

Each loop strips the least-significant 1-bit directly. N.B. This only works where signed numbers are encoded in two's complement.

What about something like this:

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

You just need to find the most significant bit and shift it left once. Here's a Python implementation. I think x86 has an instruction to get the MSB, but here I'm implementing it all in straight Python. Once you have the MSB it's easy.

>>> 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
>>>

Forget this! It uses loop !

     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;
	}
}

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

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

or even

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