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

Question

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.

---

Related questions for some specific languages:

• C: Rounding up to next power of 2
• C++: Algorithm for finding the smallest power of two that's greater or equal to a given value (including C++20 std::bit_ceil())

Paphos

This would be a great interview question. – Gyimah

@Rick: I hope you are not an interviewer and I now put a poor applicant in a tight spot ;-) – Paphos

Could be a duplicate of stackoverflow.com/questions/466204/…, anyway answers from this question could be of interest here too. – Sensorium

if n = 128, do you want to find k = 128, or k = 256? – Pelaga

Possible duplicate of Algorithm for finding the smallest power of two that's greater or equal to a given value – Volin

Possible duplicate of Rounding up to next power of 2 – Volin

Answer 1

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

Encephalogram

Ah great thanks! I had a hard time to understand why you could double k every step, but since you "double" every '1' it became obvious. Thanks for the example. – Paphos

@AndreasT: No problem! (BTW, to see why you need to go all the way up to n >> 16, consider what happens if n is already a power of 2. You'll only have a single 1 bit that needs to cover all of the previous bits, which is why all the shifting is necessary.) – Encephalogram

+1 yes, good trick, I like it :) Some more bit-twiddling tricks can be found here: graphics.stanford.edu/~seander/bithacks.html – Contain

Great example, this algorithm appears in at least one place in the Java APIs and was confusing me. – Ashcraft

Though this works but could anyone please give an explanation on why it works? – Stoeber

I think there is a typo in your second example, the number after the pipe should be 0100 0001. – Dichotomize

Why not just bit shift until it equals zero? Seems like that would be faster. – Pelaga

@Pelaga That takes log N shifts. This takes log(log N) shifts, so it uses fewer shifts. – Encephalogram

@JohnFeminella: Yeah, I probably should have read the code more carefully before commenting... – Pelaga

It does k >= n, not k > n – Braynard

if you just add a n >> 32 line you'd get illegal instruction for values n > 4611686018427387904 , so for 64-bit you need a check whether n is beyond the largest power of two that actually fits in the 64-bit – Pronty

Answer 2

Specifically on x86, 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.

Doggoned

If your input is already a power of 2, this will not return it though – Pelaga

nitpick: The logic is correct, but the description of the Z flag is inverted: jz jumps when the Z flag is set - which is its state after testing a 0 value. (This goes all the way back to Intel's 8008 CPU.) – Repair

Answer 3

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

Rattigan

Thanks. But I was searching for a "bit-twiddle" way. ;-) – Paphos

+1, not what the OP wanted, but strangely enough I needed an answer that would fit in a single inline expression: 2 ^ (floor(log(x) / log(2)) + 1) – Englis

What if the input is 0? Also, OP asked for the next largest power of 2, floor finds the next lower power of 2, no? – Pelaga

It gets you the existing value. The next part, y+1 gets you the next largest power. – Rattigan

@DanDan: but if n is already a power of 2, it gives the next power of 2 rather than returning n – Pelaga

@endolith: If n is a power of two and you want to obtain n instead of "the next power of two", you can use 2 ^ ( ceil(log(x) / log(2)) ) instead. But that was not the question (…how can I find the next number k > n…) – Triquetrous

@Triquetrous Yeah, but the log method is inaccurate for higher numbers anyway. if x = 536870912 it returns 1073741824 instead of 536870912. – Pelaga

Answer 4

Here's a logic answer:

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

Workbook

Ha, so simple! Didn't think about that one :) – Nisus

Answer 5

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

Pelaga

If you're going to use bit shifts, you might as well do shift <<= 1 instead of shift *= 2. Not sure if that's actually faster in Python, but it should be. – Resentful

Answer 6

This answer is based on constexpr to prevent any computing at runtime when the function parameter is passed as const

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) in the following snippets.

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

#include <cstdint>  // uint64_t

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

Crumbly

By definition uint64_t (if it exists) has 64 data bits and no padding bits, therefore sizeof(uint64_t)*CHAR_BIT must be 64. Perhaps you were thinking of long long or uint_fast64_t? – Repair

Hi @MartinKealey I do not remember what I was thinking in 2017. Yes we may replace sizeof(uint64_t) * CHAR_BIT by 64. Maybe I was thinking that sizeof(uint64_t) * CHAR_BIT has a better meaning… What would you suggest? – Crumbly

Answer 7

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.

Ofris

wtf! 8-) , will check it out. Thx – Paphos

Answer 8

assume x is not negative.

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

Whaleboat

Answer 9

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().

Vaunt

See also similar answer in another question: https://mcmap.net/q/20261/-rounding-up-to-next-power-of-2 (answered by ydroneaud on 2012). See Wikipedia builtin bitwise functions for other compilers: en.wikipedia.org/wiki/Find_first_set#Tool_and_library_support             This a C++ 64-bits version:        constexpr uint64_t nextPowerOfTwo64 (uint64_t x) { return 1ULL << (sizeof(uint64_t) * 8 - __builtin_clzll(x)); } – Crumbly

Answer 10

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

Bronchitis

Answer 11

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.

Alric

You can safely replace your while with do/while and save one test, as you've already confirmed the initial test with the preceding if statement. – Achitophel

Thanks @seh; improved with do while. – Alric

Fastest method here, why no upvotes? Although, I changed to while(t > (t & -t)). – Sandra

@Sandra At least in C# the accepted answer is over 2.5 times faster on average for 32-bit integers. – Pyrrhuloxia

Answer 12

What about something like this:

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

Whitehead

Answer 13

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

Ashur

Talking about assembly in a Python answer adds no value since Python uses byte code... – Jackquelin

Answer 14

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
     }

Berni

Answer 15

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

Inessential

Answer 16

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

or even

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

Educationist

This rounds up to the next multiple of some fixed power of two, n. Or it's trying to; the second one is wrong, adding the low bits to themselves not necessarily clearing them. The first one is right, e.g. rounding to a multiple of 16 by doing (x+15) & -16. Anyway, this seems to be answering a different question. – Khoury