86 - 4的幂

题目

给定一个整数 (32 位有符号整数)，请编写一个函数来判断它是否是 4 的幂次方。

示例 1:

输入: 16 输出: true

示例 2:

输入: 5 输出: false

进阶： 你能不使用循环或者递归来完成本题吗？

解答

这不和3的幂一模一样吗。。

取余

var isPowerOfFour = function (num) {
  if (num <= 0) {
    return false
  }
  while (num % 4 === 0) {
    num = Math.floor(num / 4)
  }
  return num === 1
};

Runtime: 64 ms, faster than 90.43% of JavaScript online submissions for Power of Four.

Memory Usage: 35.8 MB, less than 100.00% of JavaScript online submissions for Power of Four.

4进制

var isPowerOfFour = function (num) {
  if (num <= 0) {
    return false
  }
  return /^10*$/.test(num.toString(4))
};

Runtime: 68 ms, faster than 79.61% of JavaScript online submissions for Power of Four.

Memory Usage: 35.7 MB, less than 100.00% of JavaScript online submissions for Power of Four.

log

var isPowerOfFour = function (num) {
  return (Math.log10(num) / Math.log10(4)) % 1 === 0
};

Runtime: 84 ms, faster than 16.84% of JavaScript online submissions for Power of Four.

Memory Usage: 35.6 MB, less than 100.00% of JavaScript online submissions for Power of Four.

看起来骚但跑起来慢哈哈哈😂

32位最大值

int32最大值为2147483647，因此$log_4(2147483647)=lg(2147483647)/lg(4)=15.4999999997$

换言之，int32最大的4的幂是$4^{15}=1073741824$

var isPowerOfFour = function (num) {
  return num > 0 && 1073741824 % num === 0
};

似乎不对？

go

func isPowerOfFour(num int) bool {
    if num <= 0 {
        return false
    }
    for num%4 == 0 {
        num /= 4
    }
    return num == 1
}

Runtime: 4 ms, faster than 40.63% of Go online submissions for Power of Four.

Memory Usage: 2.1 MB, less than 100.00% of Go online submissions for Power of Four.

func isPowerOfFour(num int) bool {
    result, _ := regexp.MatchString("^10*$", strconv.FormatInt(int64(num), 4))
    return result
}

Runtime: 8 ms, faster than 40.63% of Go online submissions for Power of Four.

Memory Usage: 5.7 MB, less than 100.00% of Go online submissions for Power of Four.

二进制位

作者：infinity-2

链接：https://leetcode-cn.com/problems/power-of-four/solution/java-wei-by-infinity-2/

32位数如果是4的幂，那么只有奇数位有且只有一个1，偶数位都是0。判断条件为与0xaaaaaaaa做与运算结果为0。（a=1010）

作者：elliotxx

链接：https://leetcode-cn.com/problems/power-of-four/solution/0msyi-xing-dai-ma-de-go-shi-xian-by-elliotxx/

func isPowerOfFour(num int) bool {
    return num > 0 && num&(num-1) == 0 && 0xaaaaaaaa&num == 0
}

Runtime: 0 ms, faster than 100.00% of Go online submissions for Power of Four.

Memory Usage: 2.1 MB, less than 100.00% of Go online submissions for Power of Four.

递归

https://leetcode.com/problems/power-of-four/discuss/384752/Shortest-than-shortest

var isPowerOfFour = function (num) {
  if (num === 1) {
    return true
  }
  if (num === 0) {
    return false
  }
  return (num % 4 === 0 && isPowerOfFour(num / 4));
};

Runtime: 60 ms, faster than 96.41% of JavaScript online submissions for Power of Four.

Memory Usage: 35.7 MB, less than 100.00% of JavaScript online submissions for Power of Four.