位运算的基本操作以及实例介绍

谈到位运算，有些人可能感觉位运算很容易出错，但是位运算可以解决很多问题，所以我们有必要掌握位运算的知识，并能用位运算解决问题。

首先我们熟悉一下位运算的基本操作符（java）：
^ （xor） 代表异或，~（not）代表取非，&（and) 代表按位与，|（or）代表按位或
>> 代表右移， << 代表左移，>>>代表无符号右移(用0填充左边的空位)

知道了基本的运算符，我们先看几个小的例子：

1. 0110+0110
在这个例子中，两个相同的数相加，相当于0110*2, 所以我们把0110左移一位就可以了（0110<<1），结果是1100。

2. 0100*0011
因为0100相当于4，相当于2的平方，所以我们把0011左移两位就可以了，结果是1100。

3. 1101^(~1101)
如果我们按位运算它结果是1111，我们可以发现任何一个数异或它本身的非时（a^(~a))，结果是一个1s(1s代表一个1的序列，下面都用1s表示)。

4. 1011&（~0<<2）
这个例子的结果是1000。通过这个例子我们可以总结出一个数x和（~0 << n）进行按位与操作，x的最右边的n为将变为0的序列，换句话说我们清除了x最右边的n位。

通过上面简单的例子我们得到下面的一些基本用法 （0s代表一个全为0的序列）：
1.  ^ 异或
x ^ 0s = x
x ^ 1s = ~x
x ^ x = 0

2. & 位与
x & 0s = 0；
x & 1s = x;
x & x = x

3. | 按位或
x | 0s = x
x | 1s = 1s;
x | x = x;

4. x & (1 << n) （得到特定位）
1左移n位后我们得到一个类似于00001000的序列，所以通过这个例子我们把x所有位置0除了第n位，从而我们得到了第n位。

5. x | (1 << n) （设置特定位）
同第四个例子，1左移n位后我们得到一个类似于00001000的序列，x按位或00001000后我们能改变第n位，把她设置为1，x中其它位不会受到影响。

6. x & (~ (1 << n)) (清除特定位)
1左移n位后我们得到一个类似于00001000的序列，然后取非，得到11110111，x按位与11110111后我们只把第n位置0，其它位不会改变。类似的还有x &( (x << n) - 1) 和x &(~(-1 >>>(31 - i)))

7. (x & (~(1 << n))) | (y << n) (把x的第n位设置成y）
首先我们把x的第n位设置成0，然后把y左移n位得到一个第i位为y，其余位为0的序列，把这两个数位或就把x的第n位设置成了y。

很多复杂的问题都可以通过这些基本的操作解决。在这里仅仅举几个简单的例子，对于很多题目都可以用位运算解决，希望大家善于思索, 感受位运算的魅力。
1. 给定两个整数 a, b, 如果不用第三个变量， 怎样将两个数的数值交换？

当然我们可以用其他方法解决，但如果我们在面试中用位运算来解决一个问题，也许会让面试官眼前一亮，这道题我们可以用异或来解决。
首先我们令a = a ^ b; 然后b = a ^ b, 相当与 b = a ^ b ^ b = a ^ 0 = a; 最后我们令 a = a ^ b, 此时b = a, 也就是 a = a ^ b ^ a = b。从而完成了两个值的交换。

2. 给定两个整数A, B，写一个方法确定需要几次换位才可以将A变为B。
比如 A: 11010  B: 01100  输出：3

我们首先要知道那些位需要替换，我们很容易想到异或这个功能，A^B，相同的位异或为0，不同的位异或为1，所以我们只需要确定异或之后的数有几个1即可。我们怎么确定呢？上面讲到了如何清除特定位，这里是个特例，例如A^B = x, 我们让x&(x-1)，这个操作清除了x最右边的1，我们通过一个循环确定次数，直到x为0结束。代码如下：

public int bitSwapNums(int a, int b) {
		int count = 0;
		for(int i = a ^ b; i > 0; i= i & (i - 1)){
			count ++;
		}
		return count;
}

位运算的应用很灵活，我们也可以这样实现

public int bitSwapNums(int a, int b) {
                int count = 0;
		for(int i = a ^ b; i > 0; i = i >> 1) {
			count += i & 1;
		}
		return count;
}

每次循环i右移一位，通过与1进行位与得到1的个数。