求二进制数中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