解码二进制中1的数量：剑指Offer第11题剖析

题目阐述

给定一个整数，需要输出该整数对应的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取余数的方式来统计。但这种方法存在一个严重问题，就是没有考虑负数的情况，因为负数在以补码形式表示时，是先取反再加1的。

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'的数量。

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

• 时间复杂度：O(n)，这里的n指的是二进制的位数，由于固定为32位，所以时间复杂度是固定的。
• 空间复杂度：O(n)，因为需要存储二进制字符串。

API调用法（不推荐）

Java的标准库中其实有直接统计二进制中1的个数的方法。

public int hammingWeight(int n) {
    return Integer.bitCount(n);
}

位掩码与移位（逐位检查）

可以利用位掩码和移位操作来逐位检查是否为1。具体来说，我们可以将一个掩码初始化为1，然后通过循环32次，每次将n与掩码进行与运算，如果结果不为0，说明当前位是1，就将计数加1，然后将掩码左移一位。

public int NumberOf1(int n) {
    int count = 0;
    int mask = 1;
    for (int i = 0; i < 32; i++) {
        if ((n & mask) != 0) {
            count++;
        }
        mask <<= 1;
    }
    return count;
}

还可以使用无符号右移的方式，不断将n右移，然后每次与1进行与运算，统计结果为1的次数。

public int NumberOf1(int n) {
    int count = 0;
    while (n != 0) {
        count += (n & 1);
        n >>>= 1; // 无符号右移
    }
    return count;
}

位运算优化法

利用n & (n - 1)的特性，这个操作可以消除n最右边的那个1。我们可以不断地执行这个操作，直到n变为0，每执行一次就计数一次。例如，7的二进制是111，7&6等于111&110=110也就是6，这样就把最右边的1去掉了。再比如6的二进制是110，6&5等于110&101=100也就是4，同样去掉了最右边的1。对于负数也是适用的。

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