位运算的应用 - 异或 / XOR / ^

创建时间:
2014-06-14 12:18
最近更新:
2018-07-17 23:49

异或特性

  1. 满足交换律,即 a ^ b === b ^ a
  2. 满足结合律,即 a ^ (b ^ c) === (a ^ b) ^ c
  3. 对于任何数 x,都有 x ^ x === 0x ^ 0 === x
  4. 自反,即 a ^ b ^ b === aa ^ 0 === a

反转特定位

XOR 运算通常用于对二进制的特定位进行取反操作,因为异或可以这样定义:0 和 1 异或 0 都不变,异或 1 则取反。

假设:
a: 1010 0001
b: 1010 0111
c: 0000 0110
如需对 a 或 b 的第 2 位和第 3 位翻转,则将它与 c 进行 按位异或 运算。

加密

XOR 运算的逆运算是它本身,也就是说两次异或同一个数最后结果不变,即 (a xor b) xor b = a。此特性可以用于简单的加密。

例如:GG 想对 MM 说 1314520,但不希望别人知道,于是双方约定拿 MM 的生日 19880516 作为密钥:1314520 xor 19880516 = 20665500,GG 就把 20665500 告诉 MM,MM 再次计算 20665500 xor 19880516 得到 1314520,于是 MM 就明白了 GG 的心思。

交换两个变量的值,而不使用临时变量

a = a ^ b;
b = a ^ b; //相当于 (a ^ b) ^ b,执行后 b 已等于 a 的初始值。
a = a ^ b; //相当于 (a ^ b) ^ a,执行后 a 已等于 b 的初始值。
//原理:XOR 的逆运算是它本身。
a = a + b;
b = a - b; //相当于 (a + b) -b,执行后 b 已等于 a 的初始值。
a = a - b; //相当于 (a + b) -a,执行后 a 已等于 b 的初始值。
// 原理:加法与减法互为逆运算、加法满足交换律。
/// <summary>
/// 交换两个实参的值。
/// 原理:使用中间变量。
/// </summary>
public static void Swap<T>(ref T a, ref T b)
{
	T temporary = a;
	a = b;
	b = temporary;
}

/// <summary>
/// 交换两个实参的值。
/// 原理:异或的逆运算是它本身。
/// 缺陷一:非泛型。
/// 缺陷二:开销大于使用中间变量。
/// </summary>
public static void Swap(ref int a, ref int b)
{
	a = a ^ b;
	b = a ^ b;
	a = a ^ b;
}

/// <summary>
/// 交换两个实参的值。
/// 原理:加法与减法互为逆运算、加法满足交换律。
/// 缺陷一:非泛型。
/// 缺陷二:开销大于使用中间变量。
/// 缺陷三:存在溢出的可能性。
/// </summary>
public static void Swap(ref int a, ref int b)
{
	a = a + b;
	b = a - b;
	a = a - b;
	//or:
	//a = a - b;
	//b = a + b;
	//a = b - a;
}

Resource

  1. 异或运算交换两个元素位置,不需要额外空间

将变量置零

a = a ^ a
该方法在汇编语言中经常使用。

快速判断两个值是否相等

if((a ^ b) == 0) {}

有趣的题目

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

解法一

将所有数加起来,减去 1+2+...+1000 的和。

这个算法已经足够完美了,相信出题者的标准答案也就是这个算法,唯一的问题是,如果数列过大,则可能会导致溢出。

解法二

异或就没有这个问题,并且性能更好。

将所有的数全部异或,得到的结果与 1 ^ 2 ^ 3 ^ ... ^ 1000 的结果进行异或,得到的结果就是重复数。

虽然这个算法虽然很简单,但证明起来并不是一件容易的事情。这与异或运算的几个特性有关系。

首先是异或运算满足交换律、结合律。所以,1 ^ 2 ^ ... ^ n ^ ... ^ n ^ ... ^ 1000,无论这两个 n 出现在什么位置,都可以转换成为 1 ^ 2 ^ ... ^ 1000 ^ (n ^ n) 的形式。

其次,对于任何数 x,都有 x ^ x = 0x ^ 0 = x。所以 1 ^ 2 ^ ... ^ n ^ ... ^ n ^ ... ^ 1000 = 1 ^ 2 ^ ... ^ 1000 ^ (n ^ n) = 1 ^ 2 ^ ... ^ 1000 ^ 0 = 1 ^ 2 ^ ... ^ 1000 (即序列中除了 n 的所有数的异或)。

令,1 ^ 2 ^ ... ^ 1000 (序列中不包含 n) 的结果为 T,则 1 ^ 2 ^ ... ^ 1000 (序列中包含 n) 的结果就是 T ^ n

T ^ (T ^ n) = n

所以,将所有的数全部异或,得到的结果与 1 ^ 2 ^ 3 ^ ... ^ 1000 的结果进行异或,得到的结果就是重复数。

当然有人会说,1 + 2 + ... + 1000 的结果有高斯定律可以快速计算,但实际上 1 ^ 2 ^ ... ^ 1000 的结果也是有规律的,算法比高斯定律还该简单的多。

Google 面试题的变形

一个数组存放若干整数,一个数出现奇数次,其余数均出现偶数次,找出这个出现奇数次的数?

解法有很多,但是最好的和上面一样,就是把所有数异或,最后结果就是要找的,原理同上。