How can I quickly check if a number is a power of four?

Use bit manipulation: confirm n > 0, n & (n - 1) == 0, and the set bit is at an even position.

Can recursion be used efficiently for Power of Four?

Yes, recursively divide by 4 until reaching 1 or encountering a remainder, reflecting the math pattern.

What common mistakes occur in Power of Four checks?

Misidentifying powers of two as powers of four or relying on floating-point logarithms can cause incorrect results.

Is there a purely mathematical approach without bit operations?

Repeatedly divide n by 4 and check if the final result is 1. This avoids bit manipulation entirely.

Why is bit position important in the Power of Four problem?

Because only powers of four have their single set bit at even positions, ensuring correct distinction from other powers of two.

#342

Easy

auto_awesome数学·位运算

LeetCode 题解工作台

4的幂

给定一个整数，写一个函数来判断它是否是 4 的幂次方。如果是，返回 true ；否则，返回 false 。整数 n 是 4 的幂次方需满足：存在整数 x 使得 n == 4 x 示例 1：输入： n = 16 输出： true 示例 2：输入： n = 5 输出： false 示例 3：输入…

数学位运算递归

题目描述

给定一个整数，写一个函数来判断它是否是 4 的幂次方。如果是，返回 true ；否则，返回 false 。

整数 n 是 4 的幂次方需满足：存在整数 x 使得 n == 4^x

示例 1：

输入：n = 16
输出：true

示例 2：

输入：n = 5
输出：false

示例 3：

输入：n = 1
输出：true

提示：

-2³¹ <= n <= 2³¹ - 1

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

lightbulb

解题思路

方法一：位运算

如果一个数是 $4$ 的幂次方，那么这个数必须是大于 $0$ 的。不妨假设这个数是 $4^x$ ，即 $2^{2x}$ ，那么这个数的二进制表示中有且仅有一个 $1$ ，且这个 $1$ 出现在偶数位上。

因此，我们首先判断这个数是否大于 $0$ ，然后判断这个数是否是 $2^{2x}$ ，即 $n$ 与 $n-1$ 的按位与结果是否为 $0$ ，最后判断这个数的 $1$ 是否出现在偶数位上，即 $n$ 与 $\textit{0xAAAAAAAA}$ 的按位与结果是否为 $0$ 。如果这三个条件都满足，那么这个数就是 $4$ 的幂次方。

时间复杂度 $O(1)$ ，空间复杂度 $O(1)$ 。

1

2

3

4

class Solution:
    def isPowerOfFour(self, n: int) -> bool:
        return n > 0 and (n & (n - 1)) == 0 and (n & 0xAAAAAAAA) == 0

speed

复杂度分析

指标	值
时间	complexity ranges from O(1) for bit manipulation to O(log n) for division or recursion. Space complexity is O(1) for iterative solutions and O(log n) for recursion due to call stack usage.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Ask about distinguishing power of two versus power of four with bit operations.
question_mark
Probe candidate understanding of position of the set bit in powers of four.
question_mark
Expect efficient solutions rather than brute force iterations or floating-point checks.

warning

常见陷阱

外企场景

error
Checking only n > 0 or n & (n - 1) without verifying bit position can misidentify powers of two as powers of four.
error
Using floating-point logarithms may introduce precision errors in edge cases.
error
Failing to handle n = 1 correctly, which is a valid power of four (4^0).

swap_horiz

进阶变体

外企场景

arrow_right_alt
Power of Two check without enforcing power of four constraints.
arrow_right_alt
Power of Eight verification requiring similar bit and math insights.
arrow_right_alt
Recursive-only solution without bit manipulation optimizations.

help

常见问题

外企场景

继续练习

#231 2 的幂 #779 第K个语法符号 #326 3 的幂