LeetCode342——4的幂

Love The Way You Lie 2022-04-25 08:34 146阅读 0赞

我的LeetCode代码仓：[https://github.com/617076674/LeetCode][https_github.com_617076674_LeetCode]

原题链接：[https://leetcode-cn.com/problems/power-of-four/][https_leetcode-cn.com_problems_power-of-four]

题目描述：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjMxOTI2_size_16_color_FFFFFF_t_70][]

知识点：位运算

### 思路：先将2的幂和4的幂都筛选出来，再筛选出4的幂 ###

（1）先去除小于0的数。

（2）**如何筛选出2的幂呢**？

对于2的幂，其二进制表示是有规律的，就是其32位二进制表示里只有一个1，如：

00000000 00000000 00000000 00000001

00000000 00000000 00000000 00000010

00000000 00000000 00000000 00000100

00000000 00000000 00000000 00001000

……

因此只需满足(num & (num - 1)) == 0，即可说明这个数是2的幂。

（3）**如何筛选在2的幂中筛选出4的幂吗**？

对于4的幂，其二进制表示也是有规律的，如：

00000000 00000000 00000000 00000001

00000000 00000000 00000000 00000100

00000000 00000000 00000000 00010000

00000000 00000000 00000000 01000000

……

5的二进制表示是0101，0x55555555的二进制表示是01010101 01010101 01010101 01010101。

如果是2的幂但不是4的幂，显然会有(num & 0x55555555) == 0。

如果是4的幂，显然会有(num & 0x55555555) != 0。

时间复杂度和空间复杂度均是O(1)。

JAVA代码：

public class Solution {
    
        public boolean isPowerOfFour(int num) {
            if (0 > num || (num & (num - 1)) != 0) {
                return false;
            }
            return (num & 0x55555555) != 0;
        }
    
    }

LeetCode解题报告：

![20190530191456231.png][]

[https_github.com_617076674_LeetCode]: https://github.com/617076674/LeetCode
[https_leetcode-cn.com_problems_power-of-four]: https://leetcode-cn.com/problems/power-of-four/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjMxOTI2_size_16_color_FFFFFF_t_70]: /images/20220125/650f1c0e893641e5b56a1cab6abbbe35.png
[20190530191456231.png]: /images/20220125/36a8f849a4bc4d9ba16d975309e594df.png