Skip to content
Branch: master
Find file History
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
..
Failed to load latest commit information.
342. Power of Four.go
342. Power of Four_test.go
README.md

README.md

342. Power of Four

题目

Given an integer (signed 32 bits), write a function to check whether it is a power of 4.

Example 1:

Input: 16
Output: true

Example 2:

Input: 5
Output: false

Follow up: Could you solve it without loops/recursion?

题目大意

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

解题思路

  • 判断一个数是不是 4 的 n 次方。
  • 这一题最简单的思路是循环,可以通过。但是题目要求不循环就要判断,这就需要用到数论的知识了。
  • 证明 (4^n - 1) % 3 == 0,(1) 4^n - 1 = (2^n + 1) * (2^n - 1)(2) 在任何连续的 3 个数中 (2^n-1)(2^n)(2^n+1),一定有一个数是 3 的倍数。(2^n) 肯定不是 3 的倍数,那么 (2^n-1) 或者 (2^n+1) 中一定有一个是 3 的倍数。所以 4^n-1 一定是 3 的倍数。
You can’t perform that action at this time.