定义与相关性质

异或运算（XOR）是一种二进制运算，用符号 ^ 表示。它的规则是：对应的二进制位相同则结果为0，不同则结果为1。==（相当于无进位相加）==

具体的异或运算规则如下：

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

异或运算有一些重要的性质：

  1. 交换律： 对于任意两个数a和b，都有a ^ b = b ^ a。
  2. 结合律： 对于任意三个数a、b、c，都有a ^ (b ^ c) = (a ^ b) ^ c。
  3. 自反性： 任何数与自己异或的结果为0，即a ^ a = 0。
  4. 零元素： 任何数与0异或的结果为它本身，即a ^ 0 = a。

异或运算常常用于一些算法和编程中，有一些应用场景如下：

  1. 交换两个数的值： a = a ^ b; b = a ^ b; a = a ^ b; 这样就可以交换a和b的值。
  2. 清零特定位： 将一个数的特定位清零，可以使用 a = a ^ (1 << i)，其中i表示要清零的位。
  3. 判断两个数是否相等： 如果两个数相等，异或的结果为0；如果不相等，异或的结果非零。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <stdio.h>

int main() {
    int a = 5; // 二进制：0101
    int b = 3; // 二进制：0011

    // 异或运算
    int result = a ^ b;

    printf("a ^ b = %d\n", result); // 输出：6

    return 0;
}

在这个示例中，a和b的二进制分别是0101和0011，它们进行异或运算的结果是6（二进制：0110）。

题目一 如何不用额外变量交换两个数(面试装逼用的)

1
2
3
4
5
int a=1;int b=2;
a=a^b;
b=a^b;
a=a^b;

题目二 一个数组中有一种数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这种数（比用哈希表的方法更简单）

理解过程：

image-20231213224233037

1
2
3
4
5
6
//arr中只有一种数出现奇数次
int eor=0;
for(int i=0;i<length;i++){
	eor^=arr[i];
	}
printf("%d",eor);//eor即为所要的那一种数

题目三 怎么把一个int类型的数，提取出最右侧的1来

题目意思：

image-20231213224305027

过程：

image-20231213224702520

方法：

a&(~a+1)等用于a&(-a)

题目四 一个数组中有两种数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这两种数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
for (int i = 0; i < length; i++) {
	eor ^= arr[i];
}
//a和b是两种数 -> eor!=0
//eor最右侧的1，提取出来
//eor: 000100100  ->  rightOne:  000000100
int rightOne = eor & (-eor);//提取出最右的1
int onlyOne = 0;
for (int i = ; i < length; i++) {
	if ((arr[i] & rightOne) != 0) {
		onlyOne ^= arr[i];

	}
}
int otherOne = eor ^ onlyOne;