位操作

位操作即将数字转为二进制形式后，按照二进制位进行操作，位操作主要包括如下几种。

1. & 按位与
   1 & 1 = 1,1 & 0 = 0,0 & 0 = 0
2. | 按位或
   1 | 1 = 1,1 | 0 = 1,0 | 0 = 0
3. ^ 异或
   1 ^ 1 = 1,0 ^ 1= 0,0 ^ 0 = 1
4. ~取反
   ~1 = 0, ~0 = 1
5. << 左移(低位补0)
   1 << 2 = 4 0000 0001 左移2位后变为 0000 0100 即十进制4。
   1 << 3 = 8 0000 0001 左移3位后变为 0000 1000 即 十进制8。
   1 << -2 = 1 << (32-2) = 1073741824。
   左移一位相当于乘以2。
6. >> 右移(正数高位补0，负数高位补1）
   7 >> 2 = 1, 0000 0111 右移2位后变为 0000 0001即十进制1。
   8 >> 2 = 2 , 0000 1000 右移2位后变为 0000 0010 即十进制2。
   8 >> 3 = 1, 0000 1000 右移3位后变为 0000 0001 即十进制1。
   右移一位相当于除以2，但只适用于负数。
   -3 >> 2 = -1 因为计算机中负数用补码表示，-3原码为 1000 0011，反码为1111 1100,反码+1得到补码1111 1101,右移2位得1111 1111，即-1
7. >>> 无符号右移(高位补0)
   -1 >>> 2 = 1073741823 , -1 补码为 11111111 .... .... 11111111，右移2位，高位补0 得
   00111111 .... .... 11111111，即1073741823
   -3 >>> 2 = 1073741823 -3 补码为 11111111 .... .... 11111101,右移2位后与-1右移2位效果相同，因此结果也相同。
   3 >>> 2 = 0, 0000 0011 右移2位后变为 0000 0000即十进制0。
   正数无符号右移效果与右移相同，负数则需要特殊注意一下。

常见技巧

将某个数的二进制的最右边的1变成0

n & (n-1)

获得int型最大值

1 << 31

判断一个数奇偶性

n & 1 == 0 偶数
n & 1 == 1 奇数

判断一个数是不是2得n次幂

n & (n-1) == 0 

从低位到高位，取n的第m位

return (n >> (m-1) ) & 1

从低位到高位，将n的第m位置1

return n | (1 << (m-1));

从低位到高位，将n的第m位置0

return n & ~(1 << (m-1));

经典题型

不用临时变量交换变量a,b

a^=b
b^=a
a^=b

利用的主要性质就是一个数异或自己的结果为0，任何数与0异或结果不变。
即b = b^ a ^b = b ^ b ^ a = 0 ^ a = a, a = a^ba = a ^ a ^b = 0 ^ b = b

不用+ - * / 实现a，b俩数相加(来源剑指offer)

int result;
int sum;
int carry;
do{
     sum = a^b;
     carry = (a & b) << 1;
     a = sum;
     b = carry;
}(carry != 0);
return sum;

要实现加法运算而又不能使用加减乘除等运算符，那么只能使用位运算来进行运算了，同时异或操作又称为半加运算，其运算法则相当于不进位的加法，所以可以先通过异或实现不进位的a+b，再求得进位，将二者相加，但二者相加同样需要采用上面的办法。循环这两个过程直到进位为0。

计算一个数二进制表示中1的个数(来源剑值offer)

int count = 0;
int flag = 1;
while (flag != 0) {
    if ((flag & n) != 0)
        count++;
    flag = flag << 1;
 }
 return count;

通过移位与1作&运算看结果是否为0来判断这一思路较容易想到，不过需要将1不断左移而不是将n不断右移，因为负数右移高位会补1，最终会无限循环。