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

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

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

我用鼻尖叮当声编译了上面的内容。这并非没有问题。您需要决定如何处理负面争论。但许多架构和编译器都有这样的内在函数（遗憾的是它现在还不是标准的 C/C++）。其中一些可能会构成内在的 constexpr。

如果没有这样的内在因素，我就会退回到 Adam H. Peterson 的算法。但这个的好处是它的简单性和效率。

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)) it will be faster.

Answer 4

如果你熟悉 ceil_div，即 ceil(float(x)/n) * n，它在整数域的实现就像

(x-1)/n * n

一样简单

next_power_of_two 基本上是

2^ceil(log2(float(x)))

constexpr uint32_t ceil_log2(uint32_t n) {
  return n <= 1 ? 0 : 1 + ceil_log2((n + 1) / 2);
}

constexpr uint32_t next_power_of_two(uint32_t n) {
    return uint32_t(1) << ceil_log2(n);
}

请注意，快速实现实际上是先前逻辑的展开版本。

unsigned int v;
v--;
v |= v >> 1;
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;
v++;

请参阅godbolt了解更多详情。