问题描述

给定一个数n，判断n是否为k的幂，即判断 `n == k``` 是否成立。

  1. 给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。

如果存在一个整数 x 使得 `n == 2``` ，则认为 n 是 2 的幂次方。

  1. 给定一个整数，写一个函数来判断它是否是 3 的幂次方。如果是，返回 true ；否则，返回 false 。

整数 n 是 3 的幂次方需满足：存在整数 x 使得 `n == 3```

  1. 给定一个整数，写一个函数来判断它是否是 4 的幂次方。如果是，返回 true ；否则，返回 false 。

整数 n 是 4 的幂次方需满足：存在整数 x 使得 `n == 4```

解决方法

1. 按照题目给定数的范围求解(整数限制)

  1. 判断是否为最大k的幂的约数
  1. //2的幂
  2. class Solution {
  3.     static final int BIG = 1 << 30;
  5.     public boolean isPowerOfTwo(int n) {
  6.         return n > 0 && BIG % n == 0;
  7.     }
  8. }
  9. //3的幂
  10. class Solution {
  11.     static final int BIG = 1162261467;
  13.     public boolean isPowerOfThree(int n) {
  14.         return n > 0 && BIG % n == 0;
  15.     }
  16. }
  18. //4的幂？


存在一个问题，若k不是素数怎么办？**
答：结合模运算求解

  1. //4的幂
  2. //4不是素数，4 = 2 * 2 = 1 * 4
  3. //结合模运算 4^p % 3 = 1而2^p % 3 = 2
  4. class Solution {
  5.     static final int BIG = 1 << 30;
  7.     public boolean isPowerOfFour(int n) {
  8.         return n > 0 && BIG % n == 0 && BIG  % 3 == 1;
  9.     }
  10. }

2. 循环迭代

找出数字 n 是否是数字 k 的幂的一个简单方法是，n%k 只要余数为 0，就一直将 n 除以 k。
n = k````* m = k * k * ... * k * m
其中m∈(0,k)

因此，应该可以将 n 除以 k p 次，每次余数都为0，最终余数是 m。
若m=1，说明n是k的幂，否则不是。
如果一开始n除以k余数都不为0，说明n不是k的幂，也没有继续算的必要。

  1. public class Solution {
  2.     public boolean isPowerOfTwo(int n) {
  3.         if (n < 1)
  4.             return false;
  5.         while (n % 2 == 0)
  6.             n /= 2;
  7.         return n == 1;
  8.     }
  9. }
  10. public class Solution {
  11.     public boolean isPowerOfThree(int n) {
  12.         if (n < 1)
  13.             return false;
  14.         while (n % 3 == 0)
  15.             n /= 3;
  16.         return n == 1;
  17.     }
  18. }
  19. public class Solution {
  20.     public boolean isPowerOfFour(int n) {
  21.         if (n < 1)
  22.             return false;
  23.         while (n % 4 == 0)
  24.             n /= 4;
  25.         return n == 1;
  26.     }
  27. }

特别的

  1. 对于2的幂来说，可以有更简单的方式

    1. //方式1
    2. return n > 0 && (n & (n-1)) == 0;
    3. //方式2
    4. return n > 0 && (n & (-n)) == 0;

    见：lowbit(n)

  2. 对于4的幂来说，可以有更简单的方式

    1. //方式1
    2. return n > 0 && (n & (n-1)) == 0 && (n & 0xaaaaaaaa) == 0;
    3. //方式2
    4. return n > 0 && (n & (-n)) == 0 && (n & 0x2aaaaaaa) == 0;
    5. //方式3
    6. return n > 0 && (n & (-n)) == 0 && n % 3 == 1;

    见：同余