Bit twiddling: find next power of two with templates in c++

Question

This is a follow-up to my general question: bit-twiddling-find-next-power-of-two

I have now created the following template function:

template <typename T>
T nextPowerOfTwo(T n)
{
    std::size_t k=1;
    n--;
    do {
        n |= n >> k ;
        k <<=1;
    }
    while (k < sizeof(T)*8)
    return ++n;
}

2 Questions:

1. Specifying T as unsigned in nextPowerOfTwo(unsigned T n) threw a compiler error. Can I somehow specifiy T to be unsigned?
2. Is there something that can be honed elegance or performance-wise?

EDIT: Corrected the code, it was crap in the beginning

EDIT: Corrected the code again. I am really sorry. It was quite obvious actually. But thanks anyway for the hints. I wanted to delete it, but there were already too many contributions.

Answer 1

template <typename T>
T nextPowerOfTwo(T v)
{
    if (v < 1) return 0;

    --v;
    for (int i = 0; i < sizeof v; ++i)
     v |= v >> (1<<i);
    return v + 1;
}

Answer 2

If you want your function to be generic, which you clearly want to, you will want to be able to use user-defined types too, which won't have the keyword unsigned. Instead, you should use std::numeric_limits to test for signedness (or, in this case, lack thereof).

You should also not use 8 * sizeof (T), but instead use numeric_limits (again) to determine how many bits your type has. :-)

Answer 3

To answer your first question, no, you cannot. T must be replacable with a complete type declaration; putting unsigned before T could result in unsigned unsigned int or something similar.

That's not exactly what's happening under the covers, but it's a good enough explanation for why you can't use unsigned.

Answer 4

template<typename T>
T nextPowerOfTwo(T n) {
    --n;
    for(T k=1;!(k&(1<<(sizeof(n)+1));k<<=1) n|=n>>k;
    return ++n;
}

Answer 5

You could improve things slightly by changing the loop test to check whether the number is one less than a power of 2:

template <typename T>
T nextPowerOfTwo(T n)
{
    std::size_t k=1;
    --n;
    do {
        n |= n >> k;
        k <<= 1;
    } while (n & (n + 1));
    return n + 1;
}

The algorithm is now O(log2(n)) rather than O(width_of_T_in_bits). This should help for small n, or if n often contains many 1 bits (though the latter doesn't appear in the improved time bound).

Of course it may actually be slower, since the loop test is now probably 2 CPU instructions vs a single instruction in yours.

EDIT 25/8/2009: Thanks to hacker for noticing a very stupid bug! Now fixed.

Answer 6

While @hacker's version is technically correct, my Visual Studio 2008 failed to optimize it properly. Here's my version, which works perfectly. It also performs only logarithmic number of operations as per your request. Although this version is not as elegant, Visual Studio is actually able to calculate the value of nearestPowerOfTwo(value) without executing it. (You must enable optimizations of course).

template <typename T, T v>
struct value_holder
{
    static const T value = v;
};

template <typename T, typename value, typename partial_result>
struct ln_detail
{
    typedef typename ln_detail<T, value_holder<T, (value::value >> 1)>, value_holder<T, partial_result::value + 1> >::type type;
};

template <typename T, typename partial_result>
struct ln_detail<T, value_holder<T, 1>, partial_result>
{
    typedef partial_result type;
};

template <typename T, T value>
struct ln
{
    static const T value = ln_detail<T, value_holder<T, value>, value_holder<T, 0> >::type::value;
};

template <typename T>
T nearestPowerOfTwo(T v)
{
    if (v < 1) return 0;

    --v;
    for (int i = 0; i < ln<T, 8*sizeof v>::value; ++i)
     v |= v >> (1<<i);
    return v + 1;
}