【位运算】^、|、&、>>、>>

最近看代码的时候看到了，所以简单记录一下这些基本的位运算，高手应该很多用的，因为速度确实快，实现起来也很巧妙。

1.& and运算

如果两个相应的二进制位都为１，则该位的结果值为1，否则为0。
简单例子如下：

11 & 3 = 3
00001011 & 
00000011 =  
00000011 = 3

比如我们经常要用的是否被2整除，一般都写成 if(n % 2 == 0)可以换成 if((n&1) == 0)

2.| or运算

如果两个相应的二进制位只要有一个是1，结果就是1，否则为0。
简单例子如下：

11 | 3 = 11
00001011 | 
00000011 = 
00001011 = 11

可以用一个unsigned int 来存储多个布尔值。比如一个文件有读权限，写权限，执行权限。看起来要记录3个布尔值。我们可以用一个unsigned int也可以完成任务。
一个数r来表示读权限，它只更改个位来记录读权限的布尔值

00000001 // (表示有读权限) 
00000000 // (表示没有读权限)

一个数w表示写权限，它只用二进制的倒数第二位来记录布尔值

00000010 //(表示有写权限)
00000000 //(表示没有写权限)

一个数x表示执行权限，它只用倒数第三位来记录布尔值

00000100 //(表示有执行权限)
00000000 //(表示没有执行权限)

那么一个文件同时没有3种权限就是
~r | ~ w | ~ x 即为 00000000，就是0
只有读的权限就是
r | ~w | ~x 即为 00000001，就是1
只有写的权限就是
~r | w | ~x 即为 00000010，就是2
...
一个文件同时有3种权限就是
r | w | x 即为 00000111，就是7

3.<< 左移

简单例子(向左移一位，右边自动补0)

11 << 1 = 22
00001011 << 1
00010110 = 22

相当于二进制的每个数都变成当前值的两倍，结果就是变成当前值的两倍。
n * 2 == (n << 1)
(注意可能会溢出)

4.>> 右移

简单例子(向右移一位，左边自动补1)

11 >> 1 =  5
00001011 >> 1
00000101 = 5

注意到最后一位的1被干掉了。
比较实用的例子是:
int n = n / 2 等价于 int n = n >> 1 等价于 int n >>= 1

5.^ 异或

两个相同的数会变成0，反之是1
一个简单的例子：

11^3 = 8
     00001011
^   00000011
=   00001000 = 8

理解异或，一定要用异或来解下面的题目：
就是一个数组中，所有数字都出现了两次，只有一个没有
比如 int t = {1,2,3,3,2,1,5} 要找到5。
用异或就完美了，所有相同的都会消失，留下来的就是5了。异或是嫉妒成双成对的。

 for(int i = 1; i < n; ++i){    
           A[0] ^= A[i];    
        }    
        return A[0];   

还有不用temp值来交换两个数：

x ^= y;
y ^= x;
x ^= y;