【Algorithm】位运算总结

异或

• 表示
  xor 或 ^

具有以下几种特性

1. 交换律
2. 结合律
3. 对于任何数x，有x xor x = 0，x xor 0 = x
4. 自反性，A xor B xor B = A xor 0 = A

• 应用

1. 找出重复数
   1-1000放在含有1001个元素的数组中，只有唯一的一个元素值重复，其它均只出现
   一次。每个数组元素只能访问一次，设计一个算法，将它找出来；不用辅助存储空
   间，能否设计一个算法实现？

设重复数字为 x
t = 1^2^....^1000
k = a[0]^a[1]^....^a[1000] = t ^ x
则 t ^ k = t ^ t ^ x = 0 ^ x = x