如何生成 16 位 LookUp Table 以计算设置位

Question

我正在寻找如何生成 16 位、65536 个元素查找 table 以计算设置位的解决方案。我知道要生成 8 位 table 我可以使用：

static const unsigned char BitsSetTable256[256] = 
{
#   define B2(n) n,     n+1,     n+1,     n+2
#   define B4(n) B2(n), B2(n+1), B2(n+1), B2(n+2)
#   define B6(n) B4(n), B4(n+1), B4(n+1), B4(n+2)
    B6(0), B6(1), B6(1), B6(2)
};

但我不知道如何在 16 位中做到这一点

Answer 1

我会这样说：

static const unsigned char BitsSetTable65536[65536] = 
{
#   define B2(n)  n,      n+1,      n+1,      n+2
#   define B4(n)  B2(n),  B2(n+1),  B2(n+1),  B2(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)
           B14(0),B14(1), B14(1),   B14(2)
};

Answer 2

我将只解释该代码的工作原理，因此很容易对其进行扩展。

2位数字的LUT可以很容易地计算出来：

0, 1, 1, 2

即：

二进制“00”有 0 个设置位
二进制“01”有 1 个设置位
二进制“10”有 1 个设置位
二进制“11”有 2 个设置位

现在尝试为 4 位数字构建 LUT。共有16个数，可枚举如下：

二进制“00xx”，其中 xx 是任何 2 位数字
二进制“01xx”，其中 xx 是任何 2 位数字
二进制“10xx”，其中 xx 是任何 2 位数字
二进制“11xx”，其中 xx 是任何 2 位数字

此枚举可让您轻松计算设置位：

二进制“00xx”有 0+B2(xx) 个设置位
二进制“01xx”有 1+B2(xx) 个设置位
二进制“10xx”有 1+B2(xx) 个设置位
二进制“11xx”有 2+B2(xx) 个设置位

因此，您的 4 位数字 LUT 将如下所示：

0, 1, 1, 2,
1, 2, 2, 3,
1, 2, 2, 3,
2, 3, 3, 4

在一般情况下，如果您有 N 位的 LUT：

0, 1, 1, 2, 1, 2, ...

您可以将其转换为 N+2 位的 LUT：

0, 1, 1, 2, 1, 2, ...
1, 2, 2, 3, 2, 3, ... // all numbers as above plus 1
1, 2, 2, 3, 2, 3, ... // another row of numbers, the same
2, 3, 3, 4, 3, 4, ... // all numbers as above plus 1

前面的数字加1是通过宏实现的。要将 table 继续到 16，只需添加更多行：

#   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 BA(n) B8(n), B8(n+1), B8(n+1), B8(n+2)
...

如何生成 16 位 LookUp Table 以计算设置位

How to generate 16 bit LookUp Table for counting set bits

c

lookup

bit