对于 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 大小,就是通过这样的转换得来的。