当前位置:网站首页>LeetCode - Easy - 342. Power of Four

LeetCode - Easy - 342. Power of Four

2020-12-08 12:23:29 Giant ship

LeetCode - Easy - 342. Power of Four

Topic

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));
	}
}

版权声明
本文为[Giant ship]所创,转载请带上原文链接,感谢
https://chowdera.com/2020/12/20201208122305237s.html