代表数字7的8位像这样:
00000111
设置了三个比特。
确定32位整数中设置位数的算法是什么?
代表数字7的8位像这样:
00000111
设置了三个比特。
确定32位整数中设置位数的算法是什么?
当前回答
另一个汉明权重算法,如果你使用的是BMI2 CPU:
the_weight = __tzcnt_u64(~_pext_u64(data[i], data[i]));
其他回答
你可以使用内置函数__builtin_popcount()。c++中没有__builtin_popcount,但它是GCC编译器的内置函数。这个函数返回一个整数中的设置位数。
int __builtin_popcount (unsigned int x);
参考:Bit Twiddling Hacks
32位还是32位?我只是在阅读了“破解编码面试”第4版练习5.5(第5章:位操作)后,在Java中使用了这种方法。如果最小有效位是1个增量计数,则右移该整数。
public static int bitCount( int n){
int count = 0;
for (int i=n; i!=0; i = i >> 1){
count += i & 1;
}
return count;
}
我认为这个比常数0x33333333的解更直观,不管它们有多快。这取决于你对“最佳算法”的定义。
在Java 8或9中只调用Integer。bitCount。
这也可以正常工作:
int ans = 0;
while(num) {
ans += (num & 1);
num = num >> 1;
}
return ans;
当你写出比特模式时,“黑客的喜悦”比特旋转变得更加清晰。
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。