基本的位运算

程序中的所有数在计算机内存中都是以二进制的形式储存的。位运算就是直接对整数在内存中的二进制位进行操作。很多高级的动态规划题目或者一些基础的运算往往需要较高的执行效率和较低的空间需求，或者需要表示一些状态集合，而位运算刚好能满足这一切。很多的时候，恰当的位运算使用也能使程序变得更加简洁和优美。

位运算应用口诀：
清零取反要用与，某位置一可用或
若要取反和交换，轻轻松松用异或

一：简介

1、位逻辑运算符：

     & （位   “与”）  and      

     ^  （位   “异或”）      

     |   （位    “或”）   or      

     ~  （位   “取反”）

2、移位运算符：      

    <<（左移）

    >>（右移）

优先级

位“与”、位“或”和位“异或”运算符都是双目运算符，其结合性都是从左向右的，优先级高于逻辑运算符，低于比较运算符，且从高到低依次为&、^、|

二：位逻辑运算

1、& 运算  

运算规则：2个都为1结果为1

   0&1 =0;     0&0 =0;    1&0 =0;   1&1 =1;

   常见应用：

   &运算通常用于二进制取位操作，例如一个数 &1的结果就是取二进制的最末位。

   这可以用来判断一个整数的奇偶，二进制的最末位为0表示该数是偶数，最末位为1表示该数为奇数

2、| 运算

   运算规则：1个为1结果为1

   0|0=0;      0|1=1;    1|0=1;   1|1=1;

   常见应用：

（1）| 运算通常用于二进制特定位上的无条件赋值，例如一个数|1的结果就是把二进制最末位强行变为1

（2）如果需要把二进制最末位变成0，对这个数 |1之后再减一就可以了，其实际意义就是把这个数强行变成最近接的偶数

3、^ 运算

运算规则：不同则为1，相同则为0 // 当且仅当两个运算值中有一个为1但不同时为1时，返回值为1

   0^1=1；    1^0=1；    1^1=0；    0^0=0；

   常见应用：

（1）^运算通常用于对二进制的特定一位进行取反操作，^运算的逆运算是它本身，也就是说两次异或同一个数最后结果不变，即（a^b)^b=a；

（2）^运算可以用于简单的加密，比如原始值int a = 19880516;密钥 int key =1314520; 进行加密 int data=key^a = 20665500;解密 data^key == a；

（3）^运算还可以实现两个值的交换而不需要中间变量，例如：

1. void swap(long int &a,long int &b){
2.     a = a^b;b = a^b;a = a^b;
3. }

4、~运算

运算规则：~运算的定义把内存中的0和1全部取反，所以~运算时要格外小心，你需要注意整数类型有没符号，如果~的对象是无符号整数（不能表示负数），那么他的值就是它与它的上界限的之差，因为无符号类型的数是用0000到0000到FFFF依次表示的。

例如：下面程序返回65435。

1. #include <iostream>
2. #include <cstdio>
3. using namespace std;
4. int main()
5. {
6. unsigned short a = 100;
7.        a = ~a;
8. printf(“%d\n”,a);
9. return 0;
10. }

如果 ~的对象是有符号的整数，情况就不一样了。

三：位移运算

1、<<运算

运算规则：a<<b 表示把a转为二进制后左移b位（在后面添加 b个0）。

例如100的二进制表示为1100100，100左移2位后（后面加2个零）：1100100<<2 =110010000 =400，可以看出，a<<b的值实际上就是a乘以2的b次方，因为在二进制数后面添加一个0就相当该数乘以2，2个零即2的2次方 等于4。通常认为a<<1比a*2更快，因为前者是更底层一些的操作。因此程序中乘以2的操作尽量用左移一位来代替。

定义一些常量可能会用到<<运算。你可以方便的用1<<16 -1 来表示65535（unsigned int  最大值16位系统）。很多算法和数据结构要求数据模块必须是2的幂，此时就可以用<<来定义MAX_N等常量。

2、>>运算

运算规则：a>>b表示二进制右移b位（去掉末b位），相当于a除以2的b次方（取整）。

我们经常用>>1来代替 /2（div 2),比如二分查找、堆的插入操作等等。想办法用>>代替除法运算可以使程序的效率大大提高。最大公约数的二进制算法用除以2操作来代替慢的出奇的%（mod）运算，效率可以提高60%。

int a =100;

a/4 ==a>>2;

位移运算运用例子

1、合并数据

   缩短数据：

1. int a =4;
2. int b=2;  可以将数据 a,b 保存于一个变量 int c中,在此int 类型为32位。    
3. a=0x0000 0004; //十六进制    
4. b=0x0000 0002;    
5. int c = a<<16;//左移操作-将a数据向左移动16位=0x0004 0000     
6. c |=b;  
7. // （|） 操作，一个为1 则为1，所以高16位不变，低16位值为 b值，即c = 0x0004 0002;完成数据的合并

2、解析数据

   上面c = 0x0004 0002;

   读取高位：int a1 = c>>16; // 右移16位，消除低位数据，读取高位数据 a1 = 0x0000 0004

   读取低位：int a2 = c&0xFFFF; //（&）操作，2个都为1 则为1，所以0xFFFF 即 0X0000 FFFF, 所以高位全为0，低位的 1不变，0还是0，a2=0x0000 0002,读取低位成功

   读取低位2：int a2 = c<<16; 消除高位，低位存入高位，a2=0x0002 0000;

   2 = a2>>16;高位存入低位，消除低位; a2 = 0x0000 0002;

                      一些常见的二进制位的变换操作：