位运算的优化与应用网络李孟的博客-

一.简介

随着JDK的发展以及JIT的不断优化，语法糖越来越丰富了，程序用了太多了看似高级的用法，易读性提高很多，那么效率呢？很多时候计算可以转换位运算，提高性能和节约空间，很多组件都用到了，比如HashMap、BitSet、ProtocolBuf等等，本文验证一些位运算的用法。

二.基础

2.1 位运算符

Java整型数据类型有：byte、char、short、int、long。一个字节占8位。

计算机中二进制最高符号位”0″正好，”1″为负号。计算机中只能存在二进制，所以计算需要用二进制的补码进行计算。

• 正数的原码，补码，反码都是自己本身。
• 负数的原码、补码（反码+1）、反码（原码（除符号位外）每位取反）。

举个例子 int i=-10;

把十进制转换为二进制：

原码：10000000 00000000 00000000 00001010

反码：11111111 11111111 11111111 11110101

补码：11111111 11111111 11111111 11110110

补码的意义：

• 使符号位能与有效值部分一起参与运算，从而简化运算规则。
• 使减法运算转换为加法运算，进一步简化计算机中运算器的线路设计。

位运算符用来对二进制操作，共有七类运算符，如下：

• 左移（ << ） 整体左移，右边空出位补零，左边位舍弃 （-4 << 1 = -8）
• 右移（ >> ） 整体右移，左边空出位补零或补1（负数补1，整数补0），右边位舍弃 （-4 >> 1 = -2）
• 无符号右移（ >>> ）同>>,但不管正数还是负数都左边位都补0 （-4 >>> 1 = 2147483646）
• 与（ & ）每一位进行比较，两位都为1，结果为1，否则为0（-4 & 1 = 0）
• 或（ | ）每一位进行比较，两位有一位是1，结果就是1（-4 | 1 = -3）
• 非（ ~ ） 每一位进行比较，按位取反（符号位也要取反）（~ -4 = 3）
• 异或（ ^ ）每一位进行比较，相同为0，不同为1（^ -4 = -3）

2.2 *与<<

乘法运算，可以换算成位运算实现

a * (2^n) 等价于 a << n

看上去，位运算应该是位运算性能快，那么根据字节码可以查看下，优化是从什么时候开始？是编译器优化，还是从处理器优化，根据下面示例验证下：

public void multi1(){     int i =1;     i = i << 1; } public void multi2(){     int i = 1;     i *=2; } 

编译好之后，用javap -c来查看class文件，字节码：

Compiled from "BitTest.java" public class com.algorithm.base.bitoperation.BitTest {   public com.algorithm.base.bitoperation.BitTest();     Code:        0: aload_0        1: invokespecial #1                  // Method java/lang/Object."<init>":()V        4: return    public void multi1();     Code:        0: iconst_1        1: istore_1        2: iload_1        3: iconst_1        4: ishl        5: istore_1        6: return    public void multi2();     Code:        0: iconst_1        1: istore_1        2: iload_1        3: iconst_2        4: imul        5: istore_1        6: return } 

可以看出左移是ishl，乘法是imul，从字节码上看编译器并没有优化。那么在执行字节码转换成处理器命令是否会优化呢？是会优化的，在底层，乘法其实就是移位，但是并不是简单地左移。

处理器

从效率上看，使用移位指令有更高的效率，因为移位指令占2个机器周期，而乘除法指令占4个机器周期。从硬件上看，移位对硬件更容易实现，所以会用移位，移1位就乘2，这种乘法当然考虑移位了。

示例：

两个64位的数按位与 和 一个64位的数右移32位 哪个操作快些？

移位快，只有一次寻址，逻辑运算和写操作，按位与需要两次寻址，一次逻辑运算和一次写。

2.3 /与>>

除法运算，可以换算成位运算实现

a/(2^n) 等价于 a >> n

java中 << >> >>>都是针对补码来进行的。

2.4 %与&

取模运算，可以换算成位运算实现

a % (2^n) 等价于 a &(2^n-1)

示例：

a=25，n=3

a 二进制

a % 8 = 1

a &(7) = 1

25 二进制 11001

7 二进制 011

进一步可以判断int类型变量a是奇数还是偶数

a & 1 = 0 偶数

a & 1 = 1 奇数

这个是一个很经典的位运算运用，广泛用于各种高性能框架。例如在生成缓存队列槽位的时候，一般生成2的n次方个槽位，因为这样在选择槽位的时候，就可以用取与代替取余；java中的ForkJoinPool的队列长度就是定为2的n次方；netty中的缓存池的叶子节点都是2的n次方，当然这也是因为是平衡二叉查找树算法的实现。

2.5 交换两个数字

a ^= b b ^= a a ^= b 

示例：
a = 11 二进制 111

b = 10 二进制 110

a = a ^ b 001

b = b^ a 111

a = a ^ b 110

2.6 绝对值

绝对值的定义：

正数的绝对值是它本身，负数的绝对值是它相反数，0的绝对值还是0。

任何有理数的绝对值都是非负数，也就是说任何有理数的绝对值都大于0。

int i; int sign = i >> 31 //取符号位 （i+sign）^ sign   

2.7 bit状态位

在一个系统中，用户一般有查询(Select)、新增(Insert)、修改(Update)、删除(Selete)四种权限，四种权限有多种组合方式，也就是有16中不同的权限状态（2的4次方）。每一位代表一个状态是true还是false。

public class NewPermission {  // 是否允许查询，二进制第1位，0表示否，1表示是  public static final int ALLOW_SELECT = 1 << 0; // 0001    // 是否允许新增，二进制第2位，0表示否，1表示是  public static final int ALLOW_INSERT = 1 << 1; // 0010    // 是否允许修改，二进制第3位，0表示否，1表示是  public static final int ALLOW_UPDATE = 1 << 2; // 0100    // 是否允许删除，二进制第4位，0表示否，1表示是  public static final int ALLOW_DELETE = 1 << 3; // 1000    // 存储目前的权限状态  private int flag;    /**   *  重新设置权限   */  public void setPermission(int permission) {   flag = permission;  }    /**   *  添加一项或多项权限   */  public void enable(int permission) {   flag |= permission;  }    /**   *  删除一项或多项权限   */  public void disable(int permission) {   flag &= ~permission;  }    /**   *  是否拥某些权限   */  public boolean isAllow(int permission) {   return (flag & permission) == permission;  }    /**   *  是否禁用了某些权限   */  public boolean isNotAllow(int permission) {   return (flag & permission) == 0;  }    /**   *  是否仅仅拥有某些权限   */  public boolean isOnlyAllow(int permission) {   return flag == permission;  } } 

这样做节省空间，例如Java对象头：

判断有多少个状态true,就是计算这个状态里面有多少位是1。

比较朴素的方法的：先判断n的奇偶性，为奇数计数器加1，然后将n右移1位，重复上面的步骤

int n = Integer.MAX_VALUE; int count = 0; while (n!=0){     if((n&1)==1) count++;     n= n>>1; } 

高效的方法：

• n & (n – 1)可以移除最后一位1 （假设最后一位本来是0， 减一后必为1，0 & 1为 0， 最后一位本来是1，减一后必为0，0 & 1为 0）
• 移除了最后一位1之后，计数加1，如果结果不为零，则用结果继续第一步。

int n = Integer.MAX_VALUE; int count = 0; while(n != 0) {     n &= n -1;     count++; } 

2.8 初始化算法

这个广泛用于各种组件的初始化操作，2^n初始化资源池。

比如HashMap：

/**  * Returns a power of two size for the given target capacity.  * 不考虑最大容量情况下，返回大于输入参数且最近的2的整数次幂的数。  * 比如10，则返回16  */ 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; } 

2.9 hashcode

在Java语言，判断对象相等，需要重写hashcode和equals方法，例如在hashMap中hash算法

 static final int hash(Object key) {         int h;         return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);     } 

使用位移16和异或为了防止，后续计算节点位置，出现冲突，打乱顺序。

三.总结

还有很多应用方式，继续研究，对于工程来说少就是指数级的多。

参考：

https://zhuanlan.zhihu.com/p/101723848

https://blog.csdn.net/ko_tin/article/details/52830535?depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromBaidu-1&utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromBaidu-1

https://blog.csdn.net/zhangyong01245/article/details/103400375

https://blog.csdn.net/tonysong111073/article/details/79480495

https://blog.csdn.net/hhy107107/article/details/82801780?depth_1-utm_source=distribute.pc_relevant.none-task-blog-OPENSEARCH-2&utm_source=distribute.pc_relevant.none-task-blog-OPENSEARCH-2

https://blog.csdn.net/javazejian/article/details/51181320?depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromBaidu-2&utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromBaidu-2

https://blog.csdn.net/Hk_john/article/details/69942784