《剑指 offer》刷题记录之八：位运算

本篇博客为《剑指 offer》一书的刷题笔记（第八部分）。

位运算是把数字用二进制表示之后，对每一位上 0 或者 1 的运算。位运算总共包括以下 5 种：

• 与
• 或
• 异或
• 左移
• 右移

前三种这里不做介绍，关于左移和右移，对于正数来说，移位后左侧或右侧补 0 即可，而对于负数来说，右移时需要在左边补 1（因为最高位为符号位），java 提供了无符号右移（>>>），可以在对负数进行右移时在左边补 0。

面试题 15：二进制中 1 的个数

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

示例

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

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

思路及代码

这道题我们首先可以想到的一种思路是：判断整数二进制表示中最右边一位是不是 1；接着把输入的整数右移一位，再判断是不是 1，以此类推，直到整数变为 0。而判断的方式是将该整数和 1 做位与运算即可。需要注意，上述方法在整数为负数时不适用，因为右边会补 1 而不是 0，这时 java 可以使用无符号右移来进行解决，python 并没有提供这个操作符（python 虽然无位数限制，但是负数的移位还是遵循有位数限制的补码系统来的）。此外，对于正数来说，右移操作和除以 2 等价，但是除法的效率远远低于移位运算。

上述解法的 java 实现如下：

public class Solution {
    public int hammingWeight(int n) {
        int ans = 0;
        while (n != 0) {
            ans += n & 1;
            n >>>= 1; // 无符号右移
        }
        return ans;
    }
}

比较迷的是，LeetCode 上关于 python 使用常规右移也可以通过，但 java 不行，可能是 python 的测试用例中没有负数。上述方法的时间复杂度与数字最高位 1 所在的位数线性相关，空间复杂度为 \(O(1)\)。

第二种思路是对于整数不做移位操作，而是将 1 左移，去和整数的每一位进行比较。该方法的 java 实现如下：

public class Solution {
    public int hammingWeight(int n) {
        int ans = 0;
        int flag = 1;
        while (flag != 0) {
            if ((n & flag) != 0) { // 注意用括号保证优先级
                ans++;
            }
            flag <<= 1;
            if (n > 0 && flag > n) break; // 对于正数可以减少循环次数
        }
        return ans;
    }
}

注意 python 由于没有位数限制，所以上述方法并不适用。该方法的循环次数为 flag 的位数（有时不用）。

第三种思路利用了位运算中很常用的一个性质（证明略）：

把一个整数减去 1 之后再和原来的整数做位与运算，得到的结果相当于把整数的二进制表示中最右边的 1 变成 0。

该性质对于正数适用，对于负数来说需要有位数限制（保证在只有符号位为 1 时再减 1 符号位翻转以得到 0 结束循环），因此 python 实际上是不适用的（这道题 python 没有设置负数的测试用例，所以可以通过）。基于上述方法的 java 实现如下：

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

该方法的时间复杂度与整数二进制表示中 1 的位数线性相关。