Smallest Power of 2 greater than n

Question

This is slightly different than all the other questions asking just for an algorithm. I would like to know whether there is an O(1) algorithm that does this in C++. It seems that since C++ is such a low-level language that works closely with bits, there would be a quick O(1) function that would return the highest bit, to which we could just do << 1 to get the answer.

You might want to qualify your expectations for O(1). O(1) does not mean "one operation", but "has a maximum runtime regardless of input size". This is why, say, division, which takes multiple CPU cycles, is still considered O(1). Because C++ integers are bounded, even a naive "traverse the bits" algorithm is O(1). — dominicm00, May 31 '21 at 00:44
There's a lot of discussion [here](https://stackoverflow.com/q/671815/207421) about a computation for the highest set bit, and some links as well. — user207421, May 31 '21 at 00:49
duplicates: [Algorithm for finding the smallest power of two that's greater or equal to a given value](https://stackoverflow.com/q/364985/995714), [Algorithm for finding the smallest power of two that's greater or equal to a given value](https://stackoverflow.com/q/364985/995714), [Rounding up to next power of 2](https://stackoverflow.com/q/466204/995714) — phuclv, May 31 '21 at 02:36
other duplicates: [What is the fastest/most efficient way to find the highest set bit (msb) in an integer?](https://stackoverflow.com/q/671815/995714), [how to know the position of the first(left -> right) '1' bit in a char efficiently](https://stackoverflow.com/q/23083504/995714), [Find the highest order bit](https://stackoverflow.com/q/53161/995714) — phuclv, May 31 '21 at 03:03

score 2 · Answer 1 · answered May 31 '21 at 01:11

2

Sure.

uint32_t smallest_power_of_two_greater_than_n(int n) {
  std::array<uint32_t, 32> powers_of_two = {0, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648};
  for (uint32_t minimum : powers_of_two) {
    if (n <= minimum)
      return minimum;
  // If there's no representable number... return 0?
  return 0;
}

This is O(32) which is the same as O(1).

answered May 31 '21 at 01:11

Bill Lynch

80,138
16
128
173

2

Who said that *n* is on 32 bits? – Déjà vu May 31 '21 at 01:17
1

@Breakingnotsobad It doesn't matter. It could be 8 or 128, it is still *O(k)*, which is still *O(1)*. – user207421 May 31 '21 at 01:43
So, it is O(*b*) with *b* number of bits. – Déjà vu May 31 '21 at 04:31

phuclv · Accepted Answer · 2021-06-02T15:57:58.010

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)

Thank you. It turns out that for ints, it is relatively simple: `(1 << (32 - __builtin_clz(n)))` — Mike Smith, May 31 '21 at 06:50

score -2 · Answer 3 · answered May 31 '21 at 01:04

-2

No, because std::log has O(log log n).

#include <iostream>
#include <cmath>

int main()
{
        int n;
        std::cin >> n;

        auto logtwo = std::log(n) / std::log(2); //calculate the log of n to the base of 2.
        double integer; //stores the integer part of logtwo.

        //check if the variable logtwo is an integer or not
        if(std::modf(logtwo, &integer) == 0.0)
                std::cout << logtwo;
        else
                std::cout << static_cast<int>(logtwo+1);
}

Reference: What is the complexity of the log function?

answered May 31 '21 at 01:04

Chris Lee

1

1

You're assuming that `log()` is the only solution. – user207421 May 31 '21 at 01:17
using `log` to get the most significant bit position is the most inefficient way and also has [a high possibility of returning an incorrect result](https://stackoverflow.com/q/67559309/995714) due to the nature of floating-point math. Almost all architectures can get log2 of an integer in 1 or 2 instructions – phuclv May 31 '21 at 02:52

Smallest Power of 2 greater than n

3 Answers3