[TOC]
Java中的位运算及简单的算法应用介绍
众所周知，计算机底层是二进制。而java作为一门计算机编程语言，也对二进制的位运算提供了完整的支持。在java中，int是32位的，也就是说可以用来实现32位的位运算。方便起见，我们一般用16进制对它赋值，比如： 0011表示成16进制是 0x3, 110111表示成16进制是 0x37。那么什么是位运算呢？位运算是将数据看做二进制，进行位级别的操作。主要有移位运算和逻辑运算
移位运算
- 左移：操作符为<<，向左移动，右边的低位补0，左边高位舍弃，将二进制看做整数，左移1位就相当于乘以2。
- 无符号右移：操作符为>>>，向右移动，右边的舍弃掉，左边补0。
- 有符号右移：操作符为>>，向右移动，右边的舍弃掉，左边补的值取决于原来最高位，原来是1就补1，原来是0就补0，将二进制看做整数，右移1位相当于除以2。
例如：
1int a = 4; // 100 2a = a >> 2; // 001，等于1 3a = a << 3 // 1000，变为8
逻辑运算
- 按位与 &：两位都为1才为1
- 按位或 |：只要有一位为1，就为1
- 按位取反 ~： 1变为0，0变为1
- 按位异或 ^ ：相异为真，相同为假
例如：
1int a = ...; 2a = a & 0x1 // 返回0或1，就是a最右边一位的值。 3a = a | 0x1 //不管a原来最右边一位是什么，都将设为1
我们来看几个简单的应用场景：
场景一：判断奇偶
分析: 奇数都不是2的整数倍，转换成二进制后最低位必然为1，偶数则相反。利用这个特性我们可以很容易的通过位运算判断一个整数的奇偶性。
看代码：
1 int i = 1;// 二进制存储方式为00000000000000000000000000000001 2 int j = 5;// 二进制存储方式为00000000000000000000000000000101 3 int k = 6;// 二进制存储方式为00000000000000000000000000000110 4 if ((i & j) == 1) { 5 System.out.println("j的最低位为1，为奇数"); 6 } 7 if ((i & k) == 0) { 8 System.out.println("k的最低位为0，为偶数"); 9 }
场景二：判断一个正整数是不是2的整数次幂
分析：我们先来看一下常见的2的整数次幂的数：2、4、8、16，转化成二进制依次为：10、100、1000、10000，发现规律了没有？那就是除了首位是1，其他全是0。恰巧这些数减去1后等于他们依次按位取反的结果，比如8-1=7，二进制是111，可以通过8的二进制1000按位取反得到。而8&7=0。
提取一下规律就是： (n&(n-1))==0
符合这个规律的n就是2的整数次幂了。
场景三：简单的集合处理
1public class SimpleSet { 2 public static final int A = 0x01;// 最后四位为0001 3 public static final int B = 0x02;// 最后四位为0010 4 public static final int C = 0x04;// 最后四位为0100 5 public static final int D = 0x08;// 最后四位为1000 6 7 private int set = 0x00;// 初始0000，空集合 8 9 //1就表示存入了这个值 0 就表示没有 一个位存一个值 10 // 0111 就表示存入了 ABC 11 public void add(int i) {// 将i对应位的值置为1，重复add不影响。默认传入值为ABCD之一，此处省去边界判断 12 set = set | i; 13 System.out.println(set); 14 } 15 16 public boolean contain(int i) {// 判断相应位置是否为1 17 return (set & i) == i; 18 } 19 20 public boolean remove(int i) {// 来不及不解释了快看代码 21 //如果存在就减一 返回真 代表删除成功 否则返回 false 失败 22 if (contain(i)) { 23 set -= i; 24 return true; 25 } else { 26 return false; 27 } 28 } 29 public static void main(String[] args) { 30 SimpleSet set = new SimpleSet(); 31 System.out.println(set.contain(A)); 32 set.add(B); 33 System.out.println(set.contain(A)); 34 System.out.println(set.contain(B)); 35 set.add(A); 36 set.add(C); 37 System.out.println(set.contain(A)); 38 set.remove(A); 39 System.out.println(set.contain(A)); 40 System.out.println(set.remove(A)); 41 System.out.println(set.contain(C)); 42 } 43}
大家可能会觉得，上面的示例代码中的A、B、C、D有点类似于枚举，事实上jdk源码中的关于枚举的集合类EnumSet使用的就是类似的方案，当然比这个复杂得多，有兴趣的可以去翻一下源码，这个方案它有个名字，叫<u>位向量</u>。
顺便提一句，java中int的包装类Integer里面有很多静态工具方提供位运算操作，且大都十分复杂，感兴趣的可以去看看
结语：位运算是计算机最擅长的运算，jdk的源码中也大量地使用了它，搞明白它有助于我们更加深入的理解计算机，也有助于我们写出更优雅的代码。