Algorithm: Smallest Power of 2 >= n

#1

I want to be able to find the smallest power of 2 >= n.

For example:

Input: 1
Output: 1

Input: 3
Output: 4

Input: 29
Output: 32

Is there an O(1) algorithm for doing this? Otherwise, what is the fastest algorithm considering constant factors as well.

#2

I think you can do this using some built-in logarithm functions, but Iā€™m not 100% sure.

#3

The formula for this is 2^{\lceil \log_2 n\rceil}.

#4

What is the time complexity of the pow function in cpp?

#5

\mathcal O(1)

(1 << (32 - __builtin_clz(n)))

assuming n fits in an int

(1LL << (64 - __builtin_clzll(n)))

for long longs

if you want to use the <cmath> library (not recommended because of floating point numbers),

pow(2, ceil(log2(n)));
1 Like
#6

Cool, is there any where I can find these __builtin functions, they seem to be very useful.

#7

https://cses.fi/book/book.pdf#page=108

#8

Thanks! I also find this article in GeeksForGeeks which talks about it.