题目描述

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

示例1

输入：

10

返回值：

2

说明：

十进制中10的32位二进制表示为0000 0000 0000 0000 0000 0000 0000 1010，其中有两个1。

示例2 输入：

-1

返回值：

32

说明：

负数使用补码表示 ，-1的32位二进制表示为1111 1111 1111 1111 1111 1111 1111 1111，其中32个1   

思路 & 解答

错误解答（不考虑负数）

首先说一个错误的解法，很多人可能会想到，那就是不断对 2 取余数。但是这种做法有个致命的缺陷，那就是忽略了负数，负数使用补码表示的时候，是取反之后加一，而且

public class Solution {
    public int NumberOf1(int n) {
        int num = 0;
        while (n != 0) {
            int tmp = n % 2;
            if (tmp == 1||tmp==-1) ++num;
            n /= 2;
        }
        return num;
    }
}

位移算法

移位算法，把整数当成二进制，不断向右移位和1进行与计算。利用了所有数和1进行与计算，结果为1则证明最后一位是1。 于是我们代码可以写成这样,但是这样也是有问题的！！！：

public class Solution {
    public int NumberOf1(int n) {
        int num=0;
        while (n != 0) {
            if ((n & 1)==1){
                ++num;
            }
            n = n>>1;
        }
        return num;
    }
}

上面代码的问题在于忽略了负数右移，其实第一位还是会补1，所以还是负数。就是说-1其实右移动之后还是-1，这样判断是无效的，而且会死循环。

既然输入的n没办法右移，那么我们把1左移是不是就解决这个问题了呢？是的！

正确代码如下：

public class Solution {
    public int NumberOf1(int n) {
        int num = 0, flag = 1;
        while (flag != 0) {
            if ((n & flag) != 0) {
                num++;
            }
            flag <<= 1;
        }
        return num;
    }
}

除此之外，还有其他做法么？还有一种做法的不断把最右边的1变成0，那就是利用n=n&(n-1)，比如7的二进制是111，那么7&6=111&110=110=6，就完美把最后一位1变成0了，6的二进制是110,6&5=110&101=100=4，也把最后一位1变成了0.

负数可不可以？可以！比如：

32位-7 = 11111111111111111111111111111001 ，
32位-8 = 11111111111111111111111111111000，
-7&-8  = 11111111111111111111111111111000

所以这种思路针对负数也是正确的：

Java 实现代码如下：

public class Solution {
    public int NumberOf1(int n) {
        int num = 0;
        while (n != 0) {
            num++;
            n &= (n - 1);
        }
        return num;
    }
}

C++ 代码如下：

class Solution {
public:
    int NumberOf1(int n) {
        int num = 0;
        while (n != 0) {
            num++;
            n &= (n - 1);
        }
        return num;
    }
};

API调用(不推荐)

还有一种思路那就是直接调用java的api把整数，转成字符串，遍历一次获取1的个数,可以但是不提倡，因为本题考查的是位运算，而不是api使用和for循环。

public class Solution {
    public int NumberOf1(int n) {
        int t = 0;
        String str = Integer.toBinaryString(n);
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == '1') {
                t++;
            }
        }
        return t;
    }
}

C++ 里面也有这样的API,代码实现如下：

#include <iostream>
#include<bitset>
using namespace std;

class Solution {
public:
    int NumberOf1(int n) {
        int t = 0;
        bitset<32> str(n);
        for (int i = 0; i < str.size(); i++) {
            if (str[i] == 1) {
                t++;
            }
        }
        return t;
    }
};