• 103768

    文章

  • 803

    评论

  • 12

    友链

  • 最近新加了换肤功能,大家多来逛逛吧~~~~
  • 喜欢这个网站的朋友可以加一下QQ群,我们一起交流技术。

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

撸了今年阿里、腾讯和美团的面试,我有一个重要发现.......>>

比如: 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,那么第一行就不需要了。


695856371Web网页设计师②群 | 喜欢本站的朋友可以收藏本站,或者加入我们大家一起来交流技术!

0条评论

Loading...


自定义皮肤 主体内容背景
打开支付宝扫码付款购买视频教程
遇到问题联系客服QQ:419400980
注册梁钟霖个人博客