使用模板元编程的位交换函数

Question

bit twiddling hacks网站提出了以下非常有效的位反转函数：

// Bitswap: reverse the bits of the value of unsigned integral type T
template <class T>
constexpr T bitswap(T src)
{
    constexpr std::size_t char_bit = std::numeric_limits<unsigned char>::digits;
    constexpr std::size_t digits = sizeof(T) * char_bit;
    std::size_t size = digits;
    T mask = ~T();        
    while ((size >>= 1) > 0) {
        mask ^= (mask << size);
        src = ((src >> size) & mask) | ((src << size) & ~mask);
    }
    return src;
}

有没有什么方法可以通过使用模板元编程递归展开循环来加速这个函数？
有没有办法让它与 __uint128_t 等扩展类型一起使用？（原始版本适用于 __uint128_t）
如果 digits 正确初始化为正确的位数，此函数理论上是否可以反转具有非两倍位数的类型的位？（例如假设 uint41_t）。

Answer 1

您不能强制推出模板化调用，但很有可能，这将在优化构建中以一个内联函数结束：

#include <iostream>
#include <limits>
#include <iomanip>

template <class T, int size = ((std::numeric_limits<unsigned char>::digits
                                * sizeof(T)) >> 1)>
struct Swap
{
    static constexpr T bitswap(T src, T mask = ~T())
    {
        mask ^= (mask << size);
        src = ((src >> size) & mask) | ((src << size) & ~mask);
        return Swap<T, (size >> 1)>::bitswap(src, mask);
    }
};

template <class T>
struct Swap<T, 0>
{
    static constexpr T bitswap(T src, T mask)
    {
        return src;
    }
};

template <class T>
constexpr T bitswap(T src)
{
    return Swap<T>::bitswap(src);
}

int main() {
    std::cout << std::hex << bitswap(0x12345678l);
}

Answer 2

这是一个小实用函数，可让您将参数包内联解压到 C++14 中的 lambda 中：

template<class=void, std::size_t...Is>
constexpr auto indexer(std::index_sequence<Is...>) {
  return [](auto&& f) {
    using discard=int[];
    (void)discard{0,(void(
      f(std::integral_constant<std::size_t, Is>{})
    ),0)...};
  };
}
template<std::size_t N>
constexpr auto indexer() {
  return indexer( std::make_index_sequence<N>{} );
}

接下来我们需要一个编译时日志函数：

constexpr std::size_t ct_log_2( std::size_t N ) {
  return (N>1)?1+ct_log_2(N>>1):0;
}

然后我们将它们放在一起：

template <class T>
constexpr T bitswap(T src)
{
  constexpr std::size_t char_bit = std::numeric_limits<unsigned char>::digits;
  static_assert(char_bit == 8);
  constexpr std::size_t digits = sizeof(T) * char_bit;
  T mask = ~T();        

  auto expand = indexer<ct_log_2(digits)>();
  expand([&](auto i){
    constexpr auto size = digits >> (i+1);
    mask ^= (mask << size);
    src = ((src >> size) & mask) | ((src << size) & ~mask);
  });

  return src;
}

遗憾的是，这需要 constexpr lambda 的 C++17 特性。然而，索引器工作可以变成冗长的手动实现。

创建一个 constexpr 大小计算器：

template<std::size_t digits, std::size_t I>
constexpr auto size_calc = (digits >> (I+1));

将 expand 部分替换为：

  using discard=int[];
  (void)discard{0,(void((
    void( mask ^= (mask << size_calc<digits, Is>) ),
    void( src = ( (src >> size_calc<digits, Is> ) & mask ) | ((src << size_calc<digits, Is>) & ~mask) ),
    0
  )),0)...};

我们手动扩展了 expand 为我们所做的事情（是不是很丑陋？），然后进行单参数版本调用：

  return bitswap(src, std::make_index_sequence< ct_log_2(digits) >{} );

具有正确的索引序列。

结果应该是等价的。

Live example.

一些编译器拒绝内联深度递归调用。这里的递归深度是1到3（为了得到参数包的增长）。现在一个简单的递归解决方案只有 log_2(128) 或 6，所以这可能有点矫枉过正。

使用模板元编程的位交换函数

Bitswap function using template metaprogramming

c++

recursion

bit

template-meta-programming

c++14