判断一个整数的二进制位中有多少个1

// 判断一个整数的二进制位中有多少个1<br/> void totalOne(int x)<br/> {<br/> int count = 0;

while(x)
{
x = x & ( x - 1 );
count++;
}
printf("count = %d/n", count);
}

循环： x = x & ( x - 1 ); count++; 直到x为0为止。该方法的时间复杂度是O(m)

在此，不妨把x的二进制位表示为
x=a_n-1a_n-2...a_0。
按从低位到高位的顺序，不失一般性，假设x的第i位为第一个为1的二进制位，即：a_i=1。此时有：
x =a_n-1a_n-2...a_i+1100...0 <1>
(x-1) =a_n-1a_n-2...a_i+1011...1 <2>
很明显，从式1和式2可以得出，在第一次 x & (x-1) 后：
x=a_n-1a_n-2...a_i+1000...0
之后重复同样操作，直到x的二进制位中没有1为止
从上面可以看出，每执行过一次 x & (x-1) 后，都会将x的二进制位中为1的最低位的值变为0，并记数加1。
目前而言，一个整数最大64bit，所有三种方法执行起来都可以认为是0(1)。

如何判断整数x的二进制中含有多少个1

 主要是利用位操作来判断每一位是否为1

方法一：

清除整数a最右边的1可以使用这个操作：a&(a-1)

 所以可以利用这个方法来得到1的个数：

int count_one(unsigned x){
    int count=0;
    while(x){
        count++;
        x=x&(x-1);
    }
    return count;
}

方法二：

对整数进行移位，然后判断最后一位是否为1

int count_one2(unsigned x){
    int count=0;
    int i=0;
    while(i<32){
        if((x>>i)&0x1)
            count++;
        i++;
    }
    return count;
}

方法三：

这个方法和方法二类似，只是每次移动4位。

int count_one3(unsigned x){
    static const int hex[]={0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4};
    int count=0;
    int i=0;
    while(i<8){
        count+=hex[(x>>(i*4))&0xf];
        i++;
    }
    return count;

}

下面是测试程序：

int main(){
    int n=20;
    for(int i=0;i<n;i++){
        unsigned val=rand()%100;
        int c1=count_one(val);
        int c2=count_one2(val);
        int c3=count_one3(val);
        cout<<val<<" "<<c1<<" "<<c2<<" "<<c3<<endl;
    }
}

 具体执行结果如下：