问题描述
假设我们有 N 根筷子，我们需要找出哪些筷子是单独存在的（即没有配对的筷子）
位运算思路
- 使用异或运算：对于每一对筷子，如果它们是成对的，那么它们的状态会相互抵消。也就是说，两个相同的数进行异或运算的结果是 0，而不同的数进行异或运算的结果是一个非零的数
- 最终结果：通过对所有筷子的状态进行异或运算，最终的结果就是那些没有配对的筷子的状态。
示例代码
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
int single(int* in, int n) {
int result = 0;
for (int i = 0; i < n; i++) {
result ^= in[i];
}
return result;
}
int main() {
int n;
int in[999];
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &in);
}
int result = single(in, n);
printf("%d", result);
return 0;
}
为什么可以这样做
假设我们有一个数组 chopsticks，其中大多数筷子的状态是成对出现的，只有一根筷子的状态是唯一的。例如：
chopsticks = [1, 2, 1, 3, 2]在这个数组中，状态为 3 的筷子是唯一的，其他的状态 1 和 2 都是成对出现的
计算过程
我们可以逐步计算异或运算的结果：
- 初始
result = 0 result = 0 ^ 1 = 1（处理第一个筷子）result = 1 ^ 2 = 3（处理第二个筷子）result = 3 ^ 1 = 2（处理第三个筷子）result = 2 ^ 3 = 1（处理第四个筷子）result = 1 ^ 2 = 3（处理第五个筷子）
最终的 result 是 3，这就是唯一存在的筷子状态
为什么会这样
- 当我们遇到成对的筷子状态时，例如
1和1，它们会相互抵消，因为1 ^ 1 = 0 - 同样，
2和2也会相互抵消 - 唯一的筷子状态（在这个例子中是
3）不会被抵消，因为它没有成对的状态
因此，最终的 result 就是唯一存在的筷子状态
说人话
当我们遇到成对的筷子状态时，例如 1 和 1，它们会相互抵消，因为 1 ^ 1 = 0。但不一定是连着的啊，1后面不一定还是1，为什么还能 result ^= chopsticks[i];这样无脑遍历整个数组（result刚开始是初始化0，但是result不能清空弹夹）
这就涉及到前面的一章关于按位异或的性质
成对的筷子状态不需要是连续的。但是异或运算的特性使得它可以在任何顺序下工作，而不仅仅是相邻的元素
这实在是妙不可言！
//PS：我当时也太吊了，居然知道遇到相同就都赋值为0然后输出非0数（我想的实际上是”添加标志“的方法），和这个居然是一样的原理，GREATNESS！
- 单位元：
0 ^ a = a，这意味着任何数与0异或的结果是这个数本身
//依靠单位元可以直接将result初始化为0，就能参与运算了
- 自反性:
a ^ a = 0，这意味着任何数与自己异或的结果是0
//依靠自反性将相同的数字排除在外（使result为0）
- 交换性:
a ^ b = b ^ a，这意味着你可以改变操作数的顺序 - 结合性:
(a ^ b) ^ c = a ^ (b ^ c)，这意味着你可以改变操作数的组合方式
//依靠交换性和结合性使无脑遍历整个数组后得到的result的值就是落单的筷子
Comments NOTHING