本文共 985 字，大约阅读时间需要 3 分钟。
前言：昨天晚上做蓝桥杯的时候，发现了一道有意思的题目。在网上查找了关于位运算的运用后，发现很有意思，因此决定把他们记录下来。
异或运算的性质：
任何数字异或它自己都等于0；
0异或任何数，等于任何数；
1异或任何数，等于取反任何数。
下面列出几道题目：
1、异或去重
给定大小为n+1的数组，元素大小在[1 : n]之间，只有一个元素会重复出现两次，找到重复的那个元素。 要求，时间复杂度是O(n)，空间复杂度是O(1)。
分析：
原数组大小为n+1，其中有一个元素重复了两次（假设为x），那么将该数组与1-1000的所有数字进行异或，则x出现了3次，其他数字只出现了2次。那么该异或得到得结果便是x！
例如下面这段代码（将1000个数据改成了10个，但道理还是一样的哈）：
#includeusing namespace std;int main(){ int a[11] = {1, 2, 3, 4 ,5, 6 ,7 ,8, 9, 10, 3}; //可以看到，在该数组中3出现了两次 int x = 0; //存储重复的数字 for (int i = 0; i < 11; ++i) { x = x^a[i]; //先将数组a中的数字全部进行异或 } for (int i = 1; i < 11; ++i) { x = x^i; //将数组a异或后，再与1~10中的数字异或 } cout << x << endl; //得到重复的这个数字 return 0;}
类似的更多复杂运用：
emmmm补充一道题：
2、交换数值
在面试中，经常会碰到这样一道题：不定义临时变量，交互两个数的值。一般的解法如下：
void exchange(int * a, int * b){ *a = *a + *b; *b = *a - *b; *a = *a - *b;} 这种解法主要是通过加减和赋值运算来实现，但它有两个缺陷：
1）未考虑极限情况下的加法溢出问题；
2）仅适用于交互可以进行加减运算的变量的值。
而使用异或可以弥补这两个缺陷，且运算速度更快：
void exchange(int * a, int * b){ *a = *a ^ *b; *b = *a ^ *b; *a = *a ^ *b;}
转载地址：http://svtai.baihongyu.com/