求大于等于n的最小的2的幂m

  • Z时代
  • 2024-01-10
  • 分类：综合

编程

比如：

n = 7，m=8；n = 12， m = 16；n = 24, m = 64

这个算法在ConcurrentHashMap中用于计算sizeCtl：sizeCtl=大于（1.5倍initialCapacity+1）的最小的2的幂。

private static final int tableSizeFor(int c) {
	int n = c - 1; // 第1行
	n |= n >>> 1; // 第2行
	n |= n >>> 2; // 第3行
	n |= n >>> 4; // 第4行
	n |= n >>> 8; // 第5行
	n |= n >>> 16; // 第6行
	return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

比如n = 9，进行每一步运算。二进制补码是：0000 1001(前面3字节都是0，忽略)。

  • 第一行结果：0000 1000 (减去1的原因稍后的例子说明)

  • 第二行结果：0000 1100 最高位的1，将后面也变为1。因此现在最高位两个1

  • 第三行结果：0000 1111 接下来直接右移两位然后相或，把后面两位也变为1：1111。这里不是右移1位，这是指数爆炸的结果(一个传染俩)

  • 第四行、第五行结果维持不变。第六行：0000 1111 + 1 = 0001 0000 = 16。

其实，求大于n的最小的2的幂m这个问题就是把最高位的1后面的都变为1，然后 + 1得到结果。

那为什么右移是：1，2，4，8，16

比喻一下：最高位1是回不断分裂的细胞，第一次分类

为什么右移步骤是：1,2,4,8,16？

第2行到第6行，加起来一共进行无符号位置了：1 +2 +4 + 8 + 16 = 2^n - 1 = 32 - 1 = 31。这不是等比数列求和吗(跑题了)

为什么是31。因为要让最高位的1一直右移，并且把每一位都变为1。为什么不是直接进行31次右移？

就好比细胞分裂，最高位1是一个不断分裂的细胞，第一次1变2，然后两个细胞一起分裂；2变4(右移两位)；之后4个继续分裂为8(右移4位)，这就是为什么不是每次右移1位。(假设每次进行一次右移，那么相当于每次只有一个细胞在分裂)

为什么第6行加1

因为要求出大于>=n的2的幂。加1正好可以求出。

为什么第一行减去1

因为n可能已经是2的幂。比如1000 = 8的情况，如果不减去1，结果：1111 + 1 = 10000 = 16。但是其实正确答案是8，就是n自身。因此减去1，变为:0111 = 7进行计算，得出8的结果。

如果问题是：求大于n的最小的2的幂m，那么第一行就不需要了。

以上是 求大于等于n的最小的2的幂m 的全部内容， 来源链接： utcz.com/z/514891.html

回到顶部