# 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?

```cpp
// Naive
bool isPowerOfFour(int num) { // time: O(logn); space: O(1)
    if (num == 0) return false;
    if (num == 1) return true;
    int n = num;
    while (n > 1) {
        if (n % 4 != 0) return false;
        n /= 4;
    }
    return n == 1;
}
```

{% hint style="info" %}
4^0 = 1\
4^1 = 4 (100)\
4^2 = 16(1000)\
4^3 = 64(10000)\
...\
可以觀察到4的power在2進位表示時都只有一個digit 1，其他都是0。\
bit manipulation中的n & (n - 1)操作會得到一個移除最後一個digit 1的結果，因為4的power只有一個1，所以操作完之後應該要得到0。\
0x55555555是為了在32-bit的integer中取到位於奇數位置的digit 1，0x55在二進位表示為01010101，位於奇數位置的1才能組成4的power。
{% endhint %}

```cpp
// Bit Manipulation
bool isPowerOfFour(int num) { // time: O(1); space: O(1)
    // num & (num - 1): remove the last significant digit
    // if a number is power of 4, it only has one digit-1
    // 0x55555555 is to select out digit-1s in odd positions in binary representation
    return num > 0 && (num & (num - 1)) == 0 && (num & 0x55555555) != 0;
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/bit-manipulation/342.-power-of-four.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.