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

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

2024-09-14 12:35:35   214人阅读

   
看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的幂值


联系
我们