c++ - 二进制中1的个数

Question

剑指offer中关于二进制中1的个数有一种解法如下： {代码...} 我有一个疑问，用flag做循环判断，会不会造成无限循环，我用vs2013调试出现无限循环的情况。 个人见解：flag一直为真，而且在左移过程中一直都为真。

天蓬老师 · Answer

A int is usually 32位. At most, move 32次 to the left and then flag becomes 0.

But in other words, shouldn’t this be the way to find a number:

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

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

    return count;
}

阿神 · Answer

Won’t always be true. Repeatedly moving left, there will always be a moment when 1 is moved out.

PHP中文网 · Answer

Tested it in vs2010 SP1 environment and it runs normally.
First of all, if the highest bit is shifted out when performing a left shift, the shifted bits will be discarded, so there will be no infinite loop
Secondly, the writing method of the question is not very efficient and the complexity is full log(n). It is usually written as follows

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

The complexity is O(count), where the sentence n&-n is to extract the lowest bit of 1 in the binary of n, which is basically the same as the writing method of iSayme upstairs;
If there are a large number of calls, the complexity can be further reduced through preprocessing
We use f[i] to represent the number of 1's in the binary of i, and use f[i]=f[i>>1]+(i&1) for preprocessing. The f array only needs to be opened to 65536, and the preprocessing complexity is O(65536)
Just return f[(unsigned)n>>16]+f[n&65535] directly when asking, the complexity is O(1)