3370. 仅含置位位的最小整数
题目描述
给你一个正整数 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
解法
方法一：位运算
我们从 $x = 1$ 开始，不断将 $x$ 左移，直到 $x - 1 \geq n$，此时 $x - 1$ 就是我们要找的答案。
时间复杂度 $O(\log n)$，空间复杂度 $O(1)$。
Python3
class Solution:
def smallestNumber(self, n: int) -> int:
x = 1
while x - 1 < n:
x <<= 1
return x - 1
Java
class Solution {
public int smallestNumber(int n) {
int x = 1;
while (x - 1 < n) {
x <<= 1;
}
return x - 1;
}
}
C++
class Solution {
public:
int smallestNumber(int n) {
int x = 1;
while (x - 1 < n) {
x <<= 1;
}
return x - 1;
}
};
Go
func smallestNumber(n int) int {
x := 1
for x-1 < n {
x <<= 1
}
return x - 1
}
TypeScript
function smallestNumber(n: number): number {
let x = 1;
while (x - 1 < n) {
x <<= 1;
}
return x - 1;
}