6

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

对于那些寻找有关位计数的算法的人，请看这里：

  1. 计算无符号长序列中的公共位
  2. 计算无符号整数中位转换数的最快方法
  3. 如何计算 32 位整数中设置的位数？
4

4 回答 4

5

您可以将一串位视为 a set，其中 1 表示相应元素的集合的成员资格。因此，位计数为您population count提供了集合的值。

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

于 2010-04-13T15:52:28.130 回答
0

如果您正在滚动自己的奇偶校验方案，您可能需要计算位数。（当然，一般来说，我宁愿使用其他人的。）如果您正在模拟一台旧计算机并想跟踪它在原始计算机上的运行速度，有些具有乘法指令，其速度随数字而变化1 位。

在过去十年左右的时间里，我想不出任何时候我想这样做，所以我怀疑这更像是一种编程练习，而不是实际需要。

于 2010-04-13T16:05:06.673 回答
0

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

于 2010-04-13T16:05:42.830 回答
0

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

有一个简单的技巧可以隔离一个字中最低有效的 1 位，将其转换为它下面的位中的一个字段，然后您可以通过计算 1 位来找到位号。

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

看着它工作。

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

其中设置了 3 位，因此位 2 是原始字中最低有效的 1 位

于 2010-04-13T16:09:36.903 回答