# LeetCode - Easy - 342. Power of Four

2020-12-08 12:23:29

# LeetCode - Easy - 342. Power of Four

Bit Manipulation

## Description

https://leetcode.com/problems/power-of-four/

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³¹ <= n <= 2³¹ - 1

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

## Analysis

Method 1： Mathematical Division

Method 2： An operation

For an integer , If this number is 4 Power square , Then it must be 2 Power square .

Decimal system Binary system
2 10
4 100 （1 In the 3 position ）
8 1000
16 10000（1 In the 5 position ）
32 100000
64 1000000（1 In the 7 position ）
128 10000000
256 100000000（1 In the 9 position ）
512 1000000000
1024 10000000000（1 In the 11 position ）

It can be seen from the above table that , yes 4 In binary form to the power of 1 In odd digits .

therefore , The test value is done with a special number & An operation , In the binary form used to determine the detected value 1 Is it in the odd number .

This special number has the following characteristics ：

• Large enough , But not more than 32 position , That is, the maximum is 31 individual 1
• In its binary representation, the odd digits are 1 , Even digits are 0

The binary number that meets these two conditions is `1010101010101010101010101010101`, convert to `0x55555555`.

## Submission

``````public class PowerOfFour {
// Method 2：
public boolean isPowerOfFour(int num) {
return num > 0 && (num & (num - 1)) == 0 && (num & 0x55555555) != 0;
// 0x55555555 is to get rid of those power of 2 but not power of 4
// so that the single 1 bit always appears at the odd position
}

// Method 1：
public boolean isPowerOfFour2(int num) {
while ((num != 0) && (num % 4 == 0)) {
num /= 4;
}
return num == 1;
}
}
``````

## Test

``````public class PowerOfFourTest {

@Test
public void test() {
PowerOfFour pf = new PowerOfFour();

assertTrue(pf.isPowerOfFour(4));
assertTrue(pf.isPowerOfFour(16));
assertFalse(pf.isPowerOfFour(17));
assertFalse(pf.isPowerOfFour(5));
}

@Test
public void test2() {
PowerOfFour pf = new PowerOfFour();

assertTrue(pf.isPowerOfFour2(4));
assertTrue(pf.isPowerOfFour2(16));
assertFalse(pf.isPowerOfFour2(17));
assertFalse(pf.isPowerOfFour2(5));
}
}
``````

https://chowdera.com/2020/12/20201208122305237s.html