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

Question

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

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。

- Vincent

---

那是 next highest 还是 next-highest？这是有区别的。一个是后继者，另一个是前任。只是好奇。 - WhozCraig

他追求更高的东西，就像代码所显示的那样。 - RichardPlunkett

你知道大多数编译器/机器组合都内置了intlog函数，它通常映射到一个操作码。 - RichardPlunkett

感谢示例。 - WhozCraig

接下来，你是否关心编译时和运行时的效率？（我可以使用更差的算法吗，还是必须像上面那样聪明） - RichardPlunkett

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

- Adam H. Peterson

Answer 2

很遗憾，这可能不是您可以做的。但是如果您恰好拥有constexpr计算前导零位的编译器内置函数，则以下方法在编译时和运行时（如果您提供了运行时参数）都非常高效：

#include <climits>

template <class Int>
inline
constexpr
Int
clp2(Int v)
{
    return v > 1 ? 1 << (sizeof(Int)*CHAR_BIT - __builtin_clz(v-1)) : v;
}

int
main()
{
    static_assert(clp2(0) == 0, "");
    static_assert(clp2(1) == 1, "");
    static_assert(clp2(2) == 2, "");
    static_assert(clp2(3) == 4, "");
    static_assert(clp2(4) == 4, "");
    static_assert(clp2(5) == 8, "");
    static_assert(clp2(6) == 8, "");
    static_assert(clp2(7) == 8, "");
    static_assert(clp2(8) == 8, "");
    static_assert(clp2(42) == 64, "");
}

我使用最新版本的clang编译了以上代码。这并不是没有问题的。你需要决定如何处理负数参数。但是许多架构和编译器都有这样的内置函数（遗憾的是目前它还不是标准C / C ++）。其中一些可能会将其作为constexpr。

如果没有这样的内置函数，我会退而求其次，采用Adam H. Peterson算法的方式进行编写。但这个函数之所以好的原因在于它的简洁性和高效性。

- Howard Hinnant

Answer 3

虽然效率一般，但这个算法可以相当简洁地完成工作：

template <typename T,
          typename = typename std::enable_if<std::is_integral<T>::value>::type,
          typename = typename std::enable_if<std::is_unsigned<T>::value>::type>
constexpr T upperPowerOfTwo(T value, size_t pow = 0)
{
    return (value >> pow) ? upperPowerOfTwo(value, pow + 1)
                          : T(1) << pow;
}

这还允许您指定2的最小幂 - 例如，upperPowerOfTwo(1, 3) 返回8。

对于大多数情况来说，这样做的效率较低，因为它会进行O(sizeof(Type)*CHAR_BIT)次调用，而您链接的算法执行O(log(sizeof(Type)*CHAR_BIT))次操作。但是要注意，此算法将在log(v)次调用后终止，因此如果v足够小（即< log(max value of v-type)），则速度更快。

- Graham Palmer