Given an integer, how do I find the next largest power of two using bit-twiddling?
Solution 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).
Solution 2
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.
Solution 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);
}
Solution 4
Here's a logic answer:
function getK(int n)
{
int k = 1;
while (k < n)
k *= 2;
return k;
}
Solution 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()
AndreasT
Updated on July 18, 2022Comments
-
AndreasT almost 2 years
If I have a integer number
n
, how can I find the next numberk > n
such thatk = 2^i
, with somei
element ofN
by bitwise shifting or logic.Example: If I have
n = 123
, how can I findk = 128
, which is a power of two, and not124
which is only divisible by two. This should be simple, but it eludes me. -
AndreasT over 14 yearsThanks. But I was searching for a "bit-twiddle" way. ;-)
-
AndreasT over 14 yearsAh 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.
-
John Feminella over 14 years@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.)
-
AndreasT over 14 yearswtf! 8-) , will check it out. Thx
-
zxcat over 14 years+1 yes, good trick, I like it :) Some more bit-twiddling tricks can be found here: graphics.stanford.edu/~seander/bithacks.html
-
zildjohn01 almost 14 years+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)
-
That Realty Programmer Guy about 13 yearsIs this idea: fill out the all the 1s up to the largest, currently 'on' bit? If so, would it be
n+min+1
? -
Ian Durkan almost 12 yearsGreat example, this algorithm appears in at least one place in the Java APIs and was confusing me.
-
endolith over 11 yearsWhat if the input is
0
? Also, OP asked for the next largest power of 2,floor
finds the next lower power of 2, no? -
DanDan over 11 yearsIt gets you the existing value. The next part, y+1 gets you the next largest power.
-
Divick about 11 yearsThough this works but could anyone please give an explanation on why it works?
-
Olathe about 11 yearsThis fails. (5 & -5) = 1; 5 + 1 = 6.
-
Griffork almost 11 yearsI think there is a typo in your second example, the number after the pipe should be 0100 0001.
-
endolith over 10 yearsIf your input is already a power of 2, this will not return it though
-
endolith over 10 yearsWhy not just bit shift until it equals zero? Seems like that would be faster.
-
John Feminella over 10 years@endolith That takes log N shifts. This takes log(log N) shifts, so it uses fewer shifts.
-
endolith over 10 years@JohnFeminella: Yeah, I probably should have read the code more carefully before commenting...
-
endolith over 10 years@DanDan: but if n is already a power of 2, it gives the next power of 2 rather than returning n
-
jwalker over 9 yearsIt does
k >= n
, notk > n
-
subrat71 over 9 yearsYou can safely replace your
while
withdo/while
and save one test, as you've already confirmed the initial test with the precedingif
statement. -
Derek Illchuk over 9 yearsThanks @seh; improved with
do while
. -
Chris Middleton about 9 yearsIf you're going to use bit shifts, you might as well do
shift <<= 1
instead ofshift *= 2
. Not sure if that's actually faster in Python, but it should be. -
nemesit about 8 yearsif 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
-
yyny about 8 yearsTalking about assembly in a Python answer adds no value since Python uses byte code...
-
Wauzl about 8 years@endolith: If
n
is a power of two and you want to obtainn
instead of "the next power of two", you can use2 ^ ( ceil(log(x) / log(2)) )
instead. But that was not the question (…how can I find the next numberk > n
…) -
endolith about 8 years@Wauzl Yeah, but the log method is inaccurate for higher numbers anyway. if x = 536870912 it returns 1073741824 instead of 536870912.
-
primo over 7 yearsFastest method here, why no upvotes? Although, I changed to
while(t > (t & -t))
. -
v01pe about 7 yearsHa, so simple! Didn't think about that one :)
-
oHo about 7 yearsSee also similar answer in another question: stackoverflow.com/a/10143264/938111 (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)); }
-
NetMage almost 5 years@primo At least in C# the accepted answer is over 2.5 times faster on average for 32-bit integers.
-
Martin Kealey almost 2 yearsnitpick: The logic is correct, but the description of the
Z
flag is inverted:jz
jumps when theZ
flag is set - which is its state after testing a 0 value. (This goes all the way back to Intel's 8008 CPU.) -
Martin Kealey almost 2 yearsBy definition
uint64_t
(if it exists) has 64 data bits and no padding bits, thereforesizeof(uint64_t)*CHAR_BIT
must be 64. Perhaps you were thinking oflong long
oruint_fast64_t
?