面试经典 150 题-位运算

LeetCode 面试经典 150 题-位运算

二进制求和

位运算

逐位相加，标记进位。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public String addBinary(String a, String b) {
        // a是较长字符串
        int m = a.length();
        int n = b.length();
        if (m < n) {
            return addBinary(b, a);
        }
        // 逐位相加
        int carry = 0;
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < m; i++) {
            int sum = (a.charAt(m - i - 1) - '0') + carry;
            if (i < n) {
                sum += (b.charAt(n - i - 1) - '0');
            }
            sb.append(sum % 2);
            carry = sum / 2;
        }
        // 进位
        if (carry != 0) {
            sb.append(carry);
        }

        return sb.reverse().toString();
    }
}
  • 时间复杂度：O(max(m,n))
  • 空间复杂度：O(1)

颠倒二进制位

逐位颠倒

将 n 视作一个长为 32 的二进制串，从低位往高位枚举 n 的每一位，将其倒序添加到翻转结果 rev 中。每枚举一位就将 n 右移一位，这样当前 n 的最低位就是我们要枚举的比特位。当 n 为 0 时即可结束循环。

1
2
3
4
5
6
7
8
9
10
11
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;
    }
}
  • 时间复杂度：O(logn)
  • 空间复杂度：O(1)

位运算分治

若要翻转一个二进制串，可以将其均分成左右两部分，对每部分递归执行翻转操作，然后将左半部分拼在右半部分的后面，即完成了翻转。

由于左右两部分的计算方式是相似的，利用位掩码和位移运算，我们可以自底向上地完成这一分治流程。

  1. 交换相邻的1位
  2. 交换相邻的2位
  3. 交换相邻的4位
  4. 交换相邻的8位
  5. 交换前16位和后16位
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
    // you need treat n as an unsigned value
    private static final int M1 = 0x55555555; // 01010101010101010101010101010101
    private static final int M2 = 0x33333333; // 00110011001100110011001100110011
    private static final int M4 = 0x0f0f0f0f; // 00001111000011110000111100001111
    private static final int M8 = 0x00ff00ff; // 00000000111111110000000011111111

    public int reverseBits(int n) {
        n = n >>> 1 & M1 | (n & M1) << 1;
        n = n >>> 2 & M2 | (n & M2) << 2;
        n = n >>> 4 & M4 | (n & M4) << 4;
        n = n >>> 8 & M8 | (n & M8) << 8;
        return n >>> 16 | n << 16;
    }
}
  • 时间复杂度：O(1)
  • 空间复杂度：O(1)

位1的个数

位运算

不断右移并取最后一位的结果。

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int hammingWeight(int n) {
        int ans = 0;
        while (n != 0) {
            ans += (n & 1);
            n >>>= 1;
        }
        return ans;
    }
}
  • 时间复杂度：O(k)，k是二进制位数。
  • 空间复杂度：O(1)

位运算优化

每次消除最右边的1.

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int hammingWeight(int n) {
        int ans = 0;
        while (n != 0) {
            n &= n - 1;
            ans++;
        }
        return ans;
    }
}
  • 时间复杂度：O(m)，m是1的个数。
  • 空间复杂度：O(1)

只出现一次的数字

位运算

逐个异或，相同的数字异或结果为0，最后的结果就是只出现一次的数字。

1
2
3
4
5
6
7
8
9
class Solution {
    public int singleNumber(int[] nums) {
        int ans = 0;
        for (int i = 0; i < nums.length; i++) {
            ans ^= nums[i];
        }
        return ans;
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

只出现一次的数字II

位运算

根据(0,0)->(0,1)->(1,0)->(0,0)->…，可以看出，如果a为1，则b需要变成0，否则就异或1，按照这个原则可以得出b = (b ^ 1) & ~a；b改变之后，就变成了(0,1)->(0,0)->(1,0)->(0,1)->…，可以看出，如果变化之后的b为1，那么a需要变成0，否则就异或1，这样就得出a = (a ^ 1) & ~b，a改变之后，就变成了(0,1)->(1,0)->(0,0)->(0,1)->…，和第一个流水线相比，向前走了一半，完成了一次变化。以上是x为1的情况，如果x为0，则希望a和b都不变，那么可以把a ^ 1和b ^ 1换成a ^ 0和b ^ 0即a和b，那么原式变成b = b & ~a和a = a & ~b，因为是&操作，所以不存在让a或b从0变成1，所以假设a或b会从1变成0，那么要求a和b都是1才行，但是因为根本不存在(1,1)的情况，所以a和b会保持原来的值，这样就保证了x为0时，a和b不变的条件。综上就是a = (a ^ x) & ~b和b = (b ^ x) & ~a。

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int singleNumber(int[] nums) {
        int a = 0, b = 0;
        for (int num : nums) {
            b = ~a & (b ^ num);
            a = ~b & (a ^ num);
        }
        return b;
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

只出现一次的数字III

位运算

  1. 求所有数字的异或值：如果数组中有两个数字只出现一次，其余每个元素均出现两次。那么经过全部异或运算。我们可以得到只出现一次的两个数字的异或结果。
  2. 找到最低的不同位，找到最低位为1的位置，即最低位的两个数字不相同的位
  3. 根据最低不同位分组：
    • 根据 mask 的位置，将数组中的数字分为两组：一组在 mask 位置上为 0，另一组在 mask 位置上为 1。
    • 因为相同的数字会被分到同一组且异或为0，最终每组剩下的数字就是 a 和 b。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int[] singleNumber(int[] nums) {
        // 得到只出现一次的两个数字的异或结果
        int all = 0;
        for (int i = 0; i < nums.length; i++) {
            all ^= nums[i];
        }
        // 找到两数字最低位的不同
        int mask = 1;
        while ((all & mask) == 0) {
            mask <<= 1;
        }
        // 分组
        int a = 0, b = 0;
        for (int i = 0; i < nums.length; i++) {
            if ((nums[i] & mask) == 0) {
                a ^= nums[i];
            } else {
                b ^= nums[i];
            }
        }
        return new int[]{a, b};
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

数字范围按位与

位运算

每次清除最右边的1.

1
2
3
4
5
6
7
8
class Solution {
    public int rangeBitwiseAnd(int left, int right) {
        while (left < right) {
            right = right & (right - 1);
        }
        return right;
    }
}
  • 时间复杂度：O(logn)
  • 空间复杂度：O(1)

总结

位运算的题目代码实现都不难，但是思路不好想，之后还是把以前刷过的题再好好复习一下。

算法笔记 > 位运算
#位运算
面试经典 150 题-位运算
http://example.com/2025/03/05/posts/hot150-16/
作者
Xuan Yang
发布于
2025年3月5日
许可协议