c - 由查找表设置的位 - 递归宏

Question

这个问题已经有答案了:

Hint for lookup table set bit count algorithm (1 个回答)

已关闭 9 年前。

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

这段代码在设置位问题中非常有名。我已经了解它如何在编译时输出查找表。

但我需要更多的直觉..意味着

B2(n),B4(n),B6(n)是什么意思？
归结为这个递归宏的基本思想是什么？？

已编辑我的意思是递归背后的想法是什么

Answer 1

这个想法是“递归地将问题定义为 2 位值”:00、01、10、11。它们不是递归宏，但确实代表了递归分解的技术问题。将宏排列为级联通过解决 2 位问题(生成 4 个值)，然后解决 4 位问题(使用 2-位解 4 次)，然后是 6 位(使用 4 位解 4 次)，然后是整个问题(使用 6 位解 4 次)。

2 位提供四个值:0、1、2、3。0 有 0 位设置，1 有 1 位设置，2 也仅设置了 1 位，而 3 设置了 2 位。

4 位数字的值使用相同的模式，并对每个值的额外 2 位使用 2 位模式。

它可以“简化”为每个宏 1 位。

#define B1(n) n,     n+1
#define B2(n) B1(n), B1(n+1),
#define B3(n) B2(n), B2(n+1),
#define B4(n) B3(n), B3(n+1),
#define B5(n) B4(n), B4(n+1),
#define B6(n) B5(n), B5(n+1),
#define B7(n) B6(n), B6(n+1),
 B7(0), B7(1)

请记住，查找表的目的是用表查找 howmanybits[x] 替换函数调用 howmanybits(x)。因此表中的每个值都应代表索引 i 的 f(i) 和整体函数 f。

因此，要真正掌握它，请跟踪前几个值。 B6(0) 以 B4(0) 开头，B4(0) 以 B2(0) 开头，依次为 0、1、1、2。 f(0)=0，f(1)=1，f(2)=1，f(3)=2。 B4(0) 继续 B2(1)，结果为 1, 2, 2, 3。 f(4)=1, f(5)=2, f( 6)=2，f(7)=3。如果您以二进制表示形式查看这些数字，就会清楚这 8 个结果是正确的。

x  x_2  f(x)
0 0000  0 bits set
1 0001  1
2 0010  1
3 0011  2
4 0100  1
5 0101  2
6 0110  2
7 0111  3
...