LeetCode - Easy - 342. Power of Four

悠悠 2022-12-27 06:25 153阅读 0赞

## Topic ##

Bit Manipulation

## Description ##

[https://leetcode.com/problems/power-of-four/][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 ##

**方法1**：数学除余

--------------------

**方法2**：位运算

对于一个整数而言，如果这个数是 4 的幂次方，那它必定也是 2 的幂次方。

从上表看出，是4的幂次方的数二进制形式中的1在奇数位。

于是，检测值与一个特殊的数做 & 位运算，用来判断检测值的二进制形式中的1是否在奇数位。

这个特殊的数有如下特点：

*  足够大，但不能超过 32 位，即最大为 31 个 1
 *  它的二进制表示中奇数位为 1 ，偶数位为 0

符合这两个条件的二进制数是`1010101010101010101010101010101`，转换成`0x55555555`。

## Submission ##

public class PowerOfFour { 
    	//方法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
    	}
    
    	//方法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_leetcode.com_problems_power-of-four]: https://leetcode.com/problems/power-of-four/