异或^和左移位运算 – Akiの分身｜プライベート小空間

介绍、

异或运算符^，是按二进制位操作，相同为0，不同为1。异或运算符适用于布尔值和二进制数。

运算律、

int a = 10；int b = 20；int c = 30；

a ^ a = 0，即任何一个数与自身异或都是0，拥有相同数值的两个数异或也是0。

a ^ 0 = a，即任何一个数与0异或都是本身。

a ^ b = b ^ a，有交换律。

a ^ b ^ c = a ^ (b ^ c)，有结合律。

一些巧妙的运用、

1）两个数字之间的交换

int a = 10；int b = 20；如果需要交换 a 和 b 则可以写成下面这样：

a = a ^ b; b = a ^ b; a = a ^ b; 三行代码完成交换，没有引入中间变量。

解释：

第一行代码 a = a ^ b;

第二行代码 b = a ^ b; 且由于 a = a ^ b; 就变成了 b = a ^ b ^ b = a。

第三行代码 a = a ^ b; 且由于 b = a，a = a ^ b; ，就变成了 a = a ^ b ^ a = b。

注意这样写的前提是这两个变量不是同一个变量，不是拥有相同的内存地址。

一个经典题目、

一个 int 数组中只有一个数出现了奇数次，找出这个数。要求时间复杂度O（1），空间复杂度O（1）。

解：假设这个 int 数组是 int array [] = {1,2,3,4,5,6,1,2,3,4,5,6,7}，当然可能还很大有更多的数据。

思路是设置一个int变量，让这个变量从头异或到尾。

int array [] = {1,2,3,4,5,6,1,2,3,4,5,6,7}
int tmp = 0;
for(int i = 0;i<arraySize;++i)
{
   tmp = tmp ^ array[i];
}

最终的结果是 tmp = 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7;
由于异或运算具有结合律，所以可以写成下面这样
tmp = 0 ^ 1 ^ 1 ^ 2 ^ 2 ^ 3 ^ 3 ^ 4 ^ 4 ^ 5 ^ 5 ^ 6 ^ 6 ^ 7;
且由于偶数次的异或都是0，所以 tmp = 0 ^ 7 = 7;  这样就找出了奇数次的数

性能探究，局限性、

对于临时变量法，每次赋值只要读取一个变量的值到寄存器，然后再从寄存器写回到另一个变量中即可，前后涉及两次内存写入操作；但是对于异或运算操作，每次都需要读取两个数据到寄存器中，再进行运算操作，之后把结果写回到变量中，前后共需要三次内存写入操作。另外一点，异或操作的代码可读性差。

实际测试中异或交换的性能低于使用临时值的性能，低了差不多两倍。且还有隐患，也就是不能对同一块内存区域进行异或操作。

所以还是尽量少使用异或吧。

左移位和右移位、

左移和右移的运算规则为：逻辑左移，高位丢弃，低位补0；逻辑右移，高位补0，低位丢弃。如0000100，逻辑左移1位为0001000；逻辑右移1位为0000010。

无符号数的移位运算为逻辑移位，规则就是上面的例子。

有符号数的移位称为算术移位，移位规则为：分为正数和负数讨论。