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

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


分析

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

方法1:移位

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

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int NumberOf1(int n)
{
int count=0;
while(n)
{
if(n&0x1!=0)
{
count++;
}
n>>=1;
}
return count;
}

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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次。 代码如下:

1
2
3
4
5
6
7
8
9
10
int NubmerOf1(int n)
{
int count=0;
while(n)
{
n&=(n-1);
count++;
}
}

以上

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

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