奇怪的算法（常更）

声明：本文用于收集一些奇怪精妙的算法，不定期更新

一、寻找下一个比当前数值大的2次幂的值

• 来源：(Java)类：ForkJoinPool
• 来源代码引用

//n必不为负数，且不大于32767
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;  
n = n + 1;

• 作用
  找出比n大的下一个2次幂的数的值（0<=n<=2147483647）
• 分析
  • 当n |= n >>> 1后，n中（除了两端）任意一个位1其旁边必定至少还有1个位1
  • 当n |= n >>> 2后，n中（除了两端）任意一个位1其旁边必定至少还有3个连续的位1
  • 当n |= n >>> 4后，n中（除了两端）任意一个位1其旁边必定至少还有7个连续的位1
  • 当n |= n >>> 8后，n中（除了两端）任意一个位1其旁边必定至少还有15个连续的位1
    ...
• 使用方法
  • 重要的是控制n的范围，n的范围由最后一次右移位数的倍数决定，比如该例子n的范围最大就是2^16*2-1

参考文档：