编译时递归函数计算两个整数的下一个幂？

Question

在Bit Twiddling Hacks网站上,提供了以下算法来将整数舍入到下一个2的幂:

unsigned int v; // compute the next highest power of 2 of 32-bit v
v--;
v |= v >> 1;
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;
v++;

我想编写一个元编程函数来计算相同的操作:

• 递归(用于编译时执行)
• 对于任何类型的整数(它甚至应该适用于任何大小的可能笨拙的非标准整数,如15位,65位...)

这是预期功能的形式:

template <typename Type,
          // Something here (like a recursion index)
          class = typename std::enable_if<std::is_integral<Type>::value>::type,
          class = typename std::enable_if<std::is_unsigned<Type>::value>::type>
constexpr Type function(const Type value)
{
     // Something here
}

怎么做 ？

示例:因为value = 42它应该返回64

Answer 1

这应该实现你给出的算法:

template<typename T>
constexpr T roundup_helper( T value, unsigned maxb, unsigned curb ) {
    return maxb<=curb
            ? value
            : roundup_helper( ((value-1) | ((value-1)>>curb))+1, maxb, curb << 1 )
            ;
}

template<typename T,
        typename = typename enable_if<is_integral<T>::value>::type,
        typename = typename enable_if<is_unsigned<T>::value>::type>
constexpr T roundup( T value ) {
    return roundup_helper( value, sizeof(T)*CHAR_BIT, 1 );
}

至少,它似乎在我的测试程序中正常工作.

或者,您可以像这样移动v-1和v+1移出辅助函数:

template<typename T>
constexpr T roundup_helper( T value, unsigned maxb, unsigned curb ) {
    return maxb<=curb
            ? value
            : roundup_helper( value | (value>>curb), maxb, curb << 1 )
            ;
}

template<typename T,
        typename = typename enable_if<is_integral<T>::value>::type,
        typename = typename enable_if<is_unsigned<T>::value>::type>
constexpr T roundup( T value ) {
    return roundup_helper( value-1, sizeof(T)*CHAR_BIT, 1 )+1;
}

另一种可能性是利用默认参数并将其全部放在一个函数中:

template<typename T,
        typename = typename enable_if<is_integral<T>::value>::type,
        typename = typename enable_if<is_unsigned<T>::value>::type>
constexpr T roundup(
        T value,
        unsigned maxb = sizeof(T)*CHAR_BIT,
        unsigned curb = 1
        ) {
    return maxb<=curb
            ? value
            : roundup( ((value-1) | ((value-1)>>curb))+1, maxb, curb << 1 )
            ;
}