为什么计算比特数很有用？

Question

我看到了许多关于计算输入中设置位数的问题，但它有什么用处呢？

对于那些寻找有关位数计算算法的人，请查看以下内容：

1. 计算无符号长整型序列中常见位数
2. 在无符号整数中计算位转换的最快方法
3. 如何计算32位整数中设置位的数量？

- KushalP

Answer 1

你可以将一串比特看作是一个集合，其中1表示相应元素属于集合。因此，比特计数给出了集合的基数。

实际应用包括压缩、加密和纠错码。例如，请参见wikipedia.org/wiki/Hamming_weight和wikipedia.org/wiki/Hamming_distance。

- Paul R

Answer 2

有些人喜欢使用位图来表示“东西”的存在或不存在。

有一个简单的技巧可以隔离一个字中最不重要的1位，将其转换为下面位数的一组1，然后通过计算1位数来找到位数。

countbits((x XOR (x-1)))-1;

看着它工作。

Let x =     00101100
Then x-1 =  00101011
x XOR x-1 = 00000111

其中有3位被设置为1，因此第2位是原始字中最不重要的1位

- John R. Strohm

Answer 3

如果你正在自己编写奇偶校验方案，你可能想要计算位数。(当然，一般来说，我更愿意使用别人的。) 如果你想模拟旧计算机并跟踪它在原始设备上运行的速度，一些计算机具有乘法指令，其速度因1位的数量而异。

过去十年中，我无法想出任何需要这样做的时间，因此我认为这更多是一个程序设计练习，而不是实际需求。

- David Thornley

---

你可以直接使用比人口计数更少的操作来计算奇偶校验（除非你的CPU具有“POPCNT”或类似功能）。 - Paul R

Answer 4

以一种具有讽刺意味的方式，这是一个很有用的面试问题，因为它需要一些详细的低级思考，并且似乎并没有作为计算机科学课程的标准算法来教授。

- Paul Nathan