二进制中1的个数

  • 题目描述:

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

  • 解题思路:

该题涉及到数值的二进制表示,利用位运算的一些特性可以更方便得解决问题。
如何将整数转化为二进制数以及如何将负数转化为补码形式是本题的已知条件,我们主要的工作是根据给定的二进制数,找出1的个数。

先来观察一下该题特征:

假如给定一个二进制数m=11010100,我们可以直观得看出该数中1的个数为4,具体解题思路可以参照如下步骤:

  1. 将m减去1, m-1 = 11010011 ,观察 m-1 与 m 的不同,它等价于从数值m最右边的1位置处开始,后面的数值均取反,即 100 => 011
  2. 将 m 与 m-1 按位与运算, m&(m-1) = 11010000 ,我们可以看出经过&运算后,后三位均变为0,此时记录一下1的个数+1
  3. 按照这种方法不断进行:
    11010000 & (11010000-1) = 11000000 1的个数+1
    11000000 & (11000000-1) = 10000000 1的个数+1
    10000000 & (10000000-1) = 00000000 1的个数+1
  4. 每执行一次按位与运算,原数值m会减少一个1,直到数值变为0,此时1的个数为4
  • 源代码:
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
int NumberOf1(int n) {
int count = 0;
while (n!=0) {
n = n & (n-1);
count++;
}
return count;
}
};
-------------The End-------------