求二进制数中1的个数

Question

编程之美中的一道题,有一个解法想不明白 该算法只考虑1的个数 代码如下:

int Count(BYTE v)
{
    int num = 0;
    while(v)
    {
        v &= (v-1);
        num++;
    }
    return num;
}

在网上看了一下都只是把算法给出来都没有解释,哪位同学帮忙解释一下,想不明白.多谢

Answer 1

算法里面v &= (v-1);这一句的含义就是将二进制中最右边的一个1去掉
去掉一次num增加1

比如：
v=13 二进制1101
v-1=12 二进制1100
相与结果为 1100
v-1=11 二进制 1011
相与结果为 1000
v-1=7 二进制 0111
相与结果为 0000
就退出循环

每次相与后都是去掉最右边的一个1

Answer 2

其实就是简单的位运算啊，给你写个更好理解的

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    int n, count;

    while (scanf("%d", &n) != EOF) {
        count = 0;
        while (n) {
            if (n & 1)  count ++;
            n >>= 1;
        }
        printf("%d\n", count);
    }

    return 0;
}

Answer 3

百度了一下这里讲的不少百度文库，你贴出来的这一段代码“v &= (v-1);”这一句效果很明显的，二进制的数多用位操作。

Answer 4

v-1 是把v最右边的1变成0，然后把后边的0全部变成1

v &= (v-1) 就是消去了v最右边的1

如此多次，每次消去一个1，并计数，直到v变成0（即v不再含有1的位）。 最后就得到了v中1的个数。

Answer 5