Java位向量的实现原理与巧妙应用
Java位向量的实现原理与巧妙应用
1、博文介绍
本篇博文将会介绍几本的位运算含义、位向量介绍、BitSet实现原理、Java位向量的应用、拓展介绍Bloom Filter等。
2、位运算介绍
1) 位运算符
java中位运算操作符主要包括:
&: 与
|: 或
^: 异或
~: 非
前三种可以和 = 结合使用,比如 &=、|=、^=;但是~是单目运算符,不能和=结合使用。
<<: 左移运算,相当于乘法,低位补0;
>>: 右移运算,相当于除法,有符号移位若高位为正,则高位补0,若为负,则高位补1;
java中增加了一种"无符号"右移,>>>,它使用零扩展,无论正负都在高位插入0;
移位操作与等号也可以组合使用: >>=、<<=
2)位运算简单应用
// 1. 获得int型最大值;2147483647的十六进制为0x7FFFFFFF,其中最高位为符号位 System.out.println((1 << 31) - 1);// 2147483647, 由于优先级关系,括号不可省略 System.out.println(~(1 << 31));// 2147483647 // 2. 获得int型最小值 System.out.println(1 << 31); System.out.println(1 << -1); // 3. 判断一个数n是不是2的幂 System.out.println((n & (n - 1)) == 0); /*如果是2的幂,n一定是100... n-1就是1111.... 所以做与运算结果为0*/ // 4. 计算2的n次方 n > 0 System.out.println(2<<(n-1)); // 5. 从低位到高位,将n的第m位置为0 System.out.println(n & ~(0<<(m-1))); /* 将1左移m-1位找到第m位,取反后变成111...0...1111 n再和这个数做与运算*/ // 6. 从低位到高位,取n的第m位 int m = 2; System.out.println((n >> (m-1)) & 1); // 7. 从低位到高位.将n的第m位置为1 System.out.println(n | (1<<(m-1))); /*将1左移m-1位找到第m位,得到000...1...000 n在和这个数做或运算*/ // 8. 获得long类型的最大值 System.out.println(((long)1 << 127) - 1); // 9. 乘以2运算 System.out.println(10<<1); // 10. 求两个整数的平均值 System.out.println((a+b) >> 1); // 11. 除以2运算(负奇数的运算不可用) System.out.println(10>>1); // 12. 判断一个数的奇偶性,利用的是最后一位 System.out.println((10 & 1) == 1); System.out.println((9 & 1) == 1); // 13. 不用临时变量交换两个数(面试常考) a ^= b; b ^= a; a ^= b; // 14. 取绝对值(某些机器上,效率比n>0 ? n:-n 高) int n = -1; System.out.println((n ^ (n >> 31)) - (n >> 31)); /* n>>31 取得n的符号,若n为正数,n>>31等于0,若n为负数,n>>31等于-1 若n为正数 n^0-0数不变,若n为负数n^-1 需要计算n和-1的补码,异或后再取补码, 结果n变号并且绝对值减1,再减去-1就是绝对值 */ // 15. 取两个数的最大值(某些机器上,效率比a>b ? a:b高) System.out.println(b&((a-b)>>31) | a&(~(a-b)>>31)); // 16. 取两个数的最小值(某些机器上,效率比a>b ? b:a高) System.out.println(a&((a-b)>>31) | b&(~(a-b)>>31)); // 17. 判断符号是否相同(true 表示 x和y有相同的符号, false表示x,y有相反的符号。) System.out.println((a ^ b) > 0);
3)应用 - 小游戏中状态的判断,如斗地主判断四人是否处于准备状态
充分利用一个位有两种状态,可以代表开闭、是否准备好等二状态场景中,即便是多状态也可以用多位来实现,比如在迷宫问题中,可以用00 01 10 11 来代表四个方向。如果正常的判断四人是否处于准备状态,可定义四个变量,但是如果用位运算,则一个byte类型变量的低4位就足够了。
在提高运行速度的同时,也对程序的可读性造成了影响,上面只是举例位运算可以应用在类似的场景中,具体适不适合根据项目背景而定。可以使用设计模式来解决,底层用位实现,封装到上层之后只公开方法。
实现代码:
/** * Java 位运算的常用方法封装<br> */ public class BitUtils { /** * 获取运算数指定位置的值<br> * 例如: 0000 1011 获取其第 0 位的值为 1, 第 2 位 的值为 0<br> * * @param source * 需要运算的数 * @param pos * 指定位置 (0<=pos<=7) * @return 指定位置的值(0 or 1) */ public static byte getBitValue(byte source, int pos) { return (byte) ((source >> pos) & 1); } /** * 将运算数指定位置的值置为指定值<br> * 例: 0000 1011 需要更新为 0000 1111, 即第 2 位的值需要置为 1<br> * * @param source * 需要运算的数 * @param pos * 指定位置 (0<=pos<=7) * @param value * 只能取值为 0, 或 1, 所有大于0的值作为1处理, 所有小于0的值作为0处理 * * @return 运算后的结果数 */ public static byte setBitValue(byte source, int pos, byte value) { byte mask = (byte) (1 << pos); if (value > 0) { source |= mask; } else { source &= (~mask); } return source; } /** * 将运算数指定位置取反值<br> * 例: 0000 1011 指定第 3 位取反, 结果为 0000 0011; 指定第2位取反, 结果为 0000 1111<br> * * @param source * * @param pos * 指定位置 (0<=pos<=7) * * @return 运算后的结果数 */ public static byte reverseBitValue(byte source, int pos) { byte mask = (byte) (1 << pos); return (byte) (source ^ mask); } /** * 检查运算数的指定位置是否为1<br> * * @param source * 需要运算的数 * @param pos * 指定位置 (0<=pos<=7) * @return true 表示指定位置值为1, false 表示指定位置值为 0 */ public static boolean checkBitValue(byte source, int pos) { source = (byte) (source >>> pos); return (source & 1) == 1; } /** * 入口函数做测试<br> * * @param args */ public static void main(String[] args) { // 取十进制 11 (二级制 0000 1011) 为例子 byte source = 11; // 取第2位值并输出, 结果应为 0000 1011 for (byte i = 7; i >= 0; i--) { System.out.printf("%d ", getBitValue(source, i)); } // 将第6位置为1并输出 , 结果为 75 (0100 1011) System.out.println(" " + setBitValue(source, 6, (byte) 1)); // 将第6位取反并输出, 结果应为75(0100 1011) System.out.println(reverseBitValue(source, 6)); // 检查第6位是否为1,结果应为false System.out.println(checkBitValue(source, 6)); // 输出为1的位, 结果应为 0 1 3 for (byte i = 0; i < 8; i++) { if (checkBitValue(source, i)) { System.out.printf("%d ", i); } } } }