[向 JDK 学设计] 系列第 3 篇，本系列会涉及一小部分源码，不需要刻意记住，重要的是学习源码背后的设计思想，然后运用到实际开发中

大家好，我是尘光，持续学习，持续创作中

前言

Java 开发离不开 JDK，JDK 本身经过了精心的设计，具有出色的性能，并且支持向下兼容。可以说 JDK 是 Java 软件工程师的第一手学习资料，其中的设计思想值得学习和借鉴

对计算机而言，程序中的所有数值在内存中都是以二进制的形式储存的。位运算就是直接对整数在内存中的二进制位进行操作。位运算通常有更高的执行效率，熟练掌握位运算，也是一个面试加分项

位运算介绍

运算规则

使用场景

虽然「位运算」比「四则运算」执行效率更高，但是在开发过程中，不能滥用，需要分析使用场景。因为大部分开发语言都有强大的编译器，在编译过程中，会尽可能将代码优化为更高效的实现，比如将乘除法优化为位运算实现

位运算的实现通常更难理解，因此维护成本较高。因此，在使用位运算时，应确保代码的可读性和可维护性，并进行充分测试

以下是一些推荐使用位运算的场景

• 性能优化

  在处理大数据量或需要高性能的场景中，使用位运算可以显著提高程序性能

• 数据处理

  在处理二进制数据、位掩码、硬件交互或网络通信等场景中，位运算非常有用。例如，可以使用位运算来设置、清除或切换二进制标志，或者对数据进行加密和解密

• 空间优化

  在处理大数据量时，使用位运算可以有效地压缩数据，节省存储空间。例如，可以使用「位字段」将多个布尔值或枚举值存储在一个整数中

• 算法实现

  在某些算法中，位运算可以提供简洁高效的解决方案。如在图形算法、加密算法或哈希函数中，经常使用位运算

JDK 中的位运算

接下来探索一下 JDK 底层实现中位运算的使用场景

位掩码操作

位运算最经典的应用场景是「位掩码」操作

在计算机科学中，位掩码（Bit Mask）用于选择性地操作特定位。一般而言，其中只有一位或少数几位是 1，其余位数都是 0

基础操作

位掩码的 3 种基础操作如下

• 设置位

  使用 | 操作符，让位掩码和目标数执行「或」运算，可以设置目标数的特定位

  int target = 0b00000000_01100000;
  int mask = 0b00000001_00000100;
  target |= mask;
  String binaryTarget = Integer.toBinaryString(target);
  System.out.println(binaryTarget);
  // 101100100
  

  设置位的过程示意图如下。假设目标数为 16 位二进制数，有一块位掩码板，有相同的 16 个槽位，每个槽位可以用关闭或者开启。目前右起第 3 和 第 9 个槽位开启，将目标数放置在位掩码板下，然后在位掩码板上倒上数值为 1 的二进制位，最终目标数的第 3 和第 9 位被设置为 1，其他位不变

• 清除位

  使用 & 操作符，让取非后的位掩码和目标数执行「与」运算，可以清除目标数的特定位

  int target = 0b00000001_11000111;
  int mask = 0b00000001_00000100;
  target &= ~mask;
  String binaryTarget = Integer.toBinaryString(target);
  System.out.println(binaryTarget);
  // 11000011
  

  清除位的过程示意图如下。假设目标数为 16 位二进制数，有一块位掩码板，有相同的 16 个槽位，每个槽位可以用关闭或者开启。此时位掩码板的运算规则变为 target & ~mask，~mask 的特定位变为 0，因此可以将目标数的特定位设置为 0，也就是清除了特定位原来的数值，不管之前是 0 还是 1

• 检查位

  使用 & 操作符，让位掩码和目标数执行「与」运算，然后判断结果是否为 0，即可检查目标数的特定位是否已设置。如果位运算结果不为 0，表示相应位已设置

  int target = 0b00000000_01100100;
  int mask = 0b00000000_00000100;
  boolean isTargetBitSet = (target & mask) != 0;
  System.out.println(isTargetBitSet);
  // true
  

  注意：此时的位掩码只有 1 位，如下图所示

示例

FilePermission

java.io.FilePermission 是 Java 安全体系的一部分，表示文件系统中文件的访问权限，用于控制对文件和目录的访问

FilePermission 中定义的权限如下，使用了二进制数的不同标志位

private static final int EXECUTE  = 0x1;
private static final int WRITE    = 0x2;
private static final int READ     = 0x4;
private static final int DELETE   = 0x8;
private static final int READLINK = 0x10;

文件可以有多个权限，比如同时有「读 / 写 / 执行」权限，因此 FilePermission 中有一个 actions 属性，用于保存权限组合，此外还有一个重要属性 mask，用于辅助位运算

FilePermission 的一个构造方法如下，其中有很多位掩码操作

public final class FilePermission extends Permission implements Serializable {
    public FilePermission(String path, String actions) {
        super(path);
        init(getMask(actions));
    }
    
    // ...
}

对于传入的 actions，需要先转换为 mask，转换逻辑在 getMask(actions) 方法中，部分核心逻辑如下，其中使用了「位掩码」的设置位操作

private static int getMask(String actions) {
    int mask = NONE;

    // ...

    char[] a = actions.toCharArray();

    // ...

    while (i != -1) {
        char c;
        // ...

        // check for the known strings
        int matchlen;

        if (i >= 3 && (a[i-3] == 'r' || a[i-3] == 'R') 
                   && (a[i-2] == 'e' || a[i-2] == 'E') 
                   && (a[i-1] == 'a' || a[i-1] == 'A') 
                   && (a[i] == 'd' || a[i] == 'D'))
        {
            matchlen = 4;
            // 设置位
            mask |= READ;

        } else if (i >= 4 && (a[i-4] == 'w' || a[i-4] == 'W') 
        		  && (a[i-3] == 'r' || a[i-3] == 'R') 
        		  && (a[i-2] == 'i' || a[i-2] == 'I') 
        		  && (a[i-1] == 't' || a[i-1] == 'T') 
        		  && (a[i] == 'e' || a[i] == 'E'))
        {
            matchlen = 5;
            // 设置位
            mask |= WRITE;

        } else if (i >= 6 && (a[i-6] == 'e' || a[i-6] == 'E') 
        		  && (a[i-5] == 'x' || a[i-5] == 'X') 
        		  && (a[i-4] == 'e' || a[i-4] == 'E') 
        		  && (a[i-3] == 'c' || a[i-3] == 'C') 
        		  && (a[i-2] == 'u' || a[i-2] == 'U') 
        		  && (a[i-1] == 't' || a[i-1] == 'T') 
        		  && (a[i] == 'e' || a[i] == 'E'))
        {
            matchlen = 7;
            // 设置位
            mask |= EXECUTE;

        }

        // ...
    }

    return mask;
}

然后基于 mask 初始化

private void init(int mask) {
    // 检查位
    if ((mask & ALL) != mask)
    	throw new IllegalArgumentException("invalid actions mask");
	
    // ...

    if (FilePermCompat.nb) {
        // ...

        this.mask = mask;

        // ...
    } else {
        // ...

        this.mask = mask;

        // ...
    }
}

Spliterator

0b1

0b100

0b10000

0b1000000

0b100000000

0b10000000000

0b1000000000000

0b100000000000000

很明显，这 8 个常量值的标志位分别错开了 2 位，便于进行位运算。Spliterator 接口中有两个重要方法

public interface Spliterator<T> {

    // ...

    int characteristics();

    default boolean hasCharacteristics(int characteristics) {
        // 检查位
        return (characteristics() & characteristics) == characteristics;
    }

    // ...
}

hasCharacteristics() 方法中调用了 characteristics() 方法，获取当前 Spliterator 的特征值目标数，然后检查特定位是否已设置

以 ArrayList.ArrayListSpliterator 为例，characteristics() 方法如下

final class ArrayListSpliterator implements Spliterator<E> {
    // ...

    public int characteristics() {
        // 设置位，最终结果为 0b100000001010000
        return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;
    }

    // ...
}

熟练掌握位掩码操作是编程基本功，后面继续探索 Stream 并行流时才能得心应手

哈希算法

为了将 Key 均匀映射到不同的位置上，访问单个 key 时平均时间复杂度为 O(1)，加快访问速度，一般会使用哈希函数，目前已知的哈希算法很多，比如 MD5, SHA1

HashMap

HashMap 的底层数据结构是「数组 + 链表」，在执行 put() 或者 get() 操作时，对于传入的 key，需要先确定应该映射到数组的哪一个元素里，也就是哪一个哈希桶，这里使用 hash() 生成哈希值，方法如下

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

这里就使用了位运算来生成哈希值，即 h ^ (h >>> 16)

在 Java 中，int 占 4 个字节，转换为二进制就是 32 位，这个操作相当于将高 16 位和低 16 位进行按位异或运算，如下图所示

JDK 实现 HashMap 使用的哈希算法不是最优的，但却是权衡利弊后的结果，因为这种方式实现很简单，并且 key 较为均匀，出现哈希冲突时，转换为链表或者红黑树，可以实现近似 O(1) 的时间复杂度

乘除法运算

可以通过移位操作，实现与 2 有关的乘除法运算，JDK 中有大量的示例，尤其是整型数据类型的包装类

Integer

判断正负号

使用 signum(i) 方法判断一个 Integer 的符号

public static int signum(int i) {
    // 1. 如果 i = 0，结果为 0
    // 2. 如果 i > 0，i >> 31 为 0，-i >>> 31 为 1，最终结果为 1
    // 3. 如果 i < 0，i >> 31 为 -1，-i >>> 31 为 0，最终结果为 -1
    return (i >> 31) | (-i >>> 31);
}

0 与任意数 n 执行「或」运算，结果都为 n

前导 0 个数

public static int numberOfLeadingZeros(int i) {
    if (i <= 0)
        return i == 0 ? 32 : 0;
    int n = 31;
    if (i >= 1 << 16) { n -= 16; i >>>= 16; }
    if (i >= 1 <<  8) { n -=  8; i >>>=  8; }
    if (i >= 1 <<  4) { n -=  4; i >>>=  4; }
    if (i >= 1 <<  2) { n -=  2; i >>>=  2; }
    return n - (i >>> 1);
}

虽然只有 32 位待比较，也采用了类似二分查找的思想，追求极致的性能

HashMap

HashMap 中部分常量初始化时，使用了左移运算实现乘法

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {

    // ...

    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    static final int MAXIMUM_CAPACITY = 1 << 30;

    // ...
}

HashMap 中数组的长度必须是 2n2^n2n，在初始化时，如果传入了不规范的初始容量，会被处理为不小于传入值的最小 2n2^n2n

static final int tableSizeFor(int cap) {
    int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

假设此时 cap = 29, numberOfLeadingZeros(cap - 1) 为 27。注意到 -1 的二进制位全部为 1，因此无符号右移一定位数后，右边部分仍然全为 1，加 1 后即为 2n2^n2n，如下图所示，最终返回 32

Collections

java.util.Collections 中有二分查找的通用实现，List 的元素个数小于 5000 时，会通过下标进行二分查找

private static <T>
int indexedBinarySearch(List<? extends Comparable<? super T>> list, T key) {
    int low = 0;
    int high = list.size()-1;

    while (low <= high) {
        // 使用无符号后移 1 位实现「除 2」运算
        int mid = (low + high) >>> 1;
        Comparable<? super T> midVal = list.get(mid);
        int cmp = midVal.compareTo(key);

        if (cmp < 0)
            low = mid + 1;
        else if (cmp > 0)
            high = mid - 1;
        else
            return mid;
    }
    return -(low + 1);
}

总结

本文的示例只是 JDK 源码中极小的一部分，但万变不离其宗，位运算的原理还是很简单的，多看多练习，就会熟能生巧。在开发过程中，遇到合适的场景，也可以考虑使用位运算

参考文档

算法-超全的位运算介绍与总结

深入理解完美哈希