我正在寻找如何生成 16 位、65536 个元素查找表以计算设置位的解决方案。我知道要生成我可以使用的 8 位表:
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 位中做到这一点
最佳答案
我将只解释该代码的工作原理,因此很容易对其进行扩展。
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是通过宏实现的。要将表格继续到 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)
...
关于c - 如何生成 16 位查找表来计算设置位,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/41104560/