6.7 位计算

Java位运算非常高效，可以使用位运算代替部分算数运算以提高性能，比如，最常用的判断奇数

int  a = 111;
System.out.print((a & 1)==1);

乘以2或者除以2，也可以使用位运算

int  a = 111;//右移1位，相当于除以2
System.out.println(a1);//左移1位，相当于乘以2
System.out.println(a<<1);

在JAVA8的Integer里，也使用了位运算来实现int转字符串（toString)。

//r=i-q*10 优化为如下
r = i - ((q << 3) + (q << 1));//q=i/10，优化为如下
q = (i * 52429)>>>(16+3);

这里(i * 52429) >>> (16+3) 相当于i*0.1000000003，因此对于i较小的数据，可以认为俩着是相等的。

对比直接使用i/10 和 (i * 52429) >>> (16+3)，性能如下

Benchmark                   Mode  Samples  Score  Score error  Units
c.i.c.c.BitTest2.bit        avgt        5  0.669        0.031  ns/op
c.i.c.c.BitTest2.general    avgt        5  1.251        0.560  ns/op

在计算机里，使用除法是相对耗时的操作，所以在Java的Integer里，巧妙使用位移代替了除法。另外一个例子是在HashMap源码里，根据hash值确定对象应该放到桶的位置

假设桶的的定义是Node<K,V>[] tab ,其长度为n = tab.length, 则可以使用取余来确定位置，比如

int hash = hash(key);
Node<K,V first = tab0[hash%n]

但在源码里，使用了位移操作确定位置

Node<K,V first = tab[(n - 1) & (hash =  hash(key) )])

因为HashMap中的容量都是2的幂次,这样的话2的幂-1都是11111结尾的(16->10000,15->01111)，当长度一定是2^n时,tab[i = (2^n - 1) & hash] == tab [i=(hash%2^n)]

以桶长度为2^4，Hash值为99(二进制是01100011)来说，99/16=6，99%16=3.可以使用位移方式实现.即01100011右移4位，剩下的为0110，是结果6，移出的011即是余数3。因为16-1的二进制是00001111，Java通过直接（16-1)&99,来保留移出的位数，从而得到高效算法

关于位运算的更多知识，可以参考 Henry S.Warren,Jr.编著的《算法心得：高效算法的奥秘》

在业务系统中，也通常通过`位``来提系统高性能，比如电商中，一个订单对象，有多个属性，可能只需要一个4字节的Int类型，就能存放。这样的性能好处是

• 提高网络传输效率，因为需要传输的内容更少了
• 如果这个对象需要序列化后存储到Redis或者数据库，也能节省存储空间

下面代码片段显示了一个订单对象使用位来存储其多个属性

public class OrderRequest {
    /**
    * 0位表示是否测试订单，1-4位节表示用户状态，5-8位表示订单状态
    */
    int s;
    
    public boolean isTest(){
        //取出第1位的值
        return (status&0b1)==1;
    }
    
    public int getUserStatus(){
        // 右移1，取出1-4位的值
        return (status>>1&0b1111);
    }
    
    public int getOrderStatus(){
        //右移5，取出5-8位的值
        return (status>>5&0b1111);
    }
}