位数：预处理器魔法vs现代C ++
假设我想为16位块中的64位整数创build编译时构造的位计数查找表。 我知道这样做的唯一方法是下面的代码：
#define B4(n) n, n + 1, n + 1, n + 2 #define B6(n) B4(n), B4(n + 1), B4(n + 1), B4(n + 2) #define B8(n) B6(n), B6(n + 1), B6(n + 1), B6(n + 2) #define B10(n) B8(n), B8(n + 1), B8(n + 1), B8(n + 2) #define B12(n) B10(n), B10(n + 1), B10(n + 1), B10(n + 2) #define B14(n) B12(n), B12(n + 1), B12(n + 1), B12(n + 2) #define B16(n) B14(n), B14(n + 1), B14(n + 1), B14(n + 2) #define COUNT_BITS B16(0), B16(1), B16(1), B16(2) unsigned int lookup[65536] = { COUNT_BITS }; 有没有一种现代（C ++ 11/14）的方式来获得相同的结果？
为什么不使用标准库？
#include <bitset> int bits_in(std::uint64_t u) { auto bs = std::bitset<64>(u); return bs.count(); }
导致汇编（编译-O2）：
bits_in(unsigned long): xor eax, eax popcnt rax, rdi ret
@ tambre提到，在现实情况下，优化者会走得更远：
volatile int results[3]; int main() { results[0] = bits_in(255); results[1] = bits_in(1023); results[2] = bits_in(0x8000800080008000); }
导致汇编程序：
main: mov DWORD PTR results[rip], 8 xor eax, eax mov DWORD PTR results[rip+4], 10 mov DWORD PTR results[rip+8], 4 ret
像我这样的老同学，需要find新的问题来解决:)
更新
不是每个人都很高兴，解决scheme依赖于CPU的帮助来计算bitcount。 那么如果我们使用自动生成的表，但是允许开发人员来configuration它的大小呢？ （警告 – 16位表版本的编译时间很长）
#include <utility> #include <cstdint> #include <array> #include <numeric> #include <bitset> template<std::size_t word_size, std::size_t...Is> constexpr auto generate(std::integral_constant<std::size_t, word_size>, std::index_sequence<Is...>) { struct popcount_type { constexpr auto operator()(int i) const { int bits = 0; while (i) { i &= i - 1; ++bits; } return bits; } }; constexpr auto popcnt = popcount_type(); return std::array<int, sizeof...(Is)> { {popcnt(Is)...} }; } template<class T> constexpr auto power2(T x) { T result = 1; for (T i = 0; i < x; ++i) result *= 2; return result; } template<class TableWord> struct table { static constexpr auto word_size = std::numeric_limits<TableWord>::digits; static constexpr auto table_length = power2(word_size); using array_type = std::array<int, table_length>; static const array_type& get_data() { static const array_type data = generate(std::integral_constant<std::size_t, word_size>(), std::make_index_sequence<table_length>()); return data; }; }; template<class Word> struct use_table_word { }; template<class Word, class TableWord = std::uint8_t> int bits_in(Word val, use_table_word<TableWord> = use_table_word<TableWord>()) { constexpr auto table_word_size = std::numeric_limits<TableWord>::digits; constexpr auto word_size = std::numeric_limits<Word>::digits; constexpr auto times = word_size / table_word_size; static_assert(times > 0, "incompatible"); auto reduce = [val](auto times) { return (val >> (table_word_size * times)) & (power2(table_word_size) - 1); }; auto const& data = table<TableWord>::get_data(); auto result = 0; for (int i = 0; i < times; ++i) { result += data[reduce(i)]; } return result; } volatile int results[3]; #include <iostream> int main() { auto input = std::uint64_t(1023); results[0] = bits_in(input); results[0] = bits_in(input, use_table_word<std::uint16_t>()); results[1] = bits_in(0x8000800080008000); results[2] = bits_in(34567890); for (int i = 0; i < 3; ++i) { std::cout << results[i] << std::endl; } return 0; }
最终更新
该版本允许在查找表中使用任意数量的位，并支持任何inputtypes，即使它小于查找表中的位数。
如果高位为零，它也会短路。
#include <utility> #include <cstdint> #include <array> #include <numeric> #include <algorithm> namespace detail { template<std::size_t bits, typename = void> struct smallest_word; template<std::size_t bits> struct smallest_word<bits, std::enable_if_t<(bits <= 8)>> { using type = std::uint8_t; }; template<std::size_t bits> struct smallest_word<bits, std::enable_if_t<(bits > 8 and bits <= 16)>> { using type = std::uint16_t; }; template<std::size_t bits> struct smallest_word<bits, std::enable_if_t<(bits > 16 and bits <= 32)>> { using type = std::uint32_t; }; template<std::size_t bits> struct smallest_word<bits, std::enable_if_t<(bits > 32 and bits <= 64)>> { using type = std::uint64_t; }; } template<std::size_t bits> using smallest_word = typename detail::smallest_word<bits>::type; template<class WordType, std::size_t bits, std::size_t...Is> constexpr auto generate(std::index_sequence<Is...>) { using word_type = WordType; struct popcount_type { constexpr auto operator()(word_type i) const { int result = 0; while (i) { i &= i - 1; ++result; } return result; } }; constexpr auto popcnt = popcount_type(); return std::array<word_type, sizeof...(Is)> { {popcnt(Is)...} }; } template<class T> constexpr auto power2(T x) { return T(1) << x; } template<std::size_t word_size> struct table { static constexpr auto table_length = power2(word_size); using word_type = smallest_word<word_size>; using array_type = std::array<word_type, table_length>; static const array_type& get_data() { static const array_type data = generate<word_type, word_size>(std::make_index_sequence<table_length>()); return data; }; template<class Type, std::size_t bits> static constexpr auto n_bits() { auto result = Type(); auto b = bits; while(b--) { result = (result << 1) | Type(1); } return result; }; template<class Uint> int operator()(Uint i) const { constexpr auto mask = n_bits<Uint, word_size>(); return get_data()[i & mask]; } }; template<int bits> struct use_bits { static constexpr auto digits = bits; }; template<class T> constexpr auto minimum(T x, T y) { return x < y ? x : y; } template<class Word, class UseBits = use_bits<8>> int bits_in(Word val, UseBits = UseBits()) { using word_type = std::make_unsigned_t<Word>; auto uval = static_cast<word_type>(val); constexpr auto table_word_size = UseBits::digits; constexpr auto word_size = std::numeric_limits<word_type>::digits; auto const& mytable = table<table_word_size>(); int result = 0; while (uval) { result += mytable(uval); #pragma clang diagnostic push #pragma clang diagnostic ignored "-Wshift-count-overflow" uval >>= minimum(table_word_size, word_size); #pragma clang diagnostic pop } return result; } volatile int results[4]; #include <iostream> int main() { auto input = std::uint8_t(127); results[0] = bits_in(input); results[1] = bits_in(input, use_bits<4>()); results[2] = bits_in(input, use_bits<11>()); results[3] = bits_in(input, use_bits<15>()); for (auto&& i : results) { std::cout << i << std::endl; } auto input2 = 0xabcdef; results[0] = bits_in(input2); results[1] = bits_in(input2, use_bits<4>()); results[2] = bits_in(input2, use_bits<11>()); results[3] = bits_in(input2, use_bits<15>()); for (auto&& i : results) { std::cout << i << std::endl; } auto input3 = -1; results[0] = bits_in(input3); results[1] = bits_in(input3, use_bits<4>()); results[2] = bits_in(input3, use_bits<11>()); results[3] = bits_in(input3, use_bits<15>()); for (auto&& i : results) { std::cout << i << std::endl; } return 0; }
示例输出：
7 7 7 7 17 17 17 17 32 32 32 32
例如，调用bits_in(int, use_bits<11>())的结果汇编输出变为：
.L16: mov edx, edi and edx, 2047 movzx edx, WORD PTR table<11ul>::get_data()::data[rdx+rdx] add eax, edx shr edi, 11 jne .L16
这对我来说似乎是合理的。
这是一个基本上围绕constexpr的使用而构build的C ++ 14解决scheme：
// this struct is a primitive replacement of the std::array that // has no 'constexpr reference operator[]' in C++14 template<int N> struct lookup_table { int table[N]; constexpr int& operator[](size_t i) { return table[i]; } constexpr const int& operator[](size_t i) const { return table[i]; } }; constexpr int bit_count(int i) { int bits = 0; while (i) { i &= i-1; ++bits; } return bits; } template<int N> constexpr lookup_table<N> generate() { lookup_table<N> table = {}; for (int i = 0; i < N; ++i) table[i] = bit_count(i); return table; } template<int I> struct Check { Check() { std::cout << I << "\n"; } }; constexpr auto table = generate<65536>(); int main() { // checks that they are evaluated at compile-time Check<table[5]>(); Check<table[65535]>(); return 0; }
可运行版本： http ： //ideone.com/zQB86O
使用c ++ 17，你可以在编译时使用constexpr构造查找表。 通过计算人口数量 ，查找表可以被构build如下：
#include <array> #include <cstdint> template<std::size_t N> constexpr std::array<std::uint16_t, N> make_lookup() { std::array<std::uint16_t, N> table {}; for(std::size_t i = 0; i < N; ++i) { std::uint16_t popcnt = i; popcnt = popcnt - ((popcnt >> 1) & 0x5555); popcnt = (popcnt & 0x3333) + ((popcnt >> 2) & 0x3333); popcnt = ((popcnt + (popcnt >> 4)) & 0x0F0F) * 0x0101; table[i] = popcnt >> 8; } return table; }
示例用法：
auto lookup = make_lookup<65536>();
std::array::operator[]是从c ++ 17开始的 constexpr ，上面的例子用c ++ 14编译，但不会是一个真正的constexpr 。
如果你想惩罚你的编译器，你也可以用variadic模板初始化生成的std::array 。 这个版本也可以使用c ++ 14 ，甚至在c ++ 11中也可以使用索引技巧 。
#include <array> #include <cstdint> #include <utility> namespace detail { constexpr std::uint8_t popcnt_8(std::uint8_t i) { i = i - ((i >> 1) & 0x55); i = (i & 0x33) + ((i >> 2) & 0x33); return ((i + (i >> 4)) & 0x0F); } template<std::size_t... I> constexpr std::array<std::uint8_t, sizeof...(I)> make_lookup_impl(std::index_sequence<I...>) { return { popcnt_8(I)... }; } } /* detail */ template<std::size_t N> constexpr decltype(auto) make_lookup() { return detail::make_lookup_impl(std::make_index_sequence<N>{}); }
注：在上面的例子中，我切换到16位整数的8位整数。
assembly输出
8位版本将只为detail::make_lookup_impl函数创build256个模板参数，而不是65536.后者太多，将超过模板实例深度的最大值。 如果虚拟内存足够多，则可以使用-ftemplate-depth=65536编译器标志提高最大值，并切换回16位整数。
无论如何，看看下面的演示，试试看8位版本是如何计算一个64位整数的设置位的。
现场演示
还有一个后人，使用recursion解决scheme（log（N）深度）创build查找表。 它使用了constexpr-if和constexpr-array-operator []，所以它是非常多的C ++ 17。
#include <array> template<size_t Target, size_t I = 1> constexpr auto make_table (std::array<int, I> in = {{ 0 }}) { if constexpr (I >= Target) { return in; } else { std::array<int, I * 2> out {{}}; for (size_t i = 0; i != I; ++i) { out[i] = in[i]; out[I + i] = in[i] + 1; } return make_table<Target> (out); } } constexpr auto population = make_table<65536> ();
看到它在这里编译： https ： //godbolt.org/g/RJG1JA
for (int x = 0; x < 65536; x++) { int mask = 1; int bitCount = 0; for (int y = 0; y < 16; y++) { if ((mask << y) & x) bitCount++; } lookup_1[x] = bitCount; }
