LeetCode - Easy - 342. Power of Four-蒲公英云

LeetCode - Easy - 342. Power of Four

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

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

方法1：数学除余

方法2：位运算

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

十进制	二进制
2	10
4	100 （1 在第 3 位）
8	1000
16	10000（1 在第 5 位）
32	100000
64	1000000（1 在第 7 位）
128	10000000
256	100000000（1 在第 9 位）
512	1000000000
1024	10000000000（1 在第 11 位）

从上表看出，是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));
    }
}