LeetCode 342. 4的幂

约 3 分钟
文章信息 6 个分类 3 个标签
分类
LeetCode CodeTop 简单 未解决 2-5 字节
标签
数学 位运算 递归

题目描述

✅ 342. 4的幂

image-20260928223837038

题意分析

判断给定的 32 位有符号整数是否等于 4^k，其中 k 为非负整数。4 的幂必须为正，1 对应 k = 0，也应返回 true；进阶要求不使用循环或递归。

解法：位运算判定

核心思路

[!blue]

因为 $4^k = 2^{2k}$，4 的幂在二进制中恰好只有一个 1，且这个 1 位于从 0 开始计数的偶数位。依次检查正数、只有一个 1、该位位置正确这三个条件即可。

对正整数，减一会把最低的 1 变为 0，并把它右侧的 0 变为 1；再与原数按位与，恰好清除原数最低的那个 1。因此 n & (n - 1) == 0 等价于原数只有一个 1。必须先排除 0，因为 0 也会通过这个位运算判断。

十六进制数字 5 对应二进制 0101，所以 0x55555555 的第 0、2、4……30 位为 1。已经确认 n 只有一个 1 后，n & 0x55555555 != 0 就说明该位为偶数位。此时 n = 2^(2k) = 4^k，三项条件既必要也充分，并且满足不用循环或递归的要求。

解题步骤

  1. 若 n <= 0，返回 false。
  2. 若 n & (n - 1) 不为 0，说明有多个 1，返回 false。
  3. 返回 n 与偶数位掩码按位与的结果是否非零。

代码实现

class Solution {
    public boolean isPowerOfFour(int n) {
        if (n <= 0) {
            return false;
        }

        // 清除最低一后必须归零，确保只有一个有效位
        if ((n & (n - 1)) != 0) {
            return false;
        }

        // 掩码只保留零基偶数位，进一步排除二的奇数次幂
        return (n & 0x55555555) != 0;
    }
}

func isPowerOfFour(n int) bool {
    if n <= 0 {
        return false
    }

    // 清除最低一后必须归零，确保只有一个有效位
    if n&(n-1) != 0 {
        return false
    }

    // 掩码只保留零基偶数位，进一步排除二的奇数次幂
    return n&0x55555555 != 0
}

复杂度分析

  • 时间复杂度：$O(1)$，固定次数的比较与位运算。
  • 空间复杂度：$O(1)$。

关键点总结

[!green]

  • 单一位与偶数位置是两个不同条件。
  • 一对应四的零次幂，必须通过。

易错点总结

[!yellow]

  • 只判断 2 的幂，会把唯一 1 位于奇数位的数也接受。
  • 只检查偶数位掩码，无法排除多个 1 的数。
  • 掩码改成 0xAAAAAAAA，检查的将是相反位置。

相似题目

题目 难度 关联与区别
231. 2 的幂 简单 先满足唯一一个二进制1，再要求该1位于偶数位位置，才能是4的幂。
326. 3 的幂 简单 同样判固定底数的幂，但3的幂不能利用本题的交替位掩码。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/73812732
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！