求与一个数最接近的2的N次幂

第一种方法

public class TestClosest2NthPower {

  public static void main(String[] args) {
    System.out.println(test(-1));//1
    System.out.println(test(1));//1
    System.out.println(test(-1));//1
    System.out.println(test(10));//16
    System.out.println(test(16));//16
    System.out.println(test(Integer.MAX_VALUE));//2^30
  }

  private static int test(int target) {
    //int类型最大值为(2^31)-1,所以目标能取到的最大值为2^30
    int MAXIMUM = 1 << 30;
    if (target >= MAXIMUM) {
      return MAXIMUM;
    }
    int result = 1;
    while (result < target) {
      result *= 2;
    }
    return result;
  }

}

相当于在2的0次幂和2的30次幂中的31个数中找一个最接近的数。

[2^0,2^1 ... 2^30]

第二种方法

public class TestClosest2NthPower2 {

  public static void main(String[] args) {
    System.out.println(test(-1));//1
    System.out.println(test(1));//1
    System.out.println(test(-1));//1
    System.out.println(test(10));//16
    System.out.println(test(16));//16
    System.out.println(test(Integer.MAX_VALUE));//2^30
  }

  private static int test(int target) {
    //int类型最大值为(2^31)-1,所以目标能取到的最大值为2^30
    int MAXIMUM = 1 << 30;
    if (target >= MAXIMUM) {
      return MAXIMUM;
    }
    int temp = target - 1;
    temp |= temp >> 1;
    temp |= temp >> 2;
    temp |= temp >> 4;
    temp |= temp >> 8;
    temp |= temp >> 16;
    return (temp < 0) ? 1 : temp + 1;
  }

}

示例分析

以129为例(可以更明显看出效果),先减1为128,二进制表示为

00000000 00000000 00000000 10000000

右移1位

00000000 00000000 00000000 01000000

两者按位或

00000000 00000000 00000000 11000000

保证了前两位都为1,以此类推可以保证第一个1及之后的所有位都为1

00000000 00000000 00000000 11111111

再加一

00000000 00000000 00000001 00000000

十进制表示为256。

核心原理

核心原理就是将一个数减1的二进制表示的第一个1及之后的所有位都置为1,然后加1,这样得到的数就是2的N次幂,相当于最高位的1向左进1位,之后的所有位都置为0。

为什么要先减1

为了兼容一个数已经是2的N次幂的情况。以2的4次幂16为例,减1为15,最后操作结果还是16,如果这个数不是2的N次幂,如15,其实减不减1都可以得到正确结果16。

使用场景

ForkJoinPool的构造器中初始化workQueues的容量时就使用到了这种方法。

第三种方法

public class TestClosest2NthPower3 {

  public static void main(String[] args) {
    System.out.println(test(-1));//1
    System.out.println(test(1));//1
    System.out.println(test(-1));//1
    System.out.println(test(10));//16
    System.out.println(test(16));//16
    System.out.println(test(Integer.MAX_VALUE));//2^30
  }

  private static int test(int target) {
    //int类型最大值(2^31)-1,所以目标能取到的最大值为2^30
    int MAXIMUM = 1 << 30;
    if (target >= MAXIMUM) {
      return MAXIMUM;
    }
    int n = -1 >>> Integer.numberOfLeadingZeros(target - 1);
    return (n < 0) ? 1 : n + 1;
  }

}

示例分析

以129为例(可以更明显看出效果),先减1为128,二进制表示为

00000000 00000000 00000000 10000000

使用Integer的numberOfLeadingZeros()方法求出前导0的个数为24,-1的二进制表示为

11111111 11111111 11111111 11111111

无符号右移24位

00000000 00000000 00000000 11111111

再加一

00000000 00000000 00000001 00000000

十进制表示为256。

核心原理

和上一个方法的原理类似,也是将一个数减1的二进制表示的第一个1及之后的所有位都置为1,然后加1。

使用场景

这种方法参考的就是HashMap中计算容量大小的算法。

参考

求最接近数n的2的次方数

上一篇:java中左移、右移、无符号右移的区别


下一篇:CSS3背景裁切属性——background-clip