题目描述

剑指 Offer 15. 二进制中1的个数

难度简单90

请实现一个函数，输入一个整数（以二进制串形式），输出该数二进制表示中 1 的个数。例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。

示例 1：

输入：00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。

示例 2：

输入：00000000000000000000000010000000
输出：1
解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。

示例 3：

输入：11111111111111111111111111111101
输出：31
解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。

测试用例

• 正数（包括边界值1、0x7FFFFFFF）
• 负数（包括边界值0x80000000、0xFFFFFFFF）
• 0

题目考点

• 考察应聘者对二进制及位运算的理解。

解题思路

常规解法

首先把n和1做与运算，判断n的最低位是不是为1，接着把1左移一位得到2，再和n做运算，就能判断n的次低位是不是1…这样反复左移，每次都能判断n的其中一位是不是1。

常规解法

我们基于这样一个事实：把一个整数减去1之后再后原来的整数做位与运算，得到的结果相当于把整数的二进制表示中最右边的1变成0。例子如下：

n       : 10110100
n-1     : 10110011
n&(n-1) : 10110000

那么一个整数的二进制表示中有多少个1，就可以进行多少次这样的操作。

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

自带API解法

Integer.bitCount(n);

补充

位运算只有5中运算：与、或、异或、左移和右移。

与、或、异或运算就是简单的真值表。

左移运算符 m<<n 表示把 m 左移 n 位。在左移 n 位的时候，最左边的 n 位将被丢弃，同时在最右边补上 n 个0.

右移运算符 m>>n 表示把 m 右移 n位。在右移 n 位的时候，最右边的 n 位将被丢弃，但右移时处理最左边位情形有两种情况，如果数字是无符号数字，则用0填补最左边的 n 位；如果数字是一个有符号数值，则用数字的符号位填补最左边的 n 位。也就是说，如果数字原先是一个正数，则右移之后再最左边填补 n 个0；如果数字原先是负数，则右移之后在最左边补 n 个1。

负数的二进制表示（计算机用补码表示负数）

1. 变成原码：将绝对值转换成二进制数，然后在最高位补1
2. 变成反码：对原码除符号位外各位取反
3. 变成补码：在反码最后一位加1

问题： 把整数右移一位和把整数除以2在数学上是等价的吗？

不是，除法的效率比一位运算效率低得多，在实际编程中应尽可能得用一位运算符代替乘除法。

值得注意的地方：

把一个整数减去1之后再后原来的整数做位与运算，得到的结果相当于把整数的二进制表示中最右边的1变成0。 很多二进制问题都可以用这种思路解决。