统计二进制数中1的个数

发表于 | 分类于

循环减一按位与

介绍

执行速度较快,易理解;

算法

  • 对于 n,若n不为 0,则进行以下循环,每进行一次循环,统计循环次数 c
  • 将 n 与 (n-1) 的按位与赋值给 n
  • 循环结束,循环次数 c 即为所求

    解释

    每次循环将消去二进制数 n 的一个最低位 1

    C++代码

1
2
3
4
5
6
7
8
9
10
int bitCount(unsigned long long n)
{
	int c=0;
	while(n)
	{
		n=n&(n-1);
		++c;
	}
	return c;
}

分组统计

介绍

代码简洁,理解稍难

算法

  • 将整数 n 按二进制分为 m 组,每组包含 4 个二进制位

  • 对于每组,计算 1 的个数 e

  • 然后计算 e[1]-e[m] 的和 eSum

    解释

  • e的计算

    假设按照从高到低的顺序,各二进制的值分别为 a,b,c,d,即,a为最高位,d为最低位
    设每组的值为 v,则 v=8a+4b+2c+d
    设每组所含的1的个数为 e,则 e=a+b+c+d=(8    a+4b+2c+d)-(4a+2b+2c)-(2a+2*b)-a=v-v/2-v/4-v/8

  • eSum的计算

    使用公式 (2^p*x) mod (2^p-1)=x mod (2^p-1)
    计算出来的 eSum 是小于 2^p-1 的,所以需要适时的调整 p 的大小

    C++代码

    1
    2
    3
    4
    5
    6
    7
    8
    int bitCount(const unsigned long long n)
    {
        int x;
        x=n-((n>>1)&0x7777777777777777)
            -((n>>2)&0x3333333333333333)
            -((n>>3)&0x1111111111111111);
        return (int)((x+(x>>4))&0x0f0f0f0f0f0f0f0f)%255;
    }

C++ bitset对象

介绍

使用最为简单,需要导入 bitset 头文件

C++代码

1
2
3
4
5
#include<bitset>
int bitCount(const unsigned long long n)
{
	return bitset<64>(n).count();
}

References : 算法-求二进制数中1的个数