Skip to content

位运算专题

目录

1. 位运算

位运算简介

位运算是计算机科学中的一种基础运算方式，它直接操作二进制数的位。位运算在处理整数、优化算法、数据压缩等领域具有重要应用。以下是位运算的基本概念、常用操作及应用实例。

1.1 基本概念

在计算机中，整数通常以二进制形式存储。位运算就是通过对这些二进制位进行操作来实现特定的计算。位运算的操作符直接对二进制位进行处理，因此速度非常快，适用于需要高效计算的场合。

1.2 常用位运算操作

按位与（AND）&

对两个整数的每一位执行逻辑与运算。只有当两个相应的位都是1时，结果位才为1，否则为0。

示例：

Text Only
1
2
3
4
5
5 & 3 = 1
5:  0101
3:  0011
--------------
    0001  (结果为1)

按位或（OR）|

对两个整数的每一位执行逻辑或运算。只要其中一个相应的位是1，结果位就为1。

示例：

Text Only
1
2
3
4
5
5 | 3 = 7
5:  0101
3:  0011
--------------
    0111  (结果为7)

按位异或（XOR）^

对两个整数的每一位执行逻辑异或运算。当两个相应的位不同时，结果位为1；相同时为0。

示例：

Text Only
1
2
3
4
5
5 ^ 3 = 6
5:  0101
3:  0011
--------------
    0110  (结果为6)

异或运算的性质：

  • 任何数和 0 进行异或运算，结果为该数本身：a ⊕ 0 = a。
  • 任何数和自己进行异或运算，结果为 0：a ⊕ a = 0。
  • 异或运算满足交换律和结合律：a ⊕ b ⊕ a = (a ⊕ a) ⊕ b = 0 ⊕ b = b。

按位取反（NOT）~

对每一位进行取反操作。0变为1，1变为0。

示例：

Text Only
1
2
3
4
~5 = -6
5:  0101
--------------
    1010  (取反后为-6，使用补码表示法)

左移（<<）

将二进制数的所有位向左移动指定的位数。左移n位相当于乘以 2^n。

示例：

Text Only
1
2
3
4
5 << 1 = 10
5:  0101
--------------
    1010  (结果为10)

右移（>>）

将二进制数的所有位向右移动指定的位数。右移n位相当于整除 (2^n)。

示例：

Text Only
1
2
3
4
5 >> 1 = 2
5:  0101
--------------
    0010  (结果为2)

1.3 应用实例

常见的位运算技巧

位运算可以高效地处理许多问题，特别是在需要操作二进制数字时。以下是一些常用的位运算技巧及其应用：

类型1:用于判断

1. 判断奇偶性

  • 技巧：n & 1
  • 原理：如果 n 是奇数，那么 n 的二进制表示的最低位是 1；如果是偶数，则最低位是 0。因此，n & 1 可以直接判断奇偶性。
  • 代码示例：
Text Only
1
is_odd = (n & 1) == 1

2.清除最低位的 1（判断是否是 2 的幂次方）

  • 技巧：n & (n - 1)

  • 原理：将 n 的二进制表示中的最低位的 1 清除。适用于判断是否为 2 的幂次方，以及统计二进制数中 1 的个数。

  • 代码示例：

Text Only
1
n = n & (n - 1)  # 清除最低位的 1
  • 特性：如果 n 是正整数且满足 n & (n - 1) == 0，这意味着 n 是 2 的幂。

解释：

二进制表示中的 2 的幂

当一个数是 2 的幂时，它的二进制表示中只有一个位是 1，其余所有位都是 0。

  • 比如：
  • 20 = 1 -> 0001 (二进制)
  • 21 = 2 -> 0010
  • 22 = 4 -> 0100
  • 23 = 8 -> 1000

这意味着2 的幂总是形如 100...0 的形式，即一个 1 后面跟着若干个 0。

n - 1 的二进制特性

  • 当我们从一个 2 的幂减去 1 时，结果会将原来唯一的 1 变成 0，并将其后面的 0 变成 1。

  • 举个例子：

    • n = 8 = 1000
    • n - 1 = 7 = 0111

可以看到，n 和 n - 1 在二进制表示上是完全互补的，n 只有一个 1 后面全是 0，而 n - 1 则是原来 1 变成 0，后面的 0 全部变成 1。

按位与运算 (n & (n - 1))

  • 按位与运算会将两个数的二进制表示逐位进行比较，只有在相同位上两个数字都是 1 时结果才为 1，其他情况为 0。
  • 对于 2 的幂 n，其二进制表示中只有一位是 1，而 n - 1 的二进制表示在相同位置是 0，其它位则是 1。这样一来，n & (n - 1) 的结果会是 0，因为在二进制中没有相同位置的 1 了。

举个例子：

  • n = 8 = 1000
  • n - 1 = 7 = 0111
  • 8 & 7 = 1000 & 0111 = 0000

为什么 n & (n - 1) 可以判断 2 的幂？

  • 如果 n 是 2 的幂，它的二进制表示中只有一个 1，且 n - 1 会使这个 1 的位置变为 0，后面的 0 变为 1。这样 n & (n - 1) 的结果一定是 0。
  • 如果 n 不是 2 的幂，它的二进制表示中至少有两个 1，那么 n - 1 并不能将所有的 1 都抵消掉，n & (n - 1) 的结果就不会是 0。

3. 获取最低位的 1（判断是否是 2 的幂次方）

n & -n 这个技巧可以高效地提取出一个整数二进制表示中最低位的 1。同样，它可以用于判断一个数是否是 2 的幂。让我们通过详细解释来理解其原理：

负数的二进制表示

  • 在计算机中，负数是按照 补码 规则存储的。具体来说，负数的二进制表示是正数的每一位取反后加 1。
  • 比如：
    • n = 12 = 11002
    • -n = -12 ，首先取反 11002 -> 00112 ，然后加 1，得到 01002

n & -n 的运算原理

  • 当我们执行 n & -n 时，计算结果会保留二进制表示中最低位的 1，而其余位都会变为 0。这是因为：
  • 对于 n ，其最低位的 1 之后的所有位都是 0。
  • 对于 -n ，最低位的 1 以及之后的所有位都会取反，最低位的 1 依然存在，而更高位则变为 0。
  • 将 n 和 -n 进行按位与运算时，高位都会变成 0，只有最低位的 1 保留下来，其他位变为 0。

举个例子：

  • n = 12 = 11002
  • -n = -12 = 01002
  • 12 & (-12) = 11002 & 01002 = 01002

结果是二进制数中最低位的 1。

n & -n 判断是否为 2 的幂

  • 如果 n 是 2 的幂，它的二进制表示只有一个 1，后面跟着若干个 0，比如 n = 8 = 10002 。
  • 对于这样的数，n & -n 的结果必然等于 n，因为二进制中只有一个 1，按位与之后的结果也只会是该位的 1，其他位为 0。
  • 因此，如果 n & -n == n，可以确定 n 是 2 的幂。

举个例子：

  • n = 8 = 10002
  • -n = -8 = 10002 （因为最高位 1 之后没有 0，所以没有变化）
  • 8 & -8 = 10002

此时 n & -n == n，所以 8 是 2 的幂。

4. 判断两个数的符号是否相同

  • 技巧：(a ^ b) >= 0

  • 原理：如果 a 和 b 的符号相同，那么它们的符号位相同，异或结果的符号位为 0，因此 (a ^ b) >= 0 为真；否则为假。

  • 代码示例：

Text Only
1
same_sign = (a ^ b) >= 0

判断两个数的符号是否相同

判断两个整数的符号是否相同可以通过异或运算（^）来实现，这种方法非常高效，不需要像传统的方式那样分别判断正负号。

原理解析

首先，我们需要了解整数在计算机中的二进制表示：

  • 符号位：整数的二进制表示中，最高位（最左边的一位）是符号位。当符号位为 0 时，表示正数；当符号位为 1 时，表示负数。
    • 例如，对于 32 位整数：
    • 正数 5 的二进制表示为 00000000 00000000 00000000 00000101
    • 负数 -5 的二进制表示为 11111111 11111111 11111111 11111011

通过异或判断符号

我们可以利用异或运算来判断两个数的符号是否相同。关键点在于异或运算的结果的符号位。

  • 符号位分析：
  • 如果 a 和 b 的符号相同，二者的符号位也会相同，异或后的结果在符号位会是 0，即结果是非负数。

  • 如果 a 和 b 的符号不同，二者的符号位会不同，异或后的结果在符号位会是 1，即结果是负数。

  • 相同符号：

  • 假设 a = 5 和 b = 10，它们的二进制表示如下：

    • a = 5 : 00000000 00000000 00000000 00000101
    • b = 10: 00000000 00000000 00000000 00001010

  • 它们的符号位都是 0，表示它们都是正数。

  • 进行异或运算：

Text Only
1
2
3
4
 a ^ b =     00000000 00000000 00000000 00000101
          ^  00000000 00000000 00000000 00001010
            -------------------------------------
             00000000 00000000 00000000 00001111

  • 结果的符号位仍然是 0，说明结果是非负数，因此 (a ^ b) >= 0 为真，表明它们的符号相同。

  • 不同符号：

    • 假设 a = 5 和 b = -10，它们的二进制表示如下：

    • a = 5 : 00000000 00000000 00000000 00000101

    • b = -10: 11111111 11111111 11111111 11110110 （负数在计算机中使用补码表示）

    • 进行异或运算：

Text Only
1
2
3
4
  a ^ b =     00000000 00000000 00000000 00000101
            ^ 11111111 11111111 11111111 11110110
              -------------------------------------
              11111111 11111111 11111111 11110011
Text Only
1
- 结果的符号位是 `1`，说明结果是负数，因此 `(a ^ b) < 0` 为真，表明它们的符号不同。

总结

  • 如果 a 和 b 符号相同，则 (a ^ b) 的符号位为 0，异或结果为非负数，故 (a ^ b) >= 0 为真。
  • 如果 a 和 b 符号不同，则 (a ^ b) 的符号位为 1，异或结果为负数，故 (a ^ b) >= 0 为假。

通过这一技巧，我们可以高效地判断两个整数的符号是否相同，避免了传统方法中的分支判断逻辑（如 if-else）。

类型 2 异或运算技巧

5. 交换两个数

  • 技巧：使用以下三步来交换 a 和 b 的值：
Python
1
2
3
a = a ^ b
b = a ^ b
a = a ^ b

异或运算的原理

关键的异或运算性质：

  1. a ^ a = 0：一个数与自身进行异或运算，结果是 0。
  2. a ^ 0 = a：一个数与 0 进行异或运算，结果还是该数本身。
  3. 交换律：a ^ b = b ^ a，即异或运算是可交换的。
  4. 结合律：a ^ (b ^ c) = (a ^ b) ^ c，即异或运算是可结合的。

基于这些性质，可以通过连续三次异或运算来完成两个变量的交换。

详细步骤

假设两个数为 a = 5 和 b = 3，我们来逐步分析通过异或操作交换它们的值。

  1. 第一步：a = a ^ b
    • 对 a 进行赋值操作：a = 5 ^ 3
    • 5 的二进制表示为 101，3 的二进制表示为 011。
    • a = 101 ^ 011 = 110，即 a = 6（此时 a 的值为 6，b 仍然是 3）。
  2. 第二步：b = a ^ b
    • 对 b 进行赋值操作：b = a ^ b = 6 ^ 3
    • 6 的二进制表示为 110，3 的二进制表示为 011。
    • b = 110 ^ 011 = 101，即 b = 5（此时 b 的值变成了 5，a 仍然是 6）。
  3. 第三步：a = a ^ b
    • 对 a 进行赋值操作：a = a ^ b = 6 ^ 5
    • 6 的二进制表示为 110，5 的二进制表示为 101。
    • a = 110 ^ 101 = 011，即 a = 3（此时 a 的值变成了 3，而 b 的值是 5）。

最终结果

通过这三次异或操作，a 的初始值 5 被赋给了 b，而 b 的初始值 3 被赋给了 a。因此，两个数在没有使用临时变量的情况下完成了交换。

代码示例

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
a = 5
b = 3

print(f"Before swap: a = {a}, b = {b}")

# 通过异或操作交换 a 和 b 的值
a = a ^ b  # a 变为 a ^ b
b = a ^ b  # b 变为 a
a = a ^ b  # a 变为 b

print(f"After swap: a = {a}, b = {b}")

输出结果

Text Only
1
2
Before swap: a = 5, b = 3
After swap: a = 3, b = 5

类型 3：快速运算

6. 将整数的第 k 位设为 1

  • 技巧：n | (1 << k)

  • 原理：通过左移运算将 1 移动到第 k 位，然后与 n 进行按位或运算，将第 k 位设为 1。

  • 代码示例：

Python
1
n = n | (1 << k)

7. 将整数的第 k 位设为 0

  • 技巧：n & ~(1 << k)

  • 原理：先通过左移运算将 1 移动到第 k 位，然后对其取反，将其余位设为 1，k 位设为 0，再与 n 进行按位与运算，清除第 k 位的值。

  • 代码示例：

Python
1
n = n & ~(1 << k)

8. 获取整数的第 k 位值

  • 技巧：(n >> k) & 1

  • 原理：通过右移运算将第 k 位移到最低位，然后与 1 进行按位与运算，判断该位是 0 还是 1。

  • 代码示例：

Python
1
bit = (n >> k) & 1

9. 统计整数的二进制中 1 的个数

  • 技巧：使用 n & (n - 1) 不断清除最低位的 1

  • 原理：每次执行 n & (n - 1) 都会减少一个 1，直到 n 变为 0。

  • 代码示例：

Python
1
2
3
4
count = 0
while n > 0:
  n = n & (n - 1)
  count += 1

与传统方式的比较

传统方法：整除 2

  • 传统的方法是通过不断将 n 除以 2 来判断 n 的二进制表示中的 1 的个数。每次除以 2 可以获取当前最右边的一位，通过判断这位是否是 1 来增加计数。

  • 示例代码：

Python
1
2
3
4
5
count = 0
while n > 0:
  if n % 2 == 1:
      count += 1
  n = n // 2  # 使用整数除法
  • 缺点：该方法需要遍历二进制表示的每一位，也就是需要循环的次数与 n 的比特数成正比。因此，如果 n 的二进制表示中有很多 0，这种方法效率较低。对于一个 32 位的整数，最多需要执行 32 次操作。

使用 n & (n - 1) 的方法

  • 通过 n & (n - 1)，每次运算直接将 n 的二进制表示中最低位的 1 清除。因此，执行的次数等于 n 中 1 的个数，而不是比特数。
  • 原理：
    • n & (n - 1) 的作用是将 n 的二进制表示中最低位的 1 变为 0。
    • 每次执行一次 n & (n - 1)，我们就移除了一个 1，直到所有的 1 都被移除，n 变为 0 为止。

10. 快速计算 2 的幂

  • 技巧：1 << k

  • 原理：左移运算相当于将 1 向左移动 k 位，这样可以快速得到 2^k 的结果。

  • 代码示例：

Python
1
power_of_two = 1 << k  # 等同于 2**k

2. 例题讲解

2.1 LC 231 2的幂

问题描述

给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true；否则，返回 false。

如果存在一个整数 x 使得 n == 2^x，则认为 n 是 2 的幂次方。

方法：位运算

一个数 n 是 2 的幂，当且仅当 n 是正整数，并且 n 的二进制表示中仅包含 1 个 1。

因此，我们可以考虑使用位运算技巧来判断。

位运算技巧

  1. 使用 n & (n - 1) 判断
Python
1
2
3
class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        return n > 0 and (n & (n - 1)) == 0
  1. 使用 n & (-n) 判断
Python
1
2
3
class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        return n > 0 and (n & -n) == n

2.2 LC268 丢失的数字

问题描述

给定一个包含 [0, n] 中 n 个数的数组 nums，找出 [0, n] 这个范围内没有出现在数组中的那个数。

思路讲解

方法一：使用set

解题思路

  1. **构建一个集合set：将数组中的所有数存入set中。
  2. 遍历查找缺失的数字：然后遍历 [0, n] 的所有数，检查哪个数字不在set中。
  3. 返回结果：一旦发现某个数字不在 set 中，即可返回该数字作为缺失的数字。

参考解答

Python
1
2
3
4
5
6
class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        num_set = set(nums)
        for i in range(len(nums) + 1):
            if i not in num_set:
                return i

方法二：使用位运算（异或）

解题思路

这道题的核心思路是基于异或运算的性质来找到丢失的数字。温习异或运算的以下几个关键性质： 1. 交换律和结合律：a ^ b ^ c 和 a ^ c ^ b 的结果相同，即顺序无关。 2. 相同数字异或为 0：a ^ a = 0，即两个相同的数字异或会互相抵消为 0。 3. 任何数字与 0 异或等于自身：a ^ 0 = a。

具体步骤：

  1. 初始化变量：

    • missing 变量初始值为 0，用于存储异或结果。
    • n = len(nums)，表示数组的长度。

  2. 第一轮循环 (异或数组中的元素)：

    • 在 for 循环中，missing 会依次与数组中的每个元素进行异或运算。
    • 假设 nums = [3, 0, 1]，这时 missing 将依次变为 missing = 0 ^ 3 ^ 0 ^ 1。
    • 这一步骤的目的是通过异或将 nums 数组中的所有元素记录到 missing 中。

  3. 第二轮循环 (异或范围 [0, n])：

    • 第二个 for 循环从 0 到 n，missing 将依次与 [0, n] 这个范围的所有数字进行异或运算。
    • 由于丢失的数字存在于 [0, n] 中，但不在 nums 中，通过这个步骤，missing 会变为最终的丢失数字。

  4. 利用异或性质：

    • 最终，所有成对出现的数字都会被抵消为 0，剩下的就是那个没有成对出现的数字，也就是丢失的数字。

参考解答

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        missing = 0
        n = len(nums)

        # 第一轮循环，异或数组中的元素
        for i in range(n):
            missing ^= nums[i]

        # 第二轮循环，异或范围 [0, n]
        for i in range(n + 1):
            missing ^= i        
        return missing

3. 举一反三

3.1 LC2309 兼具大小写的最好英文字母

问题描述

给你一个由英文字母组成的字符串 s ，请你找出并返回 s 中的最好英文字母。返回的字母必须为大写形式。如果不存在满足条件的字母，则返回一个空字符串。

最好英文字母的大写和小写形式必须都在 s 中出现。

英文字母 b 比另一个英文字母 a 更好 的前提是：英文字母表中，b 在 a 之后出现。

解题思路1：哈希表

使用哈希表保存字符串 s 中出现过的字符。遍历字符串 s，将当前字符 c 加入到哈希表中。

从大到小枚举英文字母，如果一个英文字母的大写形式和小写形式都出现在哈希表中，那么直接返回该英文字母。如果所有的英文字母都不符合要求，那么直接返回空字符串。

参考解答1

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def greatestLetter(self, s: str) -> str:
        # 用一个set来保存字符串中出现的字母
        present_letters = set(s)

        # 初始化best为一个空字符串
        best = ""

        # 遍历所有大写字母
        for c in range(ord('A'), ord('Z') + 1):
            # 检查大写和对应的小写字母是否都在字符串中
            if chr(c) in present_letters and chr(c + 32) in present_letters:
                # 如果同时存在，则比较大小，找到字母表中靠后的字母
                best = chr(c) if best == "" or c > ord(best) else best

        return best

解题思路2：位运算

使用两个 32 位整数 lower 和 upper 分别表示字符串 s 中小写字母和大写字母的出现情况。

  1. 遍历字符串 s，对于每个字符 c：

  2. 如果 c 是小写字母，将 lower 的对应位置设为 1；

  3. 如果 c 是大写字母，将 upper 的对应位置设为 1。

  4. 从大到小枚举英文字母，如果发现某个英文字母的大小写形式在 lower 和 upper 中都出现，那么返回该字母。

  5. 如果所有的字母都不符合要求，则返回空字符串。

位运算技巧

  • lower |= 1 << (ord(c) - ord('a'))：将字符 c 对应的位数置为 1，表示该字符出现过。
  • upper |= 1 << (ord(c) - ord('A'))：同理，将大写字符 c 对应的位数置为 1。
  • lower & upper & (1 << i)：判断小写和大写的第 i 位是否都为 1，表示该字母的大小写都出现过。

参考解答2

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def greatestLetter(self, s: str) -> str:
        lower = upper = 0
        for c in s:
            if c.islower():
                lower |= 1 << (ord(c) - ord('a'))
            else:
                upper |= 1 << (ord(c) - ord('A'))
        for i in range(25, -1, -1):
            if lower & upper & (1 << i):
                return chr(ord('A') + i)
        return ""

3.2 LC136 只出现一次的数字

问题描述

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

解题思路1：异或运算

对于这道题目，我们可以使用 异或运算（⊕）。异或运算有以下三个性质：

  1. 任何数和 0 做异或运算，结果仍然是原来的数，即 a ⊕ 0 = a。
  2. 任何数和其自身做异或运算，结果是 0，即 a ⊕ a = 0。
  3. 异或运算满足交换律和结合律，即 a ⊕ b ⊕ a = b ⊕ a ⊕ a = b ⊕ (a ⊕ a) = b ⊕ 0 = b。

假设数组中有 2m + 1 个数，其中有 m 个数各出现两次，一个数出现一次。令 a1, a2, ..., am 为出现两次的 m 个数，am+1 为只出现一次的数。根据性质 3，数组中的全部元素的异或运算结果总是可以写成如下形式：

(a1 ⊕ a1) ⊕ (a2 ⊕ a2) ⊕ ⋯ ⊕ (am ⊕ am) ⊕ am+1

根据性质 2 和性质 1，上式可以化简为：

0 ⊕ 0 ⊕ ⋯ ⊕ 0 ⊕ am+1 = am+1

因此，数组中的所有元素的异或运算结果就是数组中只出现一次的那个数。

代码实现

Python
1
2
3
4
5
6
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        result = 0
        for num in nums:
            result ^= num
        return result

解题思路2：哈希表

我们可以利用 set 的特点来解决这个问题。

  1. 如果一个数字在集合中出现了，我们将其从集合中移除。
  2. 如果一个数字没有出现在集合中，我们将其添加到集合中。

对于每个数字，我们只会保留它在集合中出现一次的记录。如果某个数字出现了两次，它将被移除，最终集合中剩下的唯一元素就是那个只出现了一次的数字。

解题步骤

  • 创建一个 set，用于存储数组中的数字。
  • 遍历数组：
  • 如果当前数字已经在集合中存在，说明它是重复的，将其从集合中移除。
  • 如果当前数字不在集合中，说明它是第一次出现，将其加入集合。
  • 遍历结束后，集合中仅剩下的一个元素就是只出现一次的数字。

因为题目中给定的条件是只有一个数字出现了一次，其余的数字都出现了两次，最终 set 中只会剩下那个唯一的数字。

我们可以使用一个 Set 来解决这个问题。遍历数组时，如果某个数字已经在 Set 中存在，就将它移除；否则将它加入。最后剩下的那个数字就是只出现一次的数字。

Python
1
2
3
4
5
6
7
8
9
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        num_set = set()
        for num in nums:
            if num in num_set:
                num_set.remove(num)
            else:
                num_set.add(num)
        return num_set.pop()

3.3 LC389 找不同

问题描述

给定两个字符串 s 和 t ，它们只包含小写字母。

字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。

请找出在 t 中被添加的字母。

尝试使用 LC136 题目的位运算技巧解决本题

思路讲解

题目要求找出在字符串 t 中多出来的那个字符。

我们可以将两个字符串拼接成一个字符串，把问题转化为求这个拼接字符串中出现奇数次的字符。因为其他字符都会出现偶数次，最终的结果只会剩下那个出现奇数次的字符。

类似于「136. 只出现一次的数字」，我们可以使用异或运算来解决此问题：

  • 异或运算的性质：
  • 任何数和 0 进行异或运算，结果为该数本身：a ⊕ 0 = a。
  • 任何数和自己进行异或运算，结果为 0：a ⊕ a = 0。
  • 异或运算满足交换律和结合律：a ⊕ b ⊕ a = (a ⊕ a) ⊕ b = 0 ⊕ b = b。

根据这些性质，如果我们将 s 和 t 的所有字符都进行异或运算，成对出现的字符最终会抵消，剩下的就是 t 中那个多出来的字符。

解题步骤

  1. 初始化一个整数 ret，表示异或结果，初始值为 0。
  2. 遍历字符串 s 中的每个字符，将字符的 ASCII 值与 ret 进行异或操作。
  3. 遍历字符串 t 中的每个字符，同样将其 ASCII 值与 ret 进行异或操作。
  4. 返回最终 ret 的值，它就是那个多出来的字符。

代码实现

Python
1
2
3
4
5
6
class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        result = 0
        for char in s + t:
            result ^= ord(char)
        return chr(result)

4. 课后练习

题目编号 题目名称 简介
LC868 二进制间距 给定一个正整数，计算它在二进制表示中两个相邻的 1 之间的最大距离。
LC1486 数组异或操作 给定一个整数 n 和一个整数 start，生成一个数组，返回数组中所有元素的异或结果。
LC1720 解码异或后的数组 给定一个异或后的数组，返回其原始数组。
LC645 错误的集合 集合 S 包含 [1, n] 中的 n 个整数，但其中有一个重复的数和一个缺失的数，找出它们。
LC693 交替位二进制数 给定一个正整数，判断其二进制表示是否为交替位。