What is the best way to solve the Smallest Number With All Set Bits problem?

The most efficient solution is to find the next power of two greater than or equal to n, and then subtract 1 from it.

How do you calculate the next power of two using bit manipulation?

You can use bit shifting techniques, filling all bits below the highest set bit, to find the next power of two.

What is the time complexity of solving this problem?

The time complexity depends on the method used for bit manipulation, but typically it is O(log n).

What should I do if n is already a number with all set bits?

If n already has all set bits, the answer is simply n itself.

How does GhostInterview help with this problem?

GhostInterview guides you through the bit manipulation approach and ensures you avoid unnecessary calculations, offering efficient solutions.

#3370

Easy

auto_awesome数学·位运算

LeetCode 题解工作台

仅含置位位的最小整数

给你一个正整数 n 。返回大于等于 n 且二进制表示仅包含置位位的最小整数 x 。置位位指的是二进制表示中值为 1 的位。示例 1：输入： n = 5 输出： 7 解释： 7 的二进制表示是 "111" 。示例 2：输入： n = 10 输出： 15 解释： 15 的二进制表…

数学位运算

题目描述

给你一个正整数 n。

返回 大于等于 n 且二进制表示仅包含置位位的最小整数 x 。

置位位指的是二进制表示中值为 1 的位。

示例 1：

输入： n = 5

输出： 7

解释：

7 的二进制表示是 "111"。

示例 2：

输入： n = 10

输出： 15

解释：

15 的二进制表示是 "1111"。

示例 3：

输入： n = 3

输出： 3

解释：

3 的二进制表示是 "11"。

提示：

1 <= n <= 1000

lightbulb

解题思路

方法一：位运算

我们从 $x = 1$ 开始，不断将 $x$ 左移，直到 $x - 1 \geq n$ ，此时 $x - 1$ 就是我们要找的答案。

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

1

2

3

4

5

6

7

class Solution:
    def smallestNumber(self, n: int) -> int:
        x = 1
        while x - 1 < n:
            x <<= 1
        return x - 1

speed

复杂度分析

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

psychology

面试官常问的追问

外企场景

question_mark
Candidate understands the concept of powers of two and bit manipulation.
question_mark
Candidate applies bit manipulation to efficiently compute the answer.
question_mark
Candidate avoids brute force approaches and seeks optimized solutions.

warning

常见陷阱

外企场景

error
Misunderstanding the binary representation of numbers with all set bits.
error
Using inefficient or brute force methods to calculate the result.
error
Overcomplicating the problem and missing simple bitwise solutions.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if n is already a number with all set bits?
arrow_right_alt
What if n is at the maximum limit (1000)?
arrow_right_alt
What if n is a power of two, and no subtraction is needed?

help

常见问题

外企场景

继续练习

#3307 找出第 K 个字符 II #3304 找出第 K 个字符 I #3444 使数组包含目标值倍数的最少增量