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

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

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

image

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

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

image

用代码表示是：

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