Java位运算—高级用法与深入解读（上）

一、开篇浅谈

开篇我们先来小谈一下：如果你是一名高级工程师或者是架构师，你在读源码的过程中，一定见过如下的代码，可以发现源码里运用了很多位运算来提高性能。

ArrayList.class 源码节选

ArrayList源码解读—Java8版本

    private void grow(int minCapacity) {
        ...
        //ArrayList扩容1.5倍关键代码
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        ...
    }

LinkedList.class 源码节选

LinkedList源码解读—Java8版本

  //通过判断索引靠链表的前面还是后面，提高效率
    Node<E> node(int index) {
        // assert isElementIndex(index);
        if (index < (size >> 1)) {
            ...
        } else {
            ...
        }
    }

HashMap.class 源码节选

HashMap源码解读-Java8版本

   // 获取一个既大于 cap 又最接近 cap 的 2 的整数次幂数值
   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位运算的知识之前，我们先来了解几个基础的概念，机器数，真值，原码，反码，补码。

1.机器数

我们知道无论是代码还是数值，在计算机中最后都转换成以二进制的形式存在的，而一个数值在计算机中的二进制表示形式，就是这个数的机器数。机器数是有符号位的，在计算机中用一个二进制数的最高位存放符号，正数为0，负数为1，如下实例（按原码表示）：

十进制的＋5，计算机字长为8位，其二进制就是00000101

十进制的－5，计算机字长为8位，其二进制就是10000101(这里用的是原码)

其中00000101和10000101就是机器数

2.真值

由于机器数的第一位是符号位，所以其形式值就不等于其真值的数值，也就是说10000101表示的是－5而不是133（10000101的十进制是131，前提是不算最高位为符号位），因此－5才是机器数的真值。

3.原码

原码是一种计算机中对数字的二进制定点表示方法。原码表示法在数值前面增加了一位符号位（即最高位为符号位）：正数该位为0，负数该位为1，其余位表示数值的大小。

［＋5］=[00000101]（原码）

［ - 5］=[10000101]（原码）

因为第一位是符号位，因此8位二进制的取值范围就是［1111 1111，0111 1111］也就是［-127,127］

4.反码

反码是数值存储的一种，但是由于补码更能有效表现数字在计算机中的形式，所以多数计算机一般都不采用反码表示数，反码的表示方法如下:

正数的反码是其本身

负数的反码是在其原码的基础上, 符号位不变，其余各个位取反.

［＋5］=[00000101]（原码）＝ ［00000101］（反码）

［ - 5］=[10000101]（原码）＝ ［11111010］（反码）

5.补码

在计算机系统中，数值一律用补码来表示和存储。原因在于，使用补码，可以将符号位和数值域统一处理；同时，加法和减法也可以统一处理。补码的表示方法是:

正数的补码就是其本身

负数的补码是在其原码的基础上, 符号位不变, 其余各位取反, 最后+1. (即在反码的基础上+1)

［＋5］=[00000101]（原码）＝ ［00000101］（反码）＝［00000101］（补码）

［ - 5］=[10000101]（原码）＝ ［11111010］（反码）＝［11111011］（补码）

6.补充

计算机中的符号数有三种表示方法，即原码、反码和补码。三种表示方法均有符号位和数值位两部分，符号位都是用0表示“正”，用1表示“负”，而数值位，三种表示方法各不相同。而在计算机系统中，数值一律用补码来表示和存储。

三、Java位运算

位移操作：(只针对 int类型的数据有效，java中，一个int的长度始终是32位，也就是4个字节,它操作的都是该整数的二进制数).也可作用于以下类型，即 byte，short，char，long(它们都是整数形式)。当为这四种类型时，JVM先把它们转换成int型再进行操作。

7.左移（<<）

m<<n的含义:把整数m表示的二进制数左移n位,高位移出n位都舍弃，低位补0. (此时将会出现正数变成负数的可能)，如下实例：

5<<2 ：把十进制的数值5左移两位,按如下步骤计算，

把5转位16位的二进制机器数：00000000 00000000 00000000 00000101

按左移原理，将二进制数左移两位：00000000 00000000 00000000 00010100

左移后结果为20

5<<29:把十进制的数值5左移29位,按如下步骤计算，

把5转位16位的二进制机器数：00000000 00000000 00000000 00000101

按左移原理，将二进制数左移29位：10100000 00000000 00000000 00000000

左移后高位是1，结果显然是负数

小结：m<<n即在数字没有溢出的前提下，对于正数和负数，左移n位都相当于m乘以2的n次方.

8.右移（>>）

m>>n的含义:把整数m表示的二进制数右移n位,m为正数，高位全部补0；m为负数，高位全部补1,实例如下：

5>>2 ：把十进制的数值5右移两位,按如下步骤计算，

把5转位16位的二进制机器数：00000000 00000000 00000000 00000101

按右移原理，将二进制数左移两位：00000000 00000000 00000000 00000001

右移后结果为1

-5>>2：把十进制的数值-5右移两位,按如下步骤计算，

把-5转位16位的二进制机器数：11111111 11111111 11111111 11111011

按右移原理，将二进制数右移两位：11111111 11111111 11111111 11111110

右移后结果为-2

小结： m>>n即相当于m除以2的n次方，得到的为整数时，即为结果。如果结果为小数，此时会出现两种情况：

如果m为正数，得到的商会无条件 的舍弃小数位；

如果m为负数，舍弃小数部分，然后把整数部分加+1得到位移后的值。