判断一个数是否是2的N次幂

第一种方法

public class TestJudge2NthPower {

  public static void main(String[] args) {
    System.out.println(isPowerOf2(-1));//false
    System.out.println(isPowerOf2(0));//false
    System.out.println(isPowerOf2(1));//true
    System.out.println(isPowerOf2(2));//true
    System.out.println(isPowerOf2(3));//false
    System.out.println(isPowerOf2(10));//false
    System.out.println(isPowerOf2(16));//true
    System.out.println(isPowerOf2(1 << 30));//true
  }

  //判断目标值是否为2的N次幂
  private static boolean isPowerOf2(int target) {
    if (target <= 0) {
      return false;
    }
    if (target == 1) {
      return true;
    }
    //相当于target%2==0  对2取余,没有余数
    while (target > 2 && (target & 1) != 1) {
      //相当于除以2
      target >>= 1;
    }
    return target == 2;
  }

}

暴力解法

第二种方法

public class TestJudge2NthPower2 {

  public static void main(String[] args) {
    System.out.println(isPowerOf2(-1));//false
    System.out.println(isPowerOf2(0));//false
    System.out.println(isPowerOf2(1));//true
    System.out.println(isPowerOf2(2));//true
    System.out.println(isPowerOf2(3));//false
    System.out.println(isPowerOf2(10));//false
    System.out.println(isPowerOf2(16));//true
    System.out.println(isPowerOf2(1 << 30));//true
  }

  //判断目标值是否为2的N次幂
  private static boolean isPowerOf2(int target) {
    if (target <= 0) {
      return false;
    }
    return (target & (target - 1)) == 0;
  }

}

示例分析

以16为例,二进制表示为

00000000 00000000 00000000 00010000

16减1为15的二进制表示为

00000000 00000000 00000000 00001111

两者按位与

00000000 00000000 00000000 00000000

十进制表示为0,说明是2的N次幂。

扩展-判断一个数是否是n的N次幂

public class TestJudgeNNthPower {

  public static void main(String[] args) {
    System.out.println(isPowerOfN(-1, 3));//false
    System.out.println(isPowerOfN(0, 3));//false
    System.out.println(isPowerOfN(1, 3));//true
    System.out.println(isPowerOfN(2, 3));//false
    System.out.println(isPowerOfN(3, 3));//true
    System.out.println(isPowerOfN(10, 3));//false
    System.out.println(isPowerOfN(27, 3));//true
    System.out.println(isPowerOfN((int) Math.pow(4, 10), 4));//true
    System.out.println(isPowerOfN(1024, 8));//false
  }

  //判断目标值是否为n的N次幂
  private static boolean isPowerOfN(int target, int n) {
    if (target <= 0) {
      return false;
    }
    if (target == 1) {
      return true;
    }
    while (target > n && (target % n) == 0) {
      target /= n;
    }
    return target == n;
  }

}

参考

[算法]快速判断一个数是否是2的幂次方

上一篇:Windbg内存泄漏问题的定位


下一篇:原码、反码 、补码 / &(与运算)、|(或运算)、^(异或运算)