面试题10:二进制中1的个数

题目:请实现一个函数,输入一个整数,输出该数二进制便是中1的个数。例如把9表示成二进制是1001,有2位是1.因此如果输入9,该函数输出2.

分析

此题考查的是对位运算的掌握,题目不是很难,但一些细节问题还是需要注意的。

方法1:移位

我们把这个数和 0x1 相与,如果结果为 0,则表明该数的最后移位为 0,否则为 1。然后将这个数右移 1 位在此判断,循环 32 次。

代码如下:

int NumberOf1(int n)
{
    int count=0;
    while(n)
    {
        if(n&0x1!=0)
        {
            count++;
        }
        n>>=1;
    }
    return count;
}

以上我们采用了右移来计算 1 的个数。不过当计算机使用逻辑右移的时候,n 最终会变成 0xFFFFFFFF,导致死循环。

对于无符号数,左移和右移都是在相应的位上补 0;而对于有符号数,左移是在最低位补 0,而右移到底是采用算术右移还是逻辑右移,C 标准并没有明确规定。不过大多数机器上使用的是算数右移,所以以上代码可以很好地工作。但你能保证不会遇到例外情况吗?

解决办法就是使用左移,或使 n 不动,移动 1 即可。 代码如下:

int NumberOf1(int n)
{
    int count=0;
    unsigned int flag=1;
    while(flag)
    {
    	if(n & flag)
	{
		count++;
	}
	flag=flag<<1;
    }
    return count;
}

然而更好的解决办法是:

当 n 不为 0 时,n&(n-1) 就相当于去掉了其二进制中的最后一位 1。比如 n 为 9,二进制位 1001,n-1=8,二进制位 1000,两者相与结果为 1000,就相当把 9 的二进制中最后一位 1 给去掉了。

利用上述方法,来计算此题的话,给定数字的二进制中有几位 1 便只需循环几次。而第一种方法每次都要循环 32 次。 代码如下:

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

如果你有任何想法或是可以改进的地方,欢迎和我交流!

完整代码及测试用例在github上:点我前往