二进制中1的个数

实验代码：

#include<iostream>
#include<cmath>
using namespace std;

//移位+计算
int bitcount1(unsigned int n)
{
    unsigned int c=0;
    while(n){
        if(n & 1) ++c;
        n >>= 1;
    }
    return c;
}

int bitcount2(unsigned int n)
{
    unsigned int c=0;
    for(c=0;n;n>>=1){
        c+= n&1;
    }
    return c;
}

//适用于无符号、有符号整数
int bitcount3(int n)
{
    int c=0;
    unsigned int flag=1;
    while(flag!=0){
        if(n & flag) ++c;
        flag <<=1;
    }
    return c;
}

//快速法
/*
这种方法速度比较快，其运算次数与输入n的大小无关，只与n中1的个数有关。如果n的二进制
表示中有k个1，那么这个方法只需要循环k次即可。其原理是不断清除n的二进制表示中最右边
的1，同时累加计数器，直至n为0。
为什么n &= (n – 1)能清除最右边的1呢？因为从二进制的角度讲，n相当于在n - 1的最低位
加上1。举个例子，8（1000）=7（0111）+ 1（0001），所以8&7 =（1000）&（0111）= 0（0000），
清除了8最右边的1（其实就是最高位的1，因为8的二进制中只有一个1）。再比如
7（0111）= 6（0110）+ 1（0001），所以7 & 6 = （0111）&（0110）= 6（0110），
清除了7的二进制表示中最右边的1（也就是最低位的1）。
*/
int bitcount4(unsigned int n)
{
    unsigned int c=0;
    for(c=0;n;++c){
        n &= (n-1);
    }
    return c;
}

//查表法
/*分两部分：
1. 运行过程中动态建表；
2. 查表；
填表原理很巧妙，根据奇偶来分析，如下：
1）对于偶数n，n的二进制中1的个数与n/2的二进制中1的个数相同，因为n就是n/2向左移一位得到的，移位并不会增加1的个数；
2）对于奇数n，n的二进制中1的个数就是n/2中1的个数+1，因为奇数n相当于n/2左移一位再+1得到；

查表原理
对于任意一个32位无符号整数，将其分隔位4部分，每部分8bit，对每一部分分别求出1的个数，再累加起来就可以了。
每一部分8bit，对应256中0、1组合，所以表的大小为256.

类型转换：这里不能用传统的类型转换方式，要先取地址再转换为对应的指针类型
先取到n的地址，然后转换为unsigned char*，这样一个unsigned int(4 bytes)对应4个unsigned char(1 bytes).
*/
int bitcount5(unsigned int n)
{
    unsigned int c;
    unsigned char BitSetTable256[256]={0};
    for(int i=0;i<256;++i){
        BitSetTable256[i]= (i&1) + BitSetTable256[i/2];
    }
    unsigned char* p=(unsigned char*)(&n);
    c = BitSetTable256[p[0]]+
        BitSetTable256[p[1]]+
        BitSetTable256[p[2]]+
        BitSetTable256[p[3]];
    return c;
}

//静态表-4bit
int bitcount6(unsigned int n)
{
    unsigned int BitSetTable16[16]={
        0,1,1,2,
        1,2,2,3,
        1,2,2,3,
        2,3,3,4
    };
    unsigned int c=0;
    while(n){
        c += BitSetTable16[n&0xf];
        n>>=4;
    }
    return c;
}

int main(int argc,char **argv)
{
    unsigned int num=2147483647;
    unsigned int r=bitcount1(num);
    cout<<r<<endl;

    int n=-1;
    r=bitcount2(n);
    cout<<r<<endl;

    int m=2147483647;
    r=bitcount3(m);
    cout<<r<<endl;

    r=bitcount4(m);
    cout<<r<<endl;

    r=bitcount5(m);
    cout<<r<<endl;

    r=bitcount6(m);
    cout<<r<<endl;


    return 0;
}