c++ - 编译时递归函数来计算整数的下一次幂？

Question

关于 Bit Twiddling Hacks website提供以下算法以将整数四舍五入为下一个二的幂:

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 )
            ;
}