二进制中1的个数

Question

剑指offer中关于二进制中1的个数有一种解法如下：

int NumberOf1_Solution1(int n)
{
    int count = 0;
    unsigned int flag = 1;
    while(flag)
    {
        if(n & flag)
            count ++;

        flag = flag << 1;
    }

    return count;
}

我有一个疑问，用flag做循环判断，会不会造成无限循环，我用vs2013调试出现无限循环的情况。
个人见解：flag一直为真，而且在左移过程中一直都为真。

Answer 1

一个int通常是32位, 最多左移32次后flag就成0了.

不过话说, 求1个数不应该是这样做么:

int NumberOf1_Solution1(int n)
{
    int count = 0;

    while (n) {
        n = n & (n-1);
        count++;
    }

    return count;
}

Answer 2

不会一直为真的。反复左移，总会有把1移出的那一刻。

Answer 3

在vs2010 SP1环境下测试了一下，运行正常。
首先，进行左移的时候如果移出最高位，那么移出的比特位会被舍弃，所以不会死循环
其次，题主的写法效率不高，复杂度是满的log(n)的，通常采用如下写法

cppwhile(n) n-=n&-n,count++;

复杂度为O(count)，其中n&-n一句是取出n的二进制中最低的为1的比特位，和楼上iSayme的写法基本相同；
如果有大量的调用，可以通过预处理来进一步降低复杂度
我们用f[i]表示i的二进制中1的个数，使用f[i]=f[i>>1]+(i&1)进行预处理，f数组只需要开到65536即可，预处理复杂度为O(65536)
询问时直接返回f[(unsigned)n>>16]+f[n&65535]即可，复杂度为O(1)