今天的刷题日记是位运算专辑。位运算可以有效提高运算速度，当然它也是比较难掌握的，知道位运算、知道怎么用位运算、能在算法题中灵活用位运算，是完全不同的三件事情。

lc190. 颠倒二进制位（EZ）

颠倒给定的 32 位无符号整数的二进制位。

提示：

  • 请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
  • 在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在 示例 2 中，输入表示有符号整数 -3，输出表示有符号整数 -1073741825。

示例 1：

输入：n = 00000010100101000001111010011100
输出：964176192 (00111001011110000010100101000000)
解释：输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596，
     因此返回 964176192，其二进制表示形式为 00111001011110000010100101000000。

示例 2：

输入：n = 11111111111111111111111111111101
输出：3221225471 (10111111111111111111111111111111)
解释：输入的二进制串 11111111111111111111111111111101 表示无符号整数 4294967293，
     因此返回 3221225471 其二进制表示形式为 10111111111111111111111111111111 。

提示：

  • 输入是一个长度为 32 的二进制字符串

进阶: 如果多次调用这个函数，你将如何优化你的算法？

将 n 视作一个长为 32 的二进制串，从低位往高位枚举 n 的每一位，将其倒序添加到翻转结果 rev 中。

代码实现中，每枚举一位就将 n 右移一位，这样当前 n 的最低位就是我们要枚举的比特位。当 n 为 0 时即可结束循环。

public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        int rev = 0;
        for (int i = 0; i < 32 && n != 0; i++) {
            rev |= (n & 1) << (31 - i);
            n >>>= 1;
        }
        return rev;
    }
}

lc191. 位1的个数（EZ）

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中 设置位 的个数（也被称为汉明重量）。

示例 1：

输入：n = 11
输出：3
解释：输入的二进制串 1011 中，共有 3 个设置位。

示例 2：

输入：n = 128
输出：1
解释：输入的二进制串 10000000 中，共有 1 个设置位。

示例 3：

输入：n = 2147483645
输出：30
解释：输入的二进制串 11111111111111111111111111111101 中，共有 30 个设置位。

提示：

  • 1 <= n <= 2^31 - 1

进阶：

  • 如果多次调用这个函数，你将如何优化你的算法？

通过让当前的 n 和 n - 1做与运算，直到 n 变成 0 为止，因为每次运算都会使得 n 的最低位的 1 被反转，运算次数就是 n 二进制位中 1 的个数

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

lc136. 只出现一次的数字（EZ）

给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

示例 1 ：

输入：nums = [2,2,1]
输出：1

示例 2 ：

输入：nums = [4,1,2,1,2]
输出：4

示例 3 ：

输入：nums = [1]
输出：1

提示：

  • 1 <= nums.length <= 3 * 10^4
  • -3 * 10^4 <= nums[i] <= 3 * 10^4
  • 除了某个元素只出现一次以外，其余每个元素均出现两次。

首先介绍位运算中”异或运算“的三个性质

  • 任何数和 0 做异或运算，其结果都是它本身。即a⊕0=aa⊕0=a
  • 任何数和它本身做异或运算，其结果是0。即a⊕a=0a⊕a = 0
  • 异或运算满足交换律和结合律，即a⊕b⊕a=b⊕a⊕a=b⊕(a⊕a)=b⊕0=ba⊕b⊕a=b⊕a⊕a=b⊕(a⊕a)=b⊕0 = b

根据本题给出的一个提示：除了某个元素只出现1次，其他元素均出现了两次。那么根据上面提到的三个性质，我们可知：除了我们要找出来的元素，其他的元素全部做异或运算，结果是 0，因为除了我们要找出来的元素，其他元素都出现了两次；而 0 和 一个非 0 值做异或运算，结果是原来这个非 0 值本身

class Solution {
    public int singleNumber(int[] nums) {
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            res ^= nums[i];
        }
        return res;
    }
}

lc137. 只出现一次的数字 II（MD）

给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 **三次 。**请你找出并返回那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。

示例 1：

输入：nums = [2,2,3,2]
输出：3

示例 2：

输入：nums = [0,1,0,1,0,1,99]
输出：99

提示：

  • 1 <= nums.length <= 3 * 10^4
  • -2^31 <= nums[i] <= 2^31 - 1
  • nums 中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次

这道题和上一题的区别在于重复元素的个数——重复元素的个数不再是2个，而是3个。这样的话就不能再用上面提到的异或运算来判断了

因为数组中的元素都在 int 范围内，所以可以依次计算要找出的元素的每个二进制位是 0 还是 1

具体来讲，考虑要找出元素的第ii 个二进制位（ii 从 0 开始编号），它可能是 0 或者 1。对于数组中非答案的元素， 每一个元素都出现了 3 次， 对应着 第ii 个二进制位的 3 个 0 或者 3 个 1， 无论是哪种情况，它们的和都是 3 的倍数。因此，要找出的元素的第ii 个二进制位就是数组中所有元素的第ii 个二进制位之和除以 3 的余数

这样的话，对于数组中的每一个元素xx ，使用位运算(x>>i)&i(x >> i) \& i 得到xx 的第ii 个二进制位，并将它们相加再对 3 取余，得到的结果一定是 0 或 1，即为要找出元素的第ii 个二进制位

class Solution {
    public int singleNumber(int[] nums) {
        int res = 0;
        for (int i = 0; i < 32; i++) {
            int total = 0;
            for (int j = 0; j < nums.length; j++) {
                total += ((nums[j] >> i) & 1);
            }
            if (total % 3 != 0) {
                res |= (1 << i);
            }
        }
        return res;
    }
}