位操作是一种很底层的操作二进制数据的方法，虽然比较难掌握，但是有时候却有更高的效率和难以名状的优雅感。而且，在面试或者笔试中，考察基本的位操作应用越老越普遍，所以掌握位操作的基本操作和应用很有必要。
我们先从基本的位操作概念和基础谈起，并介绍其在程序中的用处比较多的应用，最后根据几道常用的算法题来总结升华。

什么是位操作

我们都知道数据在计算机存储的形式是二进制数据，位操作就是一种在二进制层面操作数据的方法，位操作直接操作0,1构成的二进制数据。

基本的位操作

基本的位操作有六种，分别是 ** 与 或 非 异或 左移 右移 **

符号	描述	运算规则
&	与	两个位都为1时，结果才为1
或	两个位都为0时，结果才为0
^	异或	两个位相同时，结果为1，不相同为0
~	取反	0变1,1变0
<<	左移	各二进位全部左移若干位，高位丢弃，低位补0
>>	右移	各二进位全部左移若干位，高位丢弃，高位补符号位，或者补零，根据不同编译器

• ** 首先，必须明确位操作只能对整数进行操作 **
• 在jdk中，java右移是进行算术右移操作
• ** 位操作的优先级很低，所以最好用括号 **

public class Byte {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int a = 13, b = -13;
        System.out.println(a>>2);
        System.out.println(b>>2);
    }

}

上述代码的输出结果：

byte.PNG

下面我们就分析一下为什么会输出这个结果：

• 首先对于13，我们写出他的二进制：0000 1101
• 右移两位： 0000 0011，由于jdk中的右移是算术右移，所以高位补00，结果为3
• 对于-13，二进制代码： 1111 0011
• 右移两位，高位补符号位，1111 1100，结果是-4

位操作的常用技巧

位操作经常用于一些小操作，由于他只能操作整形数，所以用途有限，但是一些常用的小技巧是非常值得掌握的，判断奇偶，交换两数，交换符号，求绝对值等。下面我们就将一一介绍。

判断奇偶

奇偶的区别体现在二进制上，就是末尾是0,1 显然当末尾为0时，是偶数，当末尾为1是最后一位奇数。所以判断奇偶的方法是：

if (a & 1 == 0)
  为偶数
else
  为奇数  

一个小的测试程序：

        for(int i=0;i<1000;i++)
        {
            if((i & 1) == 0)
                System.out.println(i);
        }

上面这个程序将会输出所有1000以内的偶数

交换两数

利用位操作交换两个数的好处是不用第三个temp变量(局限是只能交换整数变量)

        if (a != b)  
        {  
            a ^= b;  
            b ^= a;  
            a ^= b;  
        } 

分析一下交换是怎么产生的：
首先 a^=b 即a=(a^b);
b^=a 即b=b^(ab)，由于^{运算满足交换律，b}(a^b)=bb^a。一个数和自己异或肯定是0，因为自己肯定是等于自己的啦，那么一个数和0异或的话，1和0异或还是1，0和0异或还是0，所以显然一个数和0异或之后当然还是自己本身。所以此时，b被赋值为a。
最后一步，a^=b 就是a=a^{b，由于前面二步可知a=(a}b)，b=a，所以a=a^b即a=(ab)^a。故a会被赋上b的值。

变换符号

变换符号显然很简单，根据类似补码，取反加一就可以了。

int SignReversal(int a)  
{  
    return ~a + 1;  
} 

求绝对值

求绝对值就是在变换符号的基础上实现的，我们只要先判断是否为负数，若是负数，就变换符号，不是，就直接返回。
判断正负可以直接判断其符号位，右移31位，取到符号位,判断正负

int my_abs(int a)  
{  
    int i = a >> 31;  
    return i == 0 ? a : (~a + 1);  
}

对于任何数，与0异或都会保持不变，与-1即0xFFFFFFFF异或就相当于取反。因此，a与i异或后再减i（因为i为0或-1，所以减i即是要么加0要么加1）也可以得到绝对值。所以可以对上面代码优化下：

int my_abs(int a)  
{  
    int i = a >> 31;  
    return ((a ^ i) - i);  
} 

位操作的应用，常见的算法题

位操作实现A+B的操作是常见的算法题。
lintcode上就有一道容易题是这样。

class Solution {
    /*
     * param a: The first integer
     * param b: The second integer
     * return: The sum of a and b
     */
    public int aplusb(int a, int b) {
        // write your code here, try to do it without arithmetic operators.
        if(a==0)return b;  
        if(b==0)return a;  
        int x1 = a^b;  
        int x2 = (a&b)<<1;  
        return aplusb(x1,x2); 
    }
};

上述代码就实现了不用+操作符，利用位操作实现两个数的相加操作。
现在我们来讲解位操作实现两个数相加的原理
首先，十进制中，我们知道，7+8，不进位和是5，进位是1，然后我们可以根据不进位和和进位5+1*10算出最后的结果15。
类似二进制也可以采取这种方法
比如
a = 3，b = 6
a : 0011
b : 0110
不进位和： 0101 也就是5
进位：0010 也就是2
所以a+b变成5 + （2<<1）
5　　　　0101
2<<1 　　0100
不进位和 0001 = 1
进位 0100 = 4
因此 a + b就变成了1 + 4 << 1
然后有
1　　　　0001
4<<1 　　1000
不进位和 1001 = 9
进位 0000 = 0
当时进位为0时，不进位和为9即a + b之和。

可以发现上述是一个递归的过程，所以也就不难写出代码了。求两个数的不进位和实际上就是将两个数异或操作即可。

小结

我们先从六种基本的位操作入手，然后介绍了位操作的常用技巧，判断奇偶，求绝对值，交换符号，交换两个数。最后根据常用的算法题中，利用位操作实现两个数相加。基本总结了位操作简单的应用。
位操作当然还有更丰富复杂的应用，需要我们在学习过程中不断总结。