What is the fastest way to check if a number is a power of two?

The fastest method is using bit manipulation: return n > 0 && (n & (n - 1)) == 0, which checks the single-bit pattern directly.

Can recursion be used to solve Power of Two efficiently?

Yes, recursion divides n by 2 repeatedly until reaching 1, but it uses O(log n) stack space compared to O(1) for bit manipulation.

Why does n & (n - 1) work for detecting powers of two?

Because powers of two have exactly one 1-bit in binary; subtracting 1 flips all lower bits, and ANDing with n clears the single 1-bit if it was a power of two.

Are negative numbers ever considered powers of two?

No, by definition, only positive integers of the form 2^x are powers of two, so negatives always return false.

Does using logarithms provide a reliable solution for large integers?

It works mathematically but may suffer from floating-point precision errors for very large integers, making bit manipulation safer.

#231

Easy

auto_awesome数学·位运算

LeetCode 题解工作台

2 的幂

给你一个整数 n ，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。如果存在一个整数 x 使得 n == 2 x ，则认为 n 是 2 的幂次方。示例 1：输入： n = 1 输出： true 解释： 2 0 = 1 示例 2：输入： n = 16 输…

数学位运算递归

题目描述

给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。

如果存在一个整数 x 使得 n == 2^x ，则认为 n 是 2 的幂次方。

示例 1：

输入：n = 1
输出：true
解释：2⁰ = 1

示例 2：

输入：n = 16
输出：true
解释：2⁴ = 16

示例 3：

输入：n = 3
输出：false

提示：

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

进阶：你能够不使用循环/递归解决此问题吗？

lightbulb

解题思路

方法一：位运算

根据位运算的性质，执行 $\texttt{n\&(n-1)}$ 可以消去二进制形式的 $n$ 的最后一位 $1$ 。因此，如果 $n \gt 0$ ，并且满足 $\texttt{n\&(n-1)}$ 结果为 $0$ ，则说明 $n$ 是 $2$ 的幂。

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

1

2

3

4

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Clarifies whether negative numbers and zero should return false.
question_mark
Hints at using bit manipulation rather than iterative loops.
question_mark
Tests understanding of the mathematical pattern behind powers of two.

warning

常见陷阱

外企场景

error
Not handling zero and negative inputs correctly, returning true incorrectly.
error
Using iterative multiplication or division without stopping conditions, causing infinite loops.
error
Relying on floating-point logs without tolerance, leading to incorrect results for large n.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Check if a number is a power of three or five using a similar recursive or bit-mimicking approach.
arrow_right_alt
Return the largest power of two less than or equal to n using bit manipulation.
arrow_right_alt
Count how many numbers in an array are powers of two using the same n & (n - 1) trick.

help

常见问题

外企场景

继续练习

#342 4的幂 #779 第K个语法符号 #233 数字 1 的个数