代表数字7的8位像这样:
00000111
设置了三个比特。
确定32位整数中设置位数的算法是什么?
代表数字7的8位像这样:
00000111
设置了三个比特。
确定32位整数中设置位数的算法是什么?
当前回答
unsigned int count_bit(unsigned int x)
{
x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);
x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF);
x = (x & 0x0000FFFF) + ((x >> 16)& 0x0000FFFF);
return x;
}
我来解释一下这个算法。
该算法基于分治算法。假设有一个8位整数213(二进制的11010101),算法是这样工作的(每次合并两个邻居块):
+-------------------------------+
| 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | <- x
| 1 0 | 0 1 | 0 1 | 0 1 | <- first time merge
| 0 0 1 1 | 0 0 1 0 | <- second time merge
| 0 0 0 0 0 1 0 1 | <- third time ( answer = 00000101 = 5)
+-------------------------------+
其他回答
// How about the following:
public int CountBits(int value)
{
int count = 0;
while (value > 0)
{
if (value & 1)
count++;
value <<= 1;
}
return count;
}
当你写出比特模式时,“黑客的喜悦”比特旋转变得更加清晰。
unsigned int bitCount(unsigned int x)
{
x = ((x >> 1) & 0b01010101010101010101010101010101)
+ (x & 0b01010101010101010101010101010101);
x = ((x >> 2) & 0b00110011001100110011001100110011)
+ (x & 0b00110011001100110011001100110011);
x = ((x >> 4) & 0b00001111000011110000111100001111)
+ (x & 0b00001111000011110000111100001111);
x = ((x >> 8) & 0b00000000111111110000000011111111)
+ (x & 0b00000000111111110000000011111111);
x = ((x >> 16)& 0b00000000000000001111111111111111)
+ (x & 0b00000000000000001111111111111111);
return x;
}
第一步将偶数位加到奇数位上,产生每两个位的和。其他步骤将高阶数据块添加到低阶数据块,将数据块的大小一直增加一倍,直到最终计数占用整个int。
一个简单的算法来计算设置位的数量:
int countbits(n) {
int count = 0;
while(n != 0) {
n = n & (n-1);
count++;
}
return count;
}
以11(1011)为例,尝试手动运行该算法。它应该对你有很大帮助!
这也可以正常工作:
int ans = 0;
while(num) {
ans += (num & 1);
num = num >> 1;
}
return ans;
我在任何地方都没见过这种方法:
int nbits(unsigned char v) {
return ((((v - ((v >> 1) & 0x55)) * 0x1010101) & 0x30c00c03) * 0x10040041) >> 0x1c;
}
它每字节工作一次,所以对于一个32位整数,它必须被调用四次。它源于横向加法,但它使用两个32位乘法将指令数量减少到只有7条。
大多数当前的C编译器将使用SIMD (SSE2)指令优化这个函数,当请求的数量是4的倍数时,它变得非常有竞争力。它是可移植的,可以定义为宏或内联函数,并且不需要数据表。
这种方法可以扩展为一次处理16位,使用64位乘法。但是,当所有16位都被设置时,它会失败,返回0,所以它只能在0xFFFF输入值不存在时使用。由于64位操作,它也比较慢,并且没有很好地优化。