Java中的位运算及简单的算法应用介绍
程序员文章站
2022-05-25 12:23:18
众所周知,计算机底层是二进制。而java作为一门计算机编程语言,也对二进制的位运算提供了完整的支持。 在java中,int是32位的,也就是说可以用来实现32位的位运算。方便起见,我们一般用16进制对它赋值,比如: 0011表示成16进制是 0x3, 110111表示成16进制是 0x37。 那么什 ......
众所周知,计算机底层是二进制。而java作为一门计算机编程语言,也对二进制的位运算提供了完整的支持。
在java中,int是32位的,也就是说可以用来实现32位的位运算。方便起见,我们一般用16进制对它赋值,比如: 0011表示成16进制是 0x3, 110111表示成16进制是 0x37。
那么什么是位运算呢?位运算是将数据看做二进制,进行位级别的操作。主要有移位运算和逻辑运算
移位运算:
- 左移:操作符为<<,向左移动,右边的低位补0,左边高位舍弃,将二进制看做整数,左移1位就相当于乘以2。
- 无符号右移:操作符为>>>,向右移动,右边的舍弃掉,左边补0。
- 有符号右移:操作符为>>,向右移动,右边的舍弃掉,左边补的值取决于原来最高位,原来是1就补1,原来是0就补0,将二进制看做整数,右移1位相当于除以2。
例如:
int a = 4; // 100 a = a >> 2; // 001,等于1 a = a << 3 // 1000,变为8
逻辑运算有:
- 按位与 &:两位都为1才为1
- 按位或 |:只要有一位为1,就为1
- 按位取反 ~: 1变为0,0变为1
- 按位异或 ^ :相异为真,相同为假
例如:
int a = ...; a = a & 0x1 // 返回0或1,就是a最右边一位的值。 a = a | 0x1 //不管a原来最右边一位是什么,都将设为1
我们来看几个简单的应用场景:
场景一:判断奇偶
分析:奇数都不是2的整数倍,转换成二进制后最低位必然为1,偶数则相反。利用这个特性我们可以很容易的通过位运算判断一个整数的奇偶性。
看代码:
int i = 1;// 二进制存储方式为00000000000000000000000000000001 int j = 5;// 二进制存储方式为00000000000000000000000000000101 int k = 6;// 二进制存储方式为00000000000000000000000000000110 if ((i & j) == 1) { System.out.println("j的最低位为1,为奇数"); } if ((i & k) == 0) { System.out.println("k的最低位为0,为偶数"); }
场景二:判断一个正整数是不是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的整数次幂了。
场景三:简单的集合处理
不废话,直接看代码:
public class SimpleSet { public static final int A = 0x01;// 最后四位为0001 public static final int B = 0x02;// 最后四位为0010 public static final int C = 0x04;// 最后四位为0100 public static final int D = 0x08;// 最后四位为1000 private int set = 0x00;// 初始0000,空集合 public void add(int i) {// 将i对应位的值置为1,重复add不影响。默认传入值为ABCD之一,此处省去边界判断 set |= i; } public boolean contain(int i) {// 判断相应位置是否为1 return (set & i) == i; } public boolean remove(int i) {// 来不及不解释了快看代码 if (contain(i)) { set -= i; return true; } else { return false; } } }
测试一下:
public static void main(String[] args) { SimpleSet set = new SimpleSet(); System.out.println(set.contain(A)); set.add(B); System.out.println(set.contain(A)); System.out.println(set.contain(B)); set.add(A); set.add(C); System.out.println(set.contain(A)); set.remove(A); System.out.println(set.contain(A)); System.out.println(set.remove(A)); System.out.println(set.contain(C)); }
输出为:
false false true true false false true
好的,没有问题。
大家可能会觉得,上面的示例代码中的A、B、C、D有点类似于枚举,事实上jdk源码中的关于枚举的集合类EnumSet使用的就是类似的方案,当然比这个复杂得多,有兴趣的可以去翻一下源码,这个方案它有个名字,叫位向量
结语:
位运算是计算机最擅长的运算,jdk的源码中也大量地使用了它,搞明白它有助于我们更加深入的理解计算机,也有助于我们写出更优雅的代码。