Java 数据结构 算法 二进制

Java 中的位运算和实际应用

Java 算法和数据结构

Posted by 金志宏 on August 21, 2018

JAVA 中的位运算和实际应用

前言：

​ 作为一个有近8年 JAVA 开发经验的老程序员，再加上工作性质比较偏于项目管理，平时工作中对于位运算和二进制数的运算和应用比较少。偶尔看一些源码，对于出现的位运算符总是一脸懵逼，不得不再回炉重新温习一下，这篇文章记录一下自己的学习过程，加深印象。接下来就开始吧！

1. 数学中的二进制

​ 先简单介绍下二进制，二进制是用0和1两个数码表示的数字，进位规则是“逢二进一”，借位规则是“借一当二”。程序员都知道，二进制在当代计算机中非常微小的开关，用”开（true）“表示1，”关（false）“表示0。二进制数据采用的位置计数法，其权位是以 2 为底的幂。

1.1 二进制转十进制

例1：二进制数 1101 与十进制转换： (1 x 2³) + (1 x 2²) + (0 x 2¹) + (1 x 2⁰) = 8 + 4 + 0 + 1 = 13 例2：二进制数 111.01 与十进制转换： (1 x 2²) + (1 x 2¹) + (1 x 2⁰) + (0 x 2⁻¹) + (1 x 2⁻²) = 4 + 2 + 1 + 0 + 0.25 = 7.25

浮点型的二进制数在Java中用的不多，后面就暂且不论

1.2 十进制转二进制

除以2取余，逆序排列 *(除二取余法)* 例：89 = 1011001

十进制数/2 商(下次的被除数) 余数（二进制数）
89 / 2 44 1
44 / 2 22 0
22 / 2 11 0
11 / 2 5 1
5 / 2 2 1
2 / 2 1 0
1 / 2 0 1

以上表格中的余数倒过来，就是 89 对应的二进制数

2. JAVA 中的二进制

2.1 二进制转十进制

​ Java 中的二进制数是以 0b + 数字形式，b 大小写不限制，例如：0b101 表示二级制数 101，可以直接赋值到 十进制的 int 基本数据类型。常见表示方法有 int binary = 0b101;

int binary = 0b101;
System.out.println("0b101 = " + binary);
//输出是：0b101 = 5

2.2 十进制转二进制

​ 通过 Integer 的整型包装类中的方法 toBinaryString 可以把十进制转换成二进制然后通过字符串输出。

int i = 5;
String binary = Integer.toBinaryString(i);
System.out.println(i + " = " + binary);
//输出是：5 = 101

3. 位运算符

​ 位运算符用来对二进制位进行操作，Java 中提供了如下表所示的位运算符：位运算符中，除 ~ 以外，其余均为二元运算符。

运算符 描述
& 与，两个二进制数如果相对应位都是1，则结果为1，否则为0
| 或，两个二进制数如果相对应位都是0，则结果为0，否则为1。
^ 异或，如果相对应位值相同，则结果为0，否则为1
~ 非（取反），按位取反运算符翻转操作数的每一位，即0变成1，1变成0。 一元运算符
<< 按位左移，左操作数按位左移右操作数指定的位数。
>> 按位右移，左操作数按位右移右操作数指定的位数。
>>> 无符号按位右移，左操作数的值按右操作数指定的位数右移，移动得到的空位以零填充。

​ 在计算机中位运算符比数学中常规的加减乘除*效率高很多*，对于一些追求效率的数据结构或者算法来说，掌握位运算符的用法会让程序员在开发过程中如虎添翼，但是目前来看用的真的不是很多，可能和可读性不高有关吧。总之希望读者看了这篇文章后能对位运算符能有所了解，更能实际运用到自己的项目或者工作中去。

​ Java 中位运算符只能针对整型，除long型外，其他类型会自动转成int型，转换之后再进行位运算。首先复习一下Java中基本数据类型，也叫 Java 的内置数据类型如下表：

数据类型 大小 最小 最大
boolean      
byte 8-bit - 128 + 127
char 16-bit \u0000 \u65535
short 16-bit -2¹⁵ + 2¹⁵-1
int 32-bit -2³¹ + 2³¹-1
long 64-bit -2⁶³ + 2⁶³-1
float 32-bit IEEE 754 IEEE 754
double 64-bit IEEE 754 IEEE 754

​ 以上基本数据类型除了boolean外对应二进制的位数在Java中可以通过他们的包装类型获取 如下：

// byte
System.out.println("基本类型：byte 二进制位数：" + Byte.SIZE);
System.out.println("包装类：java.lang.Byte");
System.out.println("最小值：Byte.MIN_VALUE=" + Byte.MIN_VALUE);
System.out.println("最大值：Byte.MAX_VALUE=" + Byte.MAX_VALUE);
System.out.println();

// short
System.out.println("基本类型：short 二进制位数：" + Short.SIZE);
System.out.println("包装类：java.lang.Short");
System.out.println("最小值：Short.MIN_VALUE=" + Short.MIN_VALUE);
System.out.println("最大值：Short.MAX_VALUE=" + Short.MAX_VALUE);
System.out.println();

// int
System.out.println("基本类型：int 二进制位数：" + Integer.SIZE);
System.out.println("包装类：java.lang.Integer");
System.out.println("最小值：Integer.MIN_VALUE=" + Integer.MIN_VALUE);
System.out.println("最大值：Integer.MAX_VALUE=" + Integer.MAX_VALUE);
System.out.println();

// long
System.out.println("基本类型：long 二进制位数：" + Long.SIZE);
System.out.println("包装类：java.lang.Long");
System.out.println("最小值：Long.MIN_VALUE=" + Long.MIN_VALUE);
System.out.println("最大值：Long.MAX_VALUE=" + Long.MAX_VALUE);
System.out.println();

// float
System.out.println("基本类型：float 二进制位数：" + Float.SIZE);
System.out.println("包装类：java.lang.Float");
System.out.println("最小值：Float.MIN_VALUE=" + Float.MIN_VALUE);
System.out.println("最大值：Float.MAX_VALUE=" + Float.MAX_VALUE);
System.out.println();

// double
System.out.println("基本类型：double 二进制位数：" + Double.SIZE);
System.out.println("包装类：java.lang.Double");
System.out.println("最小值：Double.MIN_VALUE=" + Double.MIN_VALUE);
System.out.println("最大值：Double.MAX_VALUE=" + Double.MAX_VALUE);
System.out.println();

// char
System.out.println("基本类型：char 二进制位数：" + Character.SIZE);
System.out.println("包装类：java.lang.Character");
// 以数值形式而不是字符形式将Character.MIN_VALUE输出到控制台
System.out.println("最小值：Character.MIN_VALUE="
        + (int) Character.MIN_VALUE);
// 以数值形式而不是字符形式将Character.MAX_VALUE输出到控制台
System.out.println("最大值：Character.MAX_VALUE="
        + (int) Character.MAX_VALUE);

//控制台输出如下
基本类型：byte 二进制位数：8
包装类：java.lang.Byte
最小值：Byte.MIN_VALUE=-128
最大值：Byte.MAX_VALUE=127

基本类型：short 二进制位数：16
包装类：java.lang.Short
最小值：Short.MIN_VALUE=-32768
最大值：Short.MAX_VALUE=32767

基本类型：int 二进制位数：32
包装类：java.lang.Integer
最小值：Integer.MIN_VALUE=-2147483648
最大值：Integer.MAX_VALUE=2147483647

基本类型：long 二进制位数：64
包装类：java.lang.Long
最小值：Long.MIN_VALUE=-9223372036854775808
最大值：Long.MAX_VALUE=9223372036854775807

基本类型：float 二进制位数：32
包装类：java.lang.Float
最小值：Float.MIN_VALUE=1.4E-45
最大值：Float.MAX_VALUE=3.4028235E38

基本类型：double 二进制位数：64
包装类：java.lang.Double
最小值：Double.MIN_VALUE=4.9E-324
最大值：Double.MAX_VALUE=1.7976931348623157E308

基本类型：char 二进制位数：16
包装类：java.lang.Character
最小值：Character.MIN_VALUE=0
最大值：Character.MAX_VALUE=65535

​ Float和Double的最小值和最大值都是以科学记数法的形式输出的，结尾的”E+数字”表示E之前的数字要乘以10的多少次方。比如3.14E3就是3.14 × 103 =3140，3.14E-3 就是 3.14 x 10-3 =0.00314。实际上，JAVA中还存在另外一种基本类型 void，它也有对应的包装类 java.lang.Void，不过我们无法直接对它们进行操作。

​ 以下我们主要讲int和long类型的位运算，位运算通过对二进制位的操作来快速达到运算目的（因为计算机底层的存储就是按照二进制结构的）比如 int 型的变量占用了32-bit，在计算机中占用 4-byte，每个byte为8字节前面我们说到了 89 = 1011001 可以用以下方式表示

​ Java定义了位运算符，应用于整数类型(int)，长整型(long)，短整型(short)，字符型(char)，和字节型(byte)等类型。位运算符作用在所有的位上，并按位运算。假设a = 60，b = 13; 我们来看看各种位运算之后的运算结果。

3.1 & 与运算

&（与），两个二进制数如果相对应位都是1，则结果为1，否则为0。例如：60 & 13 = 12 60 的二进制数是 111100，13的二进制数是 1101 以32位bit位计算，剩余位数补0，*对于每个位上的操作，进行And比较，如果都是1则结果的相应位也是1，否则是0*。 图示如下：

Java代码：

int a = 60;
int b = 13;
System.out.println(Integer.toBinaryString(a));
System.out.println(Integer.toBinaryString(b));
System.out.println("60 & 13 = " + (a & b));

//控制台输出如下：
111100
1101
二进制 60 & 13 = 1100
十进制 60 & 13 = 12

实际应用：判断奇偶数

判断奇偶数：*假如存在 `a & 1` 结果为 0 ，a 就是偶数。`a & 1 `结果为 1 ，a 就是奇数。* 我们知道，二进制数有 *逢二进一* 的规则，那么凡是偶数，第一位必然是 0 ，奇数第一位必然是 1。通过例子我们也知道 & 运算是两个二进制数的运算，相应位都是1则结果的相应位也是1，对于1来说，第一位是1，其它位都是0。那么任何二进制奇数 & 1，只有第一位满足都是1，所以第一位是1，其它位都是0。如果该二进制数为偶数，如果该二进制数是偶数，则第一位是0，所以 & 1 后，所有位都为 0，我们看下下图就一目了然：

Java 代码：

int a = 60;
int b = 13;
System.out.println(" 60 & 1 = " + (a & 1));
System.out.println(" 13 & 1 = " + (b & 1));
//输出如下：
60 & 1 = 0   //偶数
13 & 1 = 1   //奇数
###3.2 或运算
（或），两个二进制数如果相对应位都是0，则结果为0，否则为1。其实很好理解，或运算正好对与运算，和我们的逻辑运算符 && 和   非常像，我们想象 1 = true，0 = false 。 对于与运算符，需要都为true则true，对于或运算符，只要1个为true则true。图示如下：

Java代码：

int a = 60;
int b = 13;
System.out.println(Integer.toBinaryString(a));
System.out.println(Integer.toBinaryString(b));
System.out.println("二进制 60 | 13 = " + Integer.toBinaryString(a | b));
System.out.println("十进制 60 | 13 = " + (a | b));

//输出
111100
1101
二进制 60 | 13 = 111101
十进制 60 | 13 = 61

3.3 ^ 异或运算符

^（异或），*如果相对应位值相同，则结果为0，否则为1。*这次和前面不同了，相当于逻辑运算符中的 == 和 != 区别是异或运算 == 的话是false ，!= 的话是true，继续撕图：

Java 代码

int a = 60;
int b = 13;
System.out.println(Integer.toBinaryString(a));
System.out.println(Integer.toBinaryString(b));
System.out.println("二进制 60 ^ 13 = " + Integer.toBinaryString(a ^ b));
System.out.println("十进制 60 ^ 13 = " + (a ^ b));

//输出：
111100
1101
二进制 60 ^ 13 = 110001
十进制 60 ^ 13 = 49

实际应用：Swap 两数互换

异或运算符用于 Swap 互换不需要第三个temp变量，*我们可以把异或想象成减法取绝对值，* 在二进制中，由于逢二进一，所以有1 - 1 = 0, 1 - 0 = 1, 0 - 0 = 0这样的特性，所以这三个等式中，任意两个数相减的绝对值都等于第三个数，用这种特性，就能进行Swap的两数互换。

java 代码：

int a = 60;
int b = 13;

System.out.println("a = " + Integer.toBinaryString(a));
System.out.println("b = " + Integer.toBinaryString(b));

System.out.println("a ^= b = " + Integer.toBinaryString(a ^ b));
a ^= b;
System.out.println("b ^= a = " + Integer.toBinaryString(b ^ a));
b ^= a;
System.out.println("a ^= b = " + Integer.toBinaryString(a ^ b));
a ^= b;

System.out.println("a = " + a);
System.out.println("b = " + b);
//输出
a = 111100
b = 1101
a ^= b = 110001
b ^= a = 111100
a ^= b = 1101
a = 13
b = 60

3.4 ~ 非（取反）运算

~（非），*按位取反运算符翻转操作数的每一位，即0变成1，1变成0。*所有的位运算符中，只有 ~ 运算符是一元运算符。如果我们把 1 看做 true 0 看做 false，取反操作就等于是每一位进行 ！操作，!0 或者 !1，看下图。

Java代码：

int a = 60;
int b = 13;

System.out.println("二进制 a = " + Integer.toBinaryString(a));
System.out.println("二进制 ~60 = " + Integer.toBinaryString(~a));
System.out.println("十进制 ~60 = " + (~a));

System.out.println("二进制 b = " + Integer.toBinaryString(b));
System.out.println("二进制 ~13 = " + Integer.toBinaryString(~b));
System.out.println("十进制 ~13 = " + (~b));

//输出
二进制 a = 111100
二进制 ~60 = 11111111111111111111111111000011
十进制 ~60 = -61
二进制 b = 1101
二进制 ~13 = 11111111111111111111111111110010
十进制 ~13 = -14

实际应用：取相反数

首先先看下实际的二进制 int 型整数的 32-bit 存储图，图中最高位为0表示正数 ，1表示负数。int 型二进制最大正整数为 2147483647 ，最小负整数为 -2147483648，最小数恰恰是最大数的二进制数 +1。而且他们正好是互相按位反数，有~ 2147483647 = -2147483648。 直接上图

avatar

通过上图我们发现，对于int 型来说 最大正整数的取反正好是最小负整数，同时最小负整数的递增数的取反操作正好对应了最大正整数的递减数。所以得出取相反数的二进制位运算为 (~x + 1)

Java 代码

int a = 60;
int b = 13;

System.out.println("十进制 a = " + a);
System.out.println("二进制 a = " + Integer.toBinaryString(a));
System.out.println("二进制 ~a + 1 = " + Integer.toBinaryString((~a + 1)));
System.out.println("十进制 ~a + 1 = " + (~a + 1));


System.out.println("十进制 b = " + b);
System.out.println("二进制 b = " + Integer.toBinaryString(b));
System.out.println("二进制 ~b + 1 = " + Integer.toBinaryString((~b + 1)));
System.out.println("十进制 ~b = 1 = " + (~b + 1));

//输出如下：
十进制 a = 60
二进制 a = 111100
二进制 ~a + 1 = 11111111111111111111111111000100
十进制 ~a + 1 = -60
十进制 b = 13
二进制 b = 1101
二进制 ~b + 1 = 11111111111111111111111111110011
十进制 ~b = 1 = -13

3.5 « 按位左移

按位左移，左操作数按位左移右操作数指定的位数。 写作 a « n ，使 a 的二进制数整体向左移动 n 位，并在低位补0。这个操作等同于 a x (2^n^) ，看图说话：

Java 代码：

int a = 60;
int b = 13;

System.out.println("十进制 a = " + a);
System.out.println("二进制 a = " + Integer.toBinaryString(a));
System.out.println("二进制 a << 2 = " + Integer.toBinaryString((a << 2)));
System.out.println("十进制 a << 2 = " + (a << 2));


System.out.println("十进制 b = " + b);
System.out.println("二进制 b = " + Integer.toBinaryString(b));
System.out.println("二进制 b << 2 = " + Integer.toBinaryString((b << 2)));
System.out.println("十进制 b << 2 = " + (b << 2));

//输出如下：
十进制 a = 60
二进制 a = 111100
二进制 a << 2 = 11110000
十进制 a << 2 = 240
十进制 b = 13
二进制 b = 1101
二进制 b << 2 = 110100
十进制 b << 2 = 52

3.6 » 按位右移

按位右移，左操作数按位右移右操作数指定的位数。写作 a » n ，使 a 的二进制数整体向右移动 n 位。这个操作等同于 a / (2^n^) ， 如图：

Java 代码

int a = 60;
int b = 13;

System.out.println("十进制 a = " + a);
System.out.println("二进制 a = " + Integer.toBinaryString(a));
System.out.println("二进制 a >> 2 = " + Integer.toBinaryString((a >> 2)));
System.out.println("十进制 a >> 2 = " + (a >> 2));


System.out.println("十进制 b = " + b);
System.out.println("二进制 b = " + Integer.toBinaryString(b));
System.out.println("二进制 b >> 2 = " + Integer.toBinaryString((b >> 2)));
System.out.println("十进制 b >> 2 = " + (b >> 2));

//输出如下:
十进制 a = 60
二进制 a = 111100
二进制 a >> 2 = 1111
十进制 a >> 2 = 15
十进制 b = 13
二进制 b = 1101
二进制 b >> 2 = 11
十进制 b >> 2 = 3

3.7 >>> 无符号按位右移

按位右移补零操作符。左操作数的值按右操作数指定的位数右移，移动得到的空位以零填充。使 a 的二进制数整体向右移动 n 位，并在高位补0。这个操作等同于 a / (2^n^)，他和 » 区别在于高位补0，所以也叫无符号右移。如下图：

Java 代码：

int a = 60;
int b = 13;

System.out.println("十进制 a = " + a);
System.out.println("二进制 a = " + Integer.toBinaryString(a));
System.out.println("二进制 a >>> 2 = " + Integer.toBinaryString((a >>> 2)));
System.out.println("十进制 a >>> 2 = " + (a >>> 2));


System.out.println("十进制 b = " + b);
System.out.println("二进制 b = " + Integer.toBinaryString(b));
System.out.println("二进制 b >>> 2 = " + Integer.toBinaryString((b >>> 2)));
System.out.println("十进制 b >>> 2 = " + (b >>> 2));

//输出如下：
十进制 a = 60
二进制 a = 111100
二进制 a >>> 2 = 1111
十进制 a >>> 2 = 15
十进制 b = 13
二进制 b = 1101
二进制 b >>> 2 = 11
十进制 b >>> 2 = 3

##4. 常用的使用场景及效率对比

前面介绍了3种最常用的使用场景，这里再介绍几种用法和他们的效率对比

  • 奇数偶数判断 a & 1 = 1 （奇数） a & 1 = 0 (偶数) 位运算效率低
int a = 100;
boolean temp;
long start,end;
start = System.currentTimeMillis();
for(long i =0;i<100000000L;i++){
    temp = (a & 1) == 1;
    temp = (a & 1) == 0;
}
end = System.currentTimeMillis();
System.out.println("位运算 :"+(end-start));
start = System.currentTimeMillis();
for(long i =0;i<100000000L;i++){
    temp = a % 1 == 1;
    temp = a % 1 == 0;
}
end = System.currentTimeMillis();
System.out.println("模运算 :"+(end-start));
//输出
位运算 :38
模运算 :33
  • Swap 不用临时变量两数互换 a ^= b; b ^= a; a ^= b; 位运算效率低
int a = 100,b = 200,temp;
long start,end;
start = System.currentTimeMillis();
for(long i =0;i<100000000L;i++){
    a = a^b;
    b = b^a;
    a = a^b;
}
end = System.currentTimeMillis();
System.out.println("位运算 :"+(end-start));
start = System.currentTimeMillis();
for(long i =0;i<100000000L;i++){
    temp = a;
    a = b;
    b =temp;
}
end = System.currentTimeMillis();
System.out.println("临时变量 :"+(end-start));
//输出
位运算 :99
临时变量 :54
  • 取反 (~a + 1) 两者效率接近
int a = 100;
int temp;
long start, end;
start = System.currentTimeMillis();
for (long i = 0; i < 1000000000L; i++) {
    temp = ~a + 1;
}
end = System.currentTimeMillis();
System.out.println("位运算 :" + (end - start));
start = System.currentTimeMillis();
for (long i = 0; i < 1000000000L; i++) {
    temp = -a;
}
end = System.currentTimeMillis();
System.out.println("直接取反 :" + (end - start));
//输出
位运算 :325
直接取反 :331
  • 取绝对值 (a^(a»31))-(a»31) 两者效率接近
int a = 100;
int temp;
long start, end;
start = System.currentTimeMillis();
for (long i = 0; i < 1000000000L; i++) {
    temp =  (a^(a>>31))-(a>>31) ;
}
end = System.currentTimeMillis();
System.out.println("位运算 :" + (end - start));
start = System.currentTimeMillis();
for (long i = 0; i < 1000000000L; i++) {
    temp = Math.abs(a);
}
end = System.currentTimeMillis();
System.out.println("Math函数 :" + (end - start));
//输出
位运算 :350
Math函数 :331

后面我们就不做代码示例了，各位有兴趣可以自己尝试下。

  • 整数的平均值 (x&y)+((x^y)»1; 这样不会导致INT_MAXVALUE 溢出 两者效率接近
  • 快速乘法 a * (2^n) 等价于 a « n 位运算略快
  • 快速除法 a / (2^n) 等价于 a » n 位运算略快

总结：

经过大量实验，在 Java 中其实位运算主要还是用在对位操作有要求的场景，在大多数情况下，位和数学运算的效率差不多。所以不需要为了装B而用位运算，这样会导致效率没怎么提升，代码阅读性还降低了。在HashMap源码中对Size扩容有这样一段代码，意思大概是每次扩容到距离 cap 最近的下一个 2^n^ 的值。这段效率是普通数学运算的4倍左右。有兴趣的朋友可以试试!

//HashMap源码,扩容方法
static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

二进制

位运算

关于Java中位运算符的理解

java基本数据类型

路过图床

CATALOG
    FEATURED TAGS
    Java JVM 数据结构 算法 Redis 设计模式 Maven Eureka Spring Cloud 微服务 Netflix
    FRIENDS