题目:请实现一个函数,输入一个整数,输出该数二进制表示中1的个数。例如把9表示成二进制是1001,有2位是1。因此如果输入9,该函数输出2。
在线测试平台:http://ac.jobdu.com/problem.php?pid=1513
对于上面的题目,显然我们直接对整数的二进制形式进行位操作要比直接对整数进行运算要简单的多。 先看一下,整数的左移与右移操作知识:
左移运算符m<<n表示把m左移n位。左移n位的时候,最左边的n位将被丢弃,同时在最右边补上n个0。
右移运算符m>>n表示把m右移n位。右移n位的时候,最右边的n位将被丢弃。处理左边位的情形要考虑以下的情形:
- 数字是无符号数值,则用0填补最左边的n位。
- 数字是有符号整数,则用数字的符号位填补最左边的n位,即:
- 数字是正数,左边补n个0
- 数字是负数,左边补n个1
继续分析题目,上面的题目可以进一步理解为要数数字所占内存中1的个数。我们在做位运算时,经常用掩码的方法来判断数字的第n位是否为1。在此题中我们可以利用这种掩码的方式,来判断数字的每一位是否为1,为1则计数加1。
我们利用1作为掩码判断数字的最低位是否为1,然后不断的右移数字,直到数字为0即可。但是要注意的是如果该树是负数在右移时左侧会填1这样就会使程序陷入死循环。
所以需要针对负数做特殊处理,我们需要把负数的最高位置零(不要天真地以为num = -num就可以了,因为最高位置零后得到的数并不是-num)。
下面是实现算法:
int numOf1(int num)
{
int count = 0;
if(num < 0){
//把num的最高位拉低
unsigned int temp = 1<<(sizeof(num)*8 - 1);
temp = ~temp;
num &= temp;
count++;
}
while(num){
if(num & 1)
count++;
num = num >> 1;
}
return count;
}
当然左移数字的方法也是可以的,貌似左移就不用考虑负数,更加简单了。
与第一种方法,大同小异,既然可以移动数字来判断每位是否为1,当以也可以靠移动掩码来实现:
int numOf1_2(int num)
{
int count = 0;
unsigned int mask = 1;
while(mask){
if(num & mask)
count++;
mask = mask << 1;
}
return count;
}
我们如果把一个整数减1,则会使该数最右边的1变为0。如果他右边还有0的话,所有0都变为1,而它左侧数位都保持不变,这个效果相当于从该数最右边的1开始逐位取反。我们将这个减过1的数再与原数相遇,则原来最右边1的左侧的数仍然保持不变,从最右边的1开始全变为0。
这样只要我们进行一次num & (num-1)
操作,就会就num最右边的一个1变为0。如果有n个1则进行n次操作后num就会变为0。
实现代码很简单:
int numOf1_3(int num)
{
int count = 0;
while(num){
count ++;
num = (num - 1) & num;
}
return count;
}
根据上面的左移、右移操作,我们可以得到结论:
整数右移一位相等于整数除以2,右移n位相当于除以2^n
(注意:左移没有相应的结论哦!!)
在实际编程中尽可能地利用右移去代替除法,这样会使效率提升很多
还要注意的是上面的的右移操作对负数除法也成立,但与c语言的/
的定义不同。这是因为负数的除法在定义时就有歧义,参见维基百科中的说法:
移位操作实际上是第一种定义,而C自带的操作\
和%
是第二种定义。
(例如-7除以2,右移操作得到的结果是-4,而/
得到的结果是-3
,%
得到的结果是-1)。