c++ - 二进制中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)