位计数算法 半字节查表法 32位数
- 位计数
- 算法说明
- 位计数代码
- 32位数的位计数代码 方法一
- 32位数的位计数代码 方法二
- 算法计算过程
- 拓展
- 表的生成
- 方法一
- 表的生成 方法二
- 表格生成结果
- [参考资料]
位计数
位计数(Counting bits set)，指的是计算一个数里bit位置1的个数，例如一个8位数0xea = 0b1110 1010，位置1的个数为5。
算法说明
该算法通过查表的方式来计算一个数里bit位置1的个数。算法采用半字节查表法，与一般的查表法相比，减少了空间的占用，增加了查表次数。正常查表法参照位操作笔记 位计数算法 查表法 32位数。
位计数代码
32位数的位计数代码 方法一
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20static const unsigned char BitsSetTable16[] = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, }; unsigned int count(unsigned int v) { v = BitsSetTable16[v & 0x0F] + BitsSetTable16[v >> 4 & 0x0F] + BitsSetTable16[v >> 8 & 0x0F] + BitsSetTable16[v >> 12 & 0x0F] + BitsSetTable16[v >> 16 & 0x0F] + BitsSetTable16[v >> 20 & 0x0F] + BitsSetTable16[v >> 24 & 0x0F] + BitsSetTable16[v >> 28 & 0x0F]; return v; }
32位数的位计数代码 方法二
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23static const unsigned char BitsSetTable16[] = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, }; unsigned int count(unsigned int v) { unsigned int c; // c is the total bits set in v unsigned char * p = (unsigned char *) &v; c = BitsSetTable16[p[0] & 0x0F] + BitsSetTable16[p[0] >> 4 & 0x0F] + BitsSetTable16[p[1] & 0x0F] + BitsSetTable16[p[1] >> 4 & 0x0F] + BitsSetTable16[p[2] & 0x0F] + BitsSetTable16[p[2] >> 4 & 0x0F] + BitsSetTable16[p[3] & 0x0F] + BitsSetTable16[p[3] >> 4 & 0x0F]; return c; }
算法计算过程
将一个32位数分成8个4位数，进行8次查表，然后相加，得到32位数里的bit位置1的个数。
拓展
表的生成
使用查表法就需要先生成表格，下面有两个通过算法生成表的方式。
方法一
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14static unsigned char BitsSetTable16[16]; void table(void) { int i; BitsSetTable16[0] = 0; for (i = 0; i < 16; i++) { BitsSetTable16[i] = (i & 1) + BitsSetTable16[i / 2]; } }
表的生成 方法二
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24static unsigned char BitsSetTable16[16]; unsigned char count(unsigned char v) { unsigned char c; // c accumulates the total bits set in v for (c = 0; v; v >>= 1) { c += v & 1; } return c; } void table(void) { int i; for (i = 0; i < 16; i++) { BitsSetTable16[i] = count(i); } }
表格生成结果
复制代码
1
2
30 1 1 2 1 2 2 3 1 2 2 3 2 3 3 4
[参考资料]
位操作笔记 位计数算法 查表法 32位数
Bit Twiddling Hacks
[Hacker’s Delight] 作者: Henry S. Warren Jr.
最后
以上就是开心黑米最近收集整理的关于【位操作笔记】位计数算法 半字节查表法 32位数位计数算法说明位计数代码算法计算过程拓展[参考资料]的全部内容，更多相关【位操作笔记】位计数算法内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
![【位操作笔记】位计数算法 半字节查表法 32位数位计数算法说明位计数代码算法计算过程拓展[参考资料]](/uploads/reation/bcimg8.png)
发表评论 取消回复