Return the next power of two

Question

Given an unsigned integer \$N\$, I want to return \$P\$ with \$P\$ being a power of two such that \$P \ge N\$.

Examples:

• 1 -> 1
• 2 -> 2
• 3 -> 4
• 5 -> 8

The goal is to provide a very fast implementation. This code is supposed to target a specific platform and we can make the assumption that the intrinsics used are supported.

uint32_t nextPowerOfTwo(uint32_t n) {
    uint32_t msb_index = fls(n);
    uint32_t trailing_zeros = std::__ctz(n);
    bool is_pot = (msb_index - 1 == trailing_zeros);
    uint32_t p = (is_pot ? n : 1 << msb_index);
    return p;
}

Answer 1

If you really care about performance you may also give a chance to a branchless version. Note that compiler may optimize code with explicit branches (if and ?:) if target architecture supports CMOV (& similar) instructions, check generated assembly output. In these examples I will use X86 mnemonics but I suppose meaning is clear whichever your architecture is.

Also you're using non-standard fls() and std::__clz(), they may be implemented with instrinsics or not. If not then performance will greatly decrease because they need a loop or a lookup table instead of BSR (or LZCNT) and BSF (or TZCNT).

uint32_t nextPowerOfTwo(uint32_t n)
{
    --n;

    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;

    return n + 1;
}

Note that 0 gives a wrong result then if you expect 0 as input and you don't want 0 as output you have to handle this special case (just return 1 or add 1 if your compiler will generate a branch for that.) AFAIK also implementation with BSx (or xZCNT) have the same problem (they just set ZF or CF) then special case has to be handled also there (if your implementation specific function does not already do it).

Code is equivalent to 1 << (log2(n - 1) + 1). I don't have a link to original code (algorithm is not mine!) but in my comments authors are W. Lewis and P. Hart) and (thanks Martin) there also is another author who arrived to the same code (with link to their original discussion/implementation!)

---

Which implementation is faster? It depends (see comments for a discussion with CodeRodde.) Target architecture (possibly revision), compiler vendor, version and settings will all affect results. Exact numbers are meaningless without details about your specific scenario, the point is that CodeRodde's answer is faster than this with MSVC++ but slower with GCC, the absolutely great answers from Jerry and JS1 also add more doubts about which method is best.

The only thing I can suggest is to implement them all and pick the fastest one in your specific case. If this is truly performance critical, because this function is so small, I'd also feel to suggest is to put some raw performance comparison in your unit tests: when current version will be slower than expected (compared to all the others) you will need to inspect again...

Answer 2

Undefined behavior

Your code runs into undefined behavior when the input number is 0x80000001 or larger. The undefined behavior comes here:

uint32_t p = (is_pot ? n : 1 << msb_index);

because msb_index will be 32, and shifting a uint32_t left by 32 is undefined behavior. However, the problem description does not specify what should be returned if the input is that large (since there is no larger power of two that will fit in a uint32_t), so it's not clear whether returning an arbitrary value is acceptable.

Type of 1

Another small note is that when you shift like this:

1 << msb_index

the type of 1 is int, not uint32_t. So if you were on a machine with 16-bit integers, you would get incorrect results. To fix this, you should cast the 1 to a uint32_t like this:

(uint32_t) 1 << msb_index

Branchless

Your current function seems pretty fast, but suffers from a branch because you check for a power of two as a special case. In order to avoid the special case, you can do a trick and instead of doing fls(n), you can do fls(n+n-1). This will give you the bit number of the next higher bit while taking into account the special case of a perfect power of two.

The only problem with this technique is for the input of 0. To fix the special case for 0, you can do the following:

n += !n;

Here, the n += !n will not have any effect unless n is zero, in which case it adds 1 to n. So the final rewrite of your function would be:

uint32_t nextPowerOfTwo(uint32_t n) {
    n += !n;
    return (uint32_t) 1 << (fls(n+n-1) - 1);
}

Benchmarking

I didn't have fls() available on my system, so I used 32 - __builtin_clz() instead, which should be the same as fls(). The code I used to test was:

uint32_t nextPowerOfTwo(uint32_t n)
{
    n += !n;
    return (uint32_t) 1 << (31 - __builtin_clz(n+n-1));
}

I ran the function on each number from 0 to 0xffffffff. And the timing results were:

Original function: 12.7 seconds
Adriano Repetti  :  8.8 seconds
JS1              :  4.7 seconds

I also ran some of the other proposed solutions, but for me they ended up slower than the original. So perhaps they didn't translate to my platform (Gnu C compiler on Cygwin/Windows 7/32-bit X86).

Answer 3

You can squeeze a little bit of performance. Below is everything you need for correctness demonstration and efficiency comparison to your implementation:

#include <iostream>
#include <chrono>
#include <cstdint>

using namespace std;

class CurrentTime {
    std::chrono::high_resolution_clock m_clock;

public:
    uint64_t milliseconds()
    {
        return std::chrono::duration_cast<std::chrono::milliseconds>
        (m_clock.now().time_since_epoch()).count();
    }
};

uint32_t to_power_of_two(uint32_t number)
{
    uint32_t msb_index = fls(number);
    uint32_t tmp = ((uint32_t) 1) << (msb_index - 1);
    return (tmp == number) ? number : (((uint32_t) 1) << msb_index);
}

uint32_t nextPowerOfTwo(uint32_t n) {
    uint32_t msb_index = fls(n);
    uint32_t trailing_zeros = std::__ctz(n);
    bool is_pot = (msb_index - 1 == trailing_zeros);
    uint32_t p = (is_pot ? n : 1 << msb_index);
    return p;
}

int main()
{
    cout << "DEMO" << endl;

    for (uint32_t number = 1; number < 100; ++number)
    {
        cout << number << " : " << to_power_of_two(number) << " : " << nextPowerOfTwo(number) << endl;
    }

    CurrentTime ct;
    uint64_t start = ct.milliseconds();


    for (uint32_t number = 1; number < 100 * 1000 * 1000; ++number)
    {
        nextPowerOfTwo(number);
    }

    uint64_t end = ct.milliseconds();

    cout << "nextPowerOfTwo in " << (end - start) << " milliseconds." << endl;

    start = ct.milliseconds();

    for (uint32_t number = 1; number < 100 * 1000 * 1000; ++number)
    {
        to_power_of_two(number);
    }

    end = ct.milliseconds();

    cout << "to_power_of_two in " << (end - start) << " milliseconds." << endl;
}

I get something like that:

nextPowerOfTwo in 1236 milliseconds.
to_power_of_two in 1041 milliseconds.

Hope that helps.

Post scriptum

After a discussion with Adriano, it became evident that there is no evident "winner algorithm." If you compile with MSVC++, you will benefit from my implementation. In case you use G++, use Adriano's.

Answer 4

As others have already said, a great deal here depends on the compiler. This function is small and simple enough that even a minor change in code generation can lead to a substantial change in speed (percentage-wise, anyway).

Just for example, Visual C++ does particularly well with function objects. You can gain a fair amount of speed by packaging the code as a function object instead of a bare function. Add in a few logic tricks (that I'd normally advise against, but might be useful in this case) and we can get something like this:

struct jerry {
    template <class T>
    T operator()(T in) {
        unsigned long  msb_index = fls(in);
        return T(1) << (msb_index + (msb_index - T(1) != ctz(in)) - T(1));
    }
};

Gcc, however, doesn't (at least with the optimization flags I've tried) work well with that at all. Rather the contrary, it ends up running quite slowly. With gcc, leaving it as a function works out better:

template <class T>
T jerry2(T in) {
    unsigned long  msb_index = fls(in);
    return T(1) << (msb_index + (msb_index - 1 != ctz(in)) - 1);
}

That does lead to one problem though: we need different syntax to invoke these two things, there's more to switching between them than just a quick definition based on which compiler's standard macros are defined.

If you can put up with the difference in syntax, the function object does work pretty well with VC++ though:

Jerry      time: 2147, total: 1789569708
Jerry2     time: 2950, total: 1789569708
coderodde  time: 3795, total: 1789569708
Adriano    time: 2483, total: 1789569707
Mr_Pouet   time: 2775, total: 1789569708