^异或运算符

发表于 更新于 分类于

一、异或运算符 基础定义（二进制本质）

异或的符号是 ^ ，是二进制位运算，运算规则非常简单：相同为 0，不同为 1

  • 0 ^ 0 = 0
  • 0 ^ 1 = 1
  • 1 ^ 0 = 1
  • 1 ^ 1 = 0

补充：参与运算的整数，会先被转为二进制补码形式，再按位做异或运算，最终结果转回十进制。

例：3 ^ 5 → 二进制 011 ^ 101 = 110 → 十进制结果 6

二、异或的 6 个核心基础性质（必记，最常用）

这 6 个是异或最根本的性质，所有推导规律都来自于此，优先级从上到下，重要程度递减，全部要牢记：

✅ 性质 1：自反性 a ^ a = 0

任何整数和自身做异或运算，结果一定是 0

  • 原理：二进制每一位都相同，按位异或必然全为 0
  • 例：5^5=0、100^100=0、0^0=0

✅ 性质 2：归零性 / 恒等律 a ^ 0 = a

任何整数和0做异或运算，结果一定是这个数本身

  • 原理：0 的二进制全是 0，任何位和 0 异或都「不同为 1、相同为 0」，等价于不变
  • 例：5^0=5、-3^0=-3、0^0=0

✅ 性质 3：交换律 a ^ b = b ^ a

异或运算的顺序可以交换，结果不变

  • 例：3^5 = 5^3 = 6、2^7^9 = 7^2^9

✅ 性质 4：结合律 (a ^ b) ^ c = a ^ (b ^ c)

异或运算的组合顺序可以调换，结果不变

  • 例：(1^2)^3 = 1^(2^3) = 0

✅ 性质 5：异或的逆运算还是异或 a ^ b = c → a = c ^ b 、 b = c ^ a

这是异或最核心的解题性质，非常关键！

  • 含义：如果两个数的异或结果是第三个值，那么其中任意一个数，等于「结果值」异或「另一个数」
  • 推导：a^b = c 两边同时异或 b → a^b^b = c^b → 由自反性 b^b=0 → a^0 = c^b → 由归零性得 a = c^b
  • 例：3^5=6 → 可以推出 3=6^5 、 5=6^3

✅ 性质 6：与加减运算的混合性质 a ^ b = (a + b) - 2*(a & b)

异或可以和「加法、按位与」做换算，了解即可，部分算法题会用到

  • 含义：两个数的异或 = 两数之和 - 两倍的「两数按位与」
  • 例：3+5=8，3&5=1 → 8 - 2*1 =6，和 3^5 的结果一致

三、异或的 3 个常用推导规律 / 特殊结论

由上面的基础性质，能推导出 3 个高频使用的结论，做题时可以直接套用：

结论 1

连续异或运算中，相同数字出现偶数次，会全部抵消为 0；出现奇数次，最终结果等于「该数字本身」

推导：a^a^a = (a^a)^a = 0^a = a 、 a^a^a^a = (a^a)^(a^a) = 0^0 =0

例：1^2^1^2 = 0 、 1^2^1^2^3 = 3

结论 2

多个数连续异或，结果和数字的顺序无关（交换律 + 结合律推导）

例：a^b^c^d = b^d^a^c = d^c^b^a，结果完全相同

结论 3

a ^ b ^ a = b （最常用的「去重保留」）

推导：a^a^b = 0^b = b

含义：一个数异或另一个数，再异或自身，会得到「另一个数」，相当于 “剔除自身，保留目标数”

四、异或的 3 个经典高频应用场景（必考！）

异或的性质看似简单，但能解决很多「常规方法很麻烦」的问题，且**时间复杂度 O (n)、空间复杂度 O (1)**，是最优解，这三个场景是笔试 / 面试的常客，必须掌握：

✅ 场景 1：不用临时变量，交换两个整数的值

这是异或最经典的应用，也是最能体现「逆运算性质」的场景，无任何中间变量，效率极高

java

1
2
3
4
5
6
// 交换 a 和 b 的值，无临时变量
int a = 3, b = 5;
a = a ^ b;  // 第一步：a 变成 3^5=6
b = a ^ b;  // 第二步：b = 6^5 = 3 （此时b已经是原来的a）
a = a ^ b;  // 第三步：a =6^3 =5  （此时a已经是原来的b）
// 最终 a=5，b=3，交换完成

✅ 原理：全程用到「异或的逆运算」，没有任何数值溢出风险，比 a=a+b;b=a-b 更安全。

✅ 场景 2：找出数组中「唯一出现一次」的数字

题目：一个非空整数数组，除了一个数字只出现 1 次，其余所有数字都出现偶数次，请找出这个唯一的数字。

要求：空间复杂度 O (1)，不能用哈希表 / 集合

✅ 最优解：数组中所有数字连续异或，最终结果就是目标数字

java

1
2
3
4
5
6
7
// 例：数组 [1,2,3,2,1]，唯一出现一次的是3
int[] arr = {1,2,3,2,1};
int res = 0;
for(int num : arr) {
    res ^= num; // 0^1^2^3^2^1 = 3
}
System.out.println(res); // 输出 3

✅ 原理：出现偶数次的数字，异或后相互抵消为 0；最终 0 ^ 唯一数字 = 唯一数字

✅ 场景 3：找出数组中「唯一出现奇数次」的数字

题目变形：数组中只有一个数字出现奇数次，其余都出现偶数次，求这个数字。

本质和场景 2 完全一致，解法相同！

扩展：如果数组中有两个数字出现奇数次，其余偶数次，解法是「分组异或」，也是面试高频题，思路：

  1. 全部异或得到 a^b（两个目标数的异或）；
  2. 找 a^b 二进制中任意一个为 1 的位，按这个位将数组分成两组；
  3. 两组分别异或，得到两个目标数 a 和 b。

五、补充：异或的小细节（避坑）

  1. 异或运算的优先级：比「加减」低，比「赋值」高，所以 a ^ b + c 等价于 a ^ (b+c)，建议加括号避免出错；
  2. 异或支持负数运算：负数在计算机中是「补码」形式，异或规则不变，例：-1 ^ -2 = 3；
  3. 异或运算无进位：二进制运算时，相同位相加不进位，这也是异或被称为「半加器」的原因。

✅ 总结（核心速记，建议收藏）

  1. 异或本质：二进制按位运算，相同为 0，不同为 1；
  2. 核心三性质：a^a=0、a^0=a、逆运算还是异或；
  3. 核心规律：偶数次抵消为 0，奇数次保留自身；
  4. 三大应用：无临时变量交换数字、找唯一出现 1 次的数字、找唯一奇数次数字。