位运算计算大于等于给定数字a的最小二次幂

(Updated: )
,

背景

二次幂 是指底数为2且指数为整数n的幂, 如2, 4, 8, 16等

大于等于给定数字a的最小二次幂 即输入[5, 8]的数均输出8, 输入[9, 16]的数均输出16

在Java的HashMap中, 为了方便计算hash值、减少hash碰撞, hash的范围都是二次幂, 在初始化map和map扩容时需要根据给定的初始值计算大于等于给定数字a的最小二次幂, 即 HashMap.java 中的 int tableSizeFor(int cap)

Java中int的最大值为2^31-1, 即0x7fffffff, 即01111111 11111111 11111111 11111111

HashMap的capacity最大值为2^30, 即1 << 30, 即0x40000000, 即01000000 00000000 00000000 00000000

Java8中的实现

看二进制的数, 大于给定数字a的最小二次幂即从左到右数第一个值为1的位, 再左一位为1其他为0

5->8 0101->1000

7->8 0111->1000

目标值减1的数, 即从第一个值为1的位开始所有位的值均为1

5->7 0101->0111

7->7 0111->0111

考虑到输入即为二次幂的情况, 先将输入减1, 再计算从第一个值为1的位开始所有位的值均为1, 不需要考虑等于的情况, 最后得到的数再加1

0010 1001->0011 1111 即 41->63, 输出64

如何将一个数最高位1后面的1全部置为1呢? 使用右移+取或, 例如0100右移1位并和自身取或0100 | 0010 = 0110就将最高位的后一位置为了1, 不断重复这个过程

输入的最大值为1 << 30即01000000 00000000 00000000 00000000

减1后为00111111 11111111 11111111 11111111, 不断右移取或后还是自己, 加1后为01000000 00000000 00000000 00000000

假设输入1 << 29 + 1即00100000 00000000 00000000 00000001

右移1位后和自己取或00110000 00000000 00000000 00000000

右移2位后和自己取或00111100 00000000 00000000 00000000

右移4位后和自己取或00111111 11000000 00000000 00000000

右移8位后和自己取或00111111 11111111 11000000 00000000

右移16位后和自己取或00111111 11111111 11111111 11111111

加1后为01000000 00000000 00000000 00000001即1 << 30

1
2
3
4
5
6
7
8
9
10
11
static final int MAXIMUM_CAPACITY = 1 << 30;

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;
}

Java11中的实现

目标同样是将最高位1后面的0计算出前导0的个数, 最后加1

先求出a前导0的数量, 使用比较和移位求出, 然后直接将-1 0xffffffff进行无符号右移

其中numberOfLeadingZeros()方法在OracleJDK中含注解@IntrinsicCandidate, OpenJDK中含注解@HotSpotIntrinsicCandidate, 均表示HotspotJVM会根据当前处理器平台对运算进行优化

1
2
3
4
5
6


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

其中Integer.numberOfLeadingZeros()的实现如下

1
2
3
4
5
6
7
8
9
10
11
12
@IntrinsicCandidate
public static int numberOfLeadingZeros(int i) {
    // HD, Count leading 0's
    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);
}