首页 > 代码库 > 找出不小于给定数字的最小2的幂值

找出不小于给定数字的最小2的幂值

   

看JDK源码,在HashMap类中发现了一个可以很好解决这个问题的方法。

问题描述:

假设给定 14,输出16;给定16,也输出16;给定17,输出32。输出满足给定数字的最小2的幂值

算法:

  1. int tableSizeFor(int cap) {
  2. int n = cap - 1;
  3. n |= n >>> 1; # 001XXXXX --> 0011XXXX
  4. n |= n >>> 2; # 0011XXXX --> 001111XX
  5. n |= n >>> 4; # 001111XX --> 00111111
  6. n |= n >>> 8; # 00111111 --> 00111111 不再变化
  7. n |= n >>> 16;# 00111111 --> 00111111 不再变化,因为最大就是32位,所以到此结束
  8. return n + 1;
  9. }

解析:

思路是填充1,比如 000110101,此时想要把高位第四位的1右边的所有值都填充为1,然后+1就得到满足目标的值。
但是需要注意如果本来这个数字就是2的幂,结果就会是原来数字的2倍,所以开始前先cap-1。

找出不小于给定数字的最小2的幂值