代表数字7的8位像这样:
00000111
设置了三个比特。
确定32位整数中设置位数的算法是什么?
代表数字7的8位像这样:
00000111
设置了三个比特。
确定32位整数中设置位数的算法是什么?
当前回答
这也可以正常工作:
int ans = 0;
while(num) {
ans += (num & 1);
num = num >> 1;
}
return ans;
其他回答
天真的解决方案
时间复杂度为O(no。n的比特数)
int countSet(unsigned int n)
{
int res=0;
while(n!=0){
res += (n&1);
n >>= 1; // logical right shift, like C unsigned or Java >>>
}
return res;
}
Brian Kerningam的算法
时间复杂度为O(n中设置位的个数)
int countSet(unsigned int n)
{
int res=0;
while(n != 0)
{
n = (n & (n-1));
res++;
}
return res;
}
32位数字的查找表方法-在这种方法中,我们将32位数字分解为4个8位数字的块
时间复杂度为O(1)
static unsigned char table[256]; /* the table size is 256,
the number of values i&0xFF (8 bits) can have */
void initialize() //holds the number of set bits from 0 to 255
{
table[0]=0;
for(unsigned int i=1;i<256;i++)
table[i]=(i&1)+table[i>>1];
}
int countSet(unsigned int n)
{
// 0xff is hexadecimal representation of 8 set bits.
int res=table[n & 0xff];
n=n>>8;
res=res+ table[n & 0xff];
n=n>>8;
res=res+ table[n & 0xff];
n=n>>8;
res=res+ table[n & 0xff];
return res;
}
以二进制表示计数集位(N):
伪代码,
设置counter = 0。 重复计数,直到N不为零。 检查最后一点。 如果最后一位= 1,则递增计数器 丢弃N的最后一位。
现在让我们用c++编写代码
int countSetBits(unsigned int n){
int count = 0;
while(n!=0){
count += n&1;
n = n >>1;
}
return count;
}
我们用这个函数。
int main(){
int x = 5;
cout<<countSetBits(x);
return 0;
}
输出:2
因为5有2位二进制表示(101)。
您可以在这里运行代码。
另一个汉明权重算法,如果你使用的是BMI2 CPU:
the_weight = __tzcnt_u64(~_pext_u64(data[i], data[i]));
当你写出比特模式时,“黑客的喜悦”比特旋转变得更加清晰。
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 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位操作,它也比较慢,并且没有很好地优化。