每日一面 - 求与数字最接近的 2 的 N 次方

2021-04-09 17:22:11 浏览数 (1)

对于 2 的 N 次方取余,相当于对 2 的 N 次方减一取与运算,这对于高并发分片计算的时候,很有用。为了对用户友好,我们让用户设置分片数量的时候可能不限制必须是 2 的 N 次方,但是内部我们设置分片的时候,将其设置为最近用户输入数字的 2 的 N 次方的值即可。那么如何计算呢?

抽象为比较直观的理解就是,找一个数字最左边的 1 的左边一个 1 (大于 N 的最小的 2 的 N 次方),或者是最左边的1(小于N的最大的2的N次方),前提是这个数字本身不是2的n次方。

那么,如何找呢?一种思路是,将这个数字最高位 1 之后的所有位都填上 1,最后加一,就是大于N的最小的 2 的 N 次方。右移一位,就是小于N的最大的 2 的N次方。

如何填补呢?可以考虑按位或计算,我们知道除了 0 或 0=0 以外,其他的都是 1. 我们现在有了最左面的 1,右移一位,与原来按位或,就至少有了两位是 1,再右移两位并按位或,则至少有四位为 1。。。以此类推:

用代码表示是:

代码语言:javascript复制
n |= n >>> 1; 
n |= n >>> 2; 
n |= n >>> 4; 
n |= n >>> 8; 
n |= n >>> 16;
n  = 1;  //大于N的最小的2的N次方
n = n >>> 1; //小于N的最大的2的N次方

如果有兴趣,可以看一下 Java 的 ForkJoinPool 类的构造器,其中的 WorkQueue 大小,就是通过这样的转换得来的。

0 人点赞