跳到主要内容

位运算

位运算题目通过异或 (XOR)、按位与 (&) 和偏移 (<<, >>) 在 O(1)O(1) 或 O(32)O(32) 的空间复杂度下解决问题。

67. 二进制求和 (Add Binary)​

题目描述​

给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。

解题思路​

逐位相加进位逻辑。

  1. 使用双指针从字符串末尾开始向前遍历。
  2. 累加字符值并加上进位 carry = sum / 2。
  3. 记录当前的位 sum % 2 放入 StringBuilder。
  4. 最后翻转 StringBuilder。

Java 代码实现​

class Solution {
    public String addBinary(String a, String b) {
        StringBuilder sb = new StringBuilder();
        int i = a.length() - 1, j = b.length() - 1, carry = 0;
        while (i >= 0 || j >= 0 || carry > 0) {
            int x = (i >= 0) ? a.charAt(i--) - '0' : 0;
            int y = (j >= 0) ? b.charAt(j--) - '0' : 0;
            int sum = x + y + carry;
            sb.append(sum % 2);
            carry = sum / 2;
        }
        return sb.reverse().toString();
    }
}

190. 颠倒二进制位 (Reverse Bits)​

题目描述​

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

提示：

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

解题思路​

循环偏移 + 按位或。

  1. 循环 32 次。
  2. 将结果 res 左移一位。
  3. 将输入 n 的最后一位 n & 1 加到 res 中。
  4. 将 n 右移一位 n >>> 1（无符号右移）。

Java 代码实现​

public class Solution {
    public int reverseBits(int n) {
        int res = 0;
        for (int i = 0; i < 32; i++) {
            res = (res << 1) | (n & 1);
            n >>>= 1;
        }
        return res;
    }
}

191. 位 1 的个数 (Number of 1 Bits)​

题目描述​

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

解题思路​

巧妙消除法：n & (n - 1)。

  1. 进行 n = n & (n - 1) 操作，会消去当前二进制表示中最后面的一位 1。
  2. 循环直到 n == 0。
  3. 循环次数即为 1 的个数。

Java 代码实现​

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

136. 只出现一次的数字 (Single Number)​

题目描述​

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

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

解题思路​

异或 (XOR) 特性。

  • a ^ 0 = a
  • a ^ a = 0
  • a ^ b ^ a = b
  1. 遍历数组，对所有元素进行异或。
  2. 所有重复两次的元素将抵消。
  3. 剩下的值即为只出现一次的数字。

Java 代码实现​

class Solution {
    public int singleNumber(int[] nums) {
        int res = 0;
        for (int x : nums) res ^= x;
        return res;
    }
}

137. 只出现一次的数字 II (Single Number II)​

题目描述​

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

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

解题思路​

逐位统计模 3。

  1. 遍历 32 个比特位（从 0 到 31）。
  2. 对于每一位，遍历数组，统计该位上 1 出现的总次数。
  3. 如果次数不能被 3 整除，说明只出现一次的那个数字在该位上是 1。
  4. 将这些位还原到结果中。

Java 代码实现​

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

201. 数字范围按位与 (Bitwise AND of Numbers Range)​

题目描述​

给你两个整数 left 和 right ，表示区间 [left, right] ，返回此区间内所有数字 按位与 的结果（包含 left 、right 端点）。

解题思路​

公共前缀查找。

  1. 只要 left < right，其二进制表示的低位在递增过程中必然会出现 0。
  2. 因此，区间内所有数字按位与的结果，其实就是 left 和 right 的 最长公共二进制前缀。
  3. 将两者同时右移，直到相等，计数移动步数 shift。
  4. 返回 left << shift。

Java 代码实现​

class Solution {
    public int rangeBitwiseAnd(int left, int right) {
        int shift = 0;
        while (left < right) {
            left >>= 1;
            right >>= 1;
            shift++;
        }
        return left << shift;
    }
}