Some Trics in Coding Practice

1

题目

输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。

思路

很容易想到一个会引起死循环的方法:

1
2
3
4
5
6
7
8
int (int n){
int cnt = 0;
while(n){
if(n&1) cnt++;
n >>= 1;
}
return cnt;
}

原因是负数的移位最高位总是1。
一个非常巧妙的思路是:
把一个整数 (无论正负或0)减去1,再和原整数做与运算,会把该整数最右边的一个1变为0,例如:110100减1后变为110011,二者进行与操作后,得到110000,最后边的1变为了0,而前面的位都不变。
这样,我们可以利用这这一结论来从左向右依次将整数的最右边的1变为0,当该整数的所有位为1的位均变为0之后,便统计到了该整数二进制中1的个数。

代码

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

参考

https://blog.csdn.net/ns_code/article/details/25425577