> For the complete documentation index, see [llms.txt](https://txfs19260817.gitbook.io/leetcode-go-notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://txfs19260817.gitbook.io/leetcode-go-notes/solutions/342.-power-of-four.md).

# 342. Power of Four

## LeetCode [342. Power of Four](https://leetcode-cn.com/problems/power-of-four/)

### Description

Given an integer `n`, return *`true` if it is a power of four. Otherwise, return `false`*.

An integer `n` is a power of four, if there exists an integer `x` such that `n == 4^x`.

**Example 1:**

```
Input: n = 16
Output: true
```

**Example 2:**

```
Input: n = 5
Output: false
```

**Example 3:**

```
Input: n = 1
Output: true
```

**Constraints:**

* `-2^31 <= n <= 2^31 - 1`

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

### Tags

Bit Manipulation

### Solution

From LeetCode [231. Power of Two](/leetcode-go-notes/solutions/231.-power-of-two.md) we know that a positive number `n` is a power of 2 when `n&(n-1) == 0`. We also know if a positive number `n` is a power of 4, it must a power of 2. Therefore, we can start off the characteristics of `n = 4^x`.

1. Such numbers represented in binary are like 1, 100, 10000, ... . We can find that 1 appears at odd-bits. Thus, we can use a number whose even-bits are all filled with 1 and use it to test with `n`;
2. `4^x % 3 == 1`.

We can derive 2 statements from both characteristics, and append either of them to the solution of Power of Two.

1. `n&0xaaaaaaaa == 0`;
2. `n%3 == 1`.

### Complexity

* Time complexity: $$O(1)$$
* Space complexity: $$O(1)$$

### Code

#### Solution 1:

```go
func isPowerOfFour(n int) bool {
   return n > 0 && n&(n-1) == 0 && n%3 == 1
}
```

#### Solution 2:

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

## Reference

1. [4的幂](https://leetcode-cn.com/problems/power-of-four/solution/4de-mi-by-leetcode-solution-b3ya/)