Algorithm for finding the smallest power of two that's greater or equal to a given value
Here's my favorite. Other than the initial check for whether it's invalid (<0, which you could skip if you knew you'd only have >=0 numbers passed in), it has no loops or conditionals, and thus will outperform most other methods. This is similar to erickson's answer, but I think that my decrementing x at the beginning and adding 1 at the end is a little less awkward than his answer (and also avoids the conditional at the end).
/// Round up to next higher power of 2 (return x if it's already a power
/// of 2).
inline int
pow2roundup (int x)
{
if (x < 0)
return 0;
--x;
x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
x |= x >> 8;
x |= x >> 16;
return x+1;
}
Smallest Power of 2 greater than n
The most efficient way in C++20 is std::bit_ceil(n)
In older C++ standard use boost::multiprecision::msb()
or compiler intrinsics of your compiler like __builtin_clz()
or _BitScanReverse()
... to get the most significant bit and then return that value
return 1 << boost::multiprecision::msb(n); // cross-platform
return n == 0 ? 1 : 1 << (31 - __builtin_clz(n)); // GCC, Clang
int index;
return _BitScanReverse(&index, n)) ? 1 << index : 1; // MSVC, ICC
return n == 0 ? 1 : 1 << (31 - _lzcnt_u32(n)); // ICC
(Assuming you want to get the smallest power of 2 greater than n
which is an int
and contains 32 bits)
Finding the smallest power of 2 greater than n
This piece of code fills all the least significant bits of the given number n
with binary 1
s and after that increases the result by 1
, achieving the requested outcome. E.g., for input 101
the bit manipulations will yield 111
and after the increase by 1
it will become 1000
(8), which is indeed the least power of 2 greater then 101
(5).
Update: Actually, this is an optimization to the trivial method of just setting each lsb bit manually. Why this optimization achieves the same result is a different question in a broader scope which is beyond this question.
Rounding up to next power of 2
Check the Bit Twiddling Hacks. You need to get the base 2 logarithm, then add 1 to that. Example for a 32-bit value:
Round up to the next highest power of 2
unsigned int v; // compute the next highest power of 2 of 32-bit v
v--;
v |= v >> 1;
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;
v++;
The extension to other widths should be obvious.
Given an integer, how do I find the next largest power of two using bit-twiddling?
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).
Related Topics
Capturing a Reference by Reference in a C++11 Lambda
Format Number with Commas in C++
What Is the Easiest Way to Parse an Ini File in C++
The Simplest and Neatest C++11 Scopeguard
Computing Length of a C String at Compile Time. Is This Really a Constexpr
Building Glew on Windows with Mingw
Q_Object Throwing 'Undefined Reference to Vtable' Error
When Are Static and Global Variables Initialized
Why in the Code "456"+1, Output Is "56"
How to Build a Graphical User Interface in C++
How to Print the Elements of a C++ Vector in Gdb
How to Install the Openssl Libraries on Ubuntu