JZ11 — 二进制中1的个数

题目描述

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

题目分析

很多同学看到这个问题第一眼想到的是除K取余法进行进制转换。但题目要求负数使用补码来表示，这就需要我们手动将原码转成补码，虽然可以解决这个问题，但并不优雅。

原码：将一个整数，转换成二进制，就是其原码。如单字节的5的原码为：0000 0101；-5的原码为1000 0101。
反码：正数的原码反码补码相同；负数的反码是将原码中，除符号位以外，每一位取反。如单字节的5的反码为：0000 0101；-5的反码为1111 1010。
补码：正数的原码反码补码相同；负数的反码加一就是补码。如单字节的5的补码为：0000 0101；-5的原码为1111 1011。

解法一

写过快速幂算法的同学应该都知道，可以通过位运算快速判断每一位是否是1。而计算机中整数恰好是使用补码来存储的，因此也无须考虑正负数的问题，直接使用位运算即可。
代码如下：

int NumberOf1(int n)
{
    int ans = 0;
    while (n)
    {
        if (n & 1)
            ans++;
        n >>= 1;
    }
    return ans;
}

但这种经典写法其实是存在问题的。
对于负数来说，符号位为1，右移之后符号位还是1，例如-8>>2即11111000右移两位后为11111110。
所以当n为负数时，while (n)这个循环永远也不会结束。
怎么解决这个问题吗？
我们可以不对n进行位移运算，而是对1进行位移运算。例如n & 1用来判断最右1位是否为1，n & 10用来判断自右向左第2位是否为1。
代码如下：

int NumberOf1(int n)
{
    int ans = 0;
    int base = 1;
    while (base)
    {
        if (n & base)
            ans++;
        base <<= 1;
    }
    return ans;
}

假设int是4个字节，则base在位移32次后会变为0，此时会退出循环。

解法二

在二进制中，有如下结论：
1. n-1可以使n中最右的1变为0，且此位置右边全部由0变为1，例如110100 - 1 = 110011；
2. n & (n-1)可以使n中最右的1变为0，其他位置不变，例如110100 & (110100 - 1) = 110100 & 110011 = 110000

即每执行一次n = n & (n-1)，n就会少一个1，直到n全部为0
因此有代码如下：

int NumberOf1(int n)
{
    int ans = 0;
    while (n)
    {
        n &= n - 1;
        ans++;
    }
    return ans;
}

循环执行次数就是答案的次数。

C++

class Solution
{
public:
    int NumberOf1(int n)
    {
        int ans = 0;
        int base = 1;
        while (base)
        {
            if (n & base)
                ans++;
            base <<= 1;
        }
        return ans;
    }
};

Java

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

What`s more

在解法一中我们说过，经典的向右位移操作，对于负数来说是错误的，因为负数在右移的时候高位会自动补为1.
在Java中除了普通的位移操作>>和<<，还有一种无符号右移操作>>>，对负数进行无符号位移就不会自动在高位补1了。（Java没有无符号左移操作，因为和普通左移没区别）
因此，如果使用Java语言，只要将>>改为>>>，使用解法一中给出的第一种代码也是OK的。

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