（1）基本知识
位运算的题目经常出现在面试中。在此总结一下关于位运算的知识点。
位运算是把数字用于二进制表示之后，对每一位上的0,1的运算。
其实二进制的位运算并不是很难掌握，因为位运算总共只有五种运算：与，或，异或，左移和右移。
左移：
左移运算符m <<n 表示把m左移n位。在左移n位的时候，最左边的n位将被丢弃，同时在最右边补上n个0。
比如：
00001010 << 2 = 00101000
10001010 << 3 = 01010000
右移：
右移运算符m >> n表示把m右移n位。右移n位的时候最右边的n位将被丢弃。但注意的是右移时候的最左边的n位的处理。
如果数字是一个为无符号数值，则用0填补最左边的n位。如果数字是一个有符号数值，则用数字的符号位填补最左边的n位。
也就是说如果原先数字是一个整数则右移之后最左边补上n个0,；如果数字原始是负数，则右移之后在左边补n个1。
比如：
00001010 >> 2 = 00000010
10001010 >> 3 = 11110001
注意以下几点：
1.在这5种操作符，都是双目操作符。只有~取反是单目操作符，在这没有提及。
2.位操作只能用于整形数据，对float和double类型进行位操作会被编译器报错。
3.对于移位操作，在微软的VC6.0和VS2008编译器都是采取算术称位即算术移位操作，算术移位是相对于逻辑移位，它们在左移操作中都一样，低位补0即可，但在右移中逻辑
移位的高位补0而算术移位的高位是补符号位。
4.位操作符的运算优先级比较低，因为尽量使用括号来确保运算顺序，否则很可能会得到莫明其妙的结果。比如要得到像1，3，5，9这些2^i+1的数字。写成int a = 1 << i + 1;是
不对的，程序会先执行i + 1，再执行左移操作。应该写成int a = (1 << i) + 1;
5.另外位操作还有一些复合操作符，如&=、|=、 ^=、<<=、>>=。
（2）位运算常用技巧
1.判断奇偶
只要根据最未位是0还是1来决定,为0就是偶数,为1就是奇数。因此可以用if((a & 1) == 0)代替if(a % 2 == 0)来判断a是不是偶数。
int a = 4;
if(a & 1){
printf("%d是奇数!\n",a);
}
else{
printf("%d是偶数!\n",a);
}
2.交换数据
//临时变量法交换数据
void swap(int &a, int &b){
int temp;
if (a != b){
temp = a;
a = b;
b = temp;
}
}
//位运算法交换数据
void swap2(int &a, int &b){
if (a != b){
a ^= b;
b ^= a;
a ^= b;
}
}
第一步 a^=b 即a=(a^b);
第二步 b^=a即b=b^(a^b)，由于^运算满足交换律，b^(a^b)=b^b^a。
由于一个数和自己异或的结果为0并且任何数与0异或都会不变的，所以此时b被赋上了a的值。
第三步 a^=b 就是a=a^b，由于前面二步可知a=(a^b)，b=a，所以a=a^b即a=(a^b)^a。故a会被赋上b的值。
比如：
int a = 13, b = 6;
a的二进制为 13=8+4+1=1101(二进制)
b的二进制为 6=4+2=110(二进制)
第一步 a^=b a = 1101 ^ 110 = 1011;
第二步 b^=a b = 110 ^ 1011 = 1101;即b=13
第三步 a^=b a = 1011 ^ 1101 = 110;即a=6
3.变换符号
变换符号就是正数变成负数，负数变成正数。
如对于-11和11，可以通过下面的变换方法将-11变成11
1111 0101(二进制) 取反-> 0000 1010(二进制) 加1-> 0000 1011(二进制)
同样可以这样的将11变成-11
0000 1011(二进制) 取反-> 0000 0100(二进制) 加1-> 1111 0101(二进制)
因此变换符号只需要取反后加1即可。
int a = 4;
int b = ~a + 1;
printf("%d\n",b);
int c = -4;
int d = ~c + 1;
printf("%d\n",d);
4.求绝对值
位操作也可以用来求绝对值，对于负数可以通过对其取反后加1来得到正数。
对-6可以这样：
1111 1010(二进制) –取反->0000 0101(二进制) -加1-> 0000 0110(二进制)
来得到6。
因此先移位来取符号位，int i = a >> 31;
要注意如果a为正数，i等于0，为负数，i等于-1。
然后对i进行判断:如果i等于0，直接返回。否之，返回~a+1。
//取符号位
int a = -100;
int i = a >> 31;
//i = 0 正数
if(i == 0){
printf("%d\n",a);
}
//i = 1 负数
else{
printf("%d\n",~a + 1);
}
对于任何数，与0异或都会保持不变，与-1即0xFFFFFFFF异或就相当于取反。
因此，a与i异或后再减i（因为i为0或-1，所以减i即是要么加0要么加1）也可以得到绝对值。
int a = -100;
int i = a >> 31;
int b = ((a ^ i) - i);
printf("%d\n",b);
（3）位运算应用
它即是十进制的55430。
这个问题用位操作解决起来非常方便，设x=34520= 10000110 11011000(二进制) 由于x为无符号数，右移时会执行逻辑右移即高位补0，因此x右移8位将得到00000000 10000110。而x左移8位将得到 11011000 00000000。可以发现只要将x>>8与x<<8这两个数相或就可以得到 11011000 10000110。
2.判断一个整数是不是2的整数次方
如果一个整数是2的整数次方，那么他的二进制标识中一定有且只有一位是1，而其他所有位均为0.
解决方案：
把这个整数减去1之后再和他自己做与运算，这个整数中唯一的一个1就会变成0.所以只要判断是不是等于0即可。
