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.

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

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

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

\mathcal O(1)

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

assuming n fits in an `int`

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

for `long long`

s

if you want to use the `<cmath>`

library (not recommended because of floating point numbers),

```
pow(2, ceil(log2(n)));
```

1 Like

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

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