剑指Offer-二进制中1的个数

发表于 | 分类于

题目描述

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

解题思路

我一开始的方法是最蠢笨的，即将整数表示为二进制位数，再依次数其中1的个数。由于负数是用补码表示的，因此负数这个情况花了不少时间。特别是最后有个特例始终过不了，只能添加了一个if判断语句，这才通过。蠢笨代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
public:
    int NumberOf1(int n){
        if(n == 0) return 0;
        else if(n > 0){ // 正数
            int cnt = 0, temp1 = n, temp2 = 0;
            while(temp1 != 0){
                temp2 = temp1 % 2;
                temp1 = temp1 / 2;
                if(temp2 == 1) cnt++;
            }
            return cnt;
        }
        else{ // 负数
            if(n == -2147483648) return 1;
            else{
                int cnt = 0, temp1 = abs(n), temp2 = 0;
                int num[32]; int i=0;
                while(temp1 != 0){
                    temp2 = temp1 % 2;
                    temp1 = temp1 / 2;
                    // 取反
                    if(temp2 == 1) num[i] = 0;
                    else num[i] = 1;
                    i++;
                }
                // 加1
                int n = i;
                for(int j=n; j<32; j++) num[j] = 1;
                i = 1;
                if(num[0] == 0) num[0] = 1;
                else{
                    num[0] = 0; 
                    while(num[i] != 0){
                        num[i] = 0;
                        i++;
                    }
                    if(i <= n-1) num[i] = 1;
                }
                for(int i=0; i<32; i++){
                    if(num[i] == 1) cnt++;
                }
                return cnt;
            }
        }
    }
}

另外，其实还有一个问题是，整数为int型，这种做法还得考虑int是32位的。很复杂！！

更简便方法

下面是从牛客看到的一个简单的方法。参考：https://www.nowcoder.com/profile/9536154/codeBookDetail?submissionId=17465787.

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

分析一下代码： 这段小小的代码，很是巧妙。

如果一个整数不为0，那么这个整数至少有一位是1。如果我们把这个整数减1，那么原来处在整数最右边的1就会变为0，原来在1后面的所有的0都会变成1(如果最右边的1后面还有0的话)。其余所有位将不会受到影响。

举个例子：一个二进制数1100，从右边数起第三位是处于最右边的一个1。减去1后，第三位变成0，它后面的两位0变成了1，而前面的1保持不变，因此得到的结果是1011.我们发现减1的结果是把最右边的一个1开始的所有位都取反了。这个时候如果我们再把原来的整数和减去1之后的结果做与运算，从原来整数最右边一个1那一位开始所有位都会变成0。如1100&1011=1000.也就是说，把一个整数减去1，再和原整数做与运算，会把该整数最右边一个1变成0.那么一个整数的二进制有多少个1，就可以进行多少次这样的操作。