异或
- 表示
xor 或 ^
具有以下几种特性
- 交换律
- 结合律
- 对于任何数x,有x xor x = 0,x xor 0 = x
- 自反性,A xor B xor B = A xor 0 = A
- 应用
- 找出重复数
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
网友评论