gpt4 book ai didi

count - 查找表设置位计数算法的提示

转载 作者:行者123 更新时间:2023-12-01 10:59:20 25 4
gpt4 key购买 nike

我正在寻找设置位计数问题的解决方案(给定一个二进制数,如何有效地计算设置了多少位)。

在这里,http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive ,我找到了一些方法。

查找表方法呢?我不明白二进制表示/数字的哪些属性使它起作用。

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

unsigned int v; // count the number of bits set in 32-bit value v
unsigned int c; // c is the total bits set in v

// 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首先定义。为什么要定义这些量 B2、B4、...?在我看来,它们之后就不再使用了。

你能暗示更多关于二进制表示的文档吗?

谢谢!

最佳答案

定义是按模式形成表格。它们是递归宏,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 指令。

关于count - 查找表设置位计数算法的提示,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12684805/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com