位运算的优化与应用

一.简介

随着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对象头：
| Mark Word (32 bits) | State |
|:----|:----|
| identity_hashcode:25 | age:4 | biased_lock:1 | lock:2 | Normal |
| thread:23 | epoch:2 | age:4 | biased_lock:1 | lock:2 | Biased |
| ptr_to_lock_record:30 | lock:2 | Lightweight Locked |
| ptr_to_heavyweight_monitor:30 | lock:2 | Heavyweight Locked |
| | lock:2 | Marked for GC |

判断有多少个状态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和异或为了防止，后续计算节点位置，出现冲突，打乱顺序。

三.总结

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