定义是通过模式形成表格。它们是递归宏,B6 使用 B4,B4 使用 B2。 B6(0) 将被分解为:
B4(0), B4(1), B4(1), B4(2)
B4(0) 将被分解为:
0, 1, 1, 2
序列的前几个数字将是:
// 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3
正如您所看到的,这些是为表中每个索引设置的位数。
算法的其余部分是将数字分解为 8 位块,并对每个块中设置的位数求和,这就是这些行的内容(您可以根据自己的喜好使用选项 1 或选项 2,而不是同时使用两者) :
// Option 1:
c = BitsSetTable256[v & 0xff] +
BitsSetTable256[(v >> 8) & 0xff] +
BitsSetTable256[(v >> 16) & 0xff] +
BitsSetTable256[v >> 24];
// Option 2:
unsigned char * p = (unsigned char *) &v;
c = BitsSetTable256[p[0]] +
BitsSetTable256[p[1]] +
BitsSetTable256[p[2]] +
BitsSetTable256[p[3]];
底部的代码:
// To initially generate the table algorithmically:
BitsSetTable256[0] = 0;
for (int i = 0; i < 256; i++)
{
BitsSetTable256[i] = (i & 1) + BitsSetTable256[i / 2];
}
是生成 BitsSetTable256 的不同方式。它在运行时而不是在编译时生成表(这是宏定义的作用)。
附:如果您的目标是足够新的 (SSE4) x86,您可以使用 POPCNT 指令。