LeetCode342-4的幂

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/power-of-four/

中文链接：https://leetcode-cn.com/problems/power-of-four/

题目详述

给定一个整数 (32 位有符号整数)，请编写一个函数来判断它是否是 4 的幂次方。

示例 1:

1
2
输入: 16
输出: true

示例 2:

1
2
输入: 5
输出: false

进阶：
你能不使用循环或者递归来完成本题吗？

题目详解

位运算。

4的幂必然是 2的幂，只不过它的 1 只能出现在奇数位置（按从右往左，第一位为奇数位）。

  • n > 0。
  • 二进制位里面只有一个 1。
  • 唯一的一个 1 在奇数位上。

根据上面三个关键条件，合理运用位运算进行判断即可，有很多种写法。

1
2
3
4
5
6
7
8
9
public class LeetCode_00342 {

    public boolean isPowerOfFour(int num) {
        return num > 0 && (num & (num - 1)) == 0 && (num & 0x55555555) != 0;
//        return num > 0 && (num & (num - 1)) == 0 && (num & 0x55555555) == num;
//        return num > 0 && (num & (num - 1)) == 0 && (num & 0xaaaaaaaa) == 0;
//        return num > 0 && (num & (num - 1)) == 0 && (num | 0x55555555) == 0x55555555;
    }
}