Question

0 0

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


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

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

10 years, 8 months ago

share

LTsir 10 years, 8 months ago

Answer 1

0

算法里面 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

answered 10 years, 8 months ago

share

Actury answered 10 years, 8 months ago