题目描述

给你一个正整数 n。

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

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

样例

输入： n = 5

输出： 7

解释：

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

输入： n = 10

输出： 15

解释：

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

输入： n = 3

输出： 3

解释：

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

限制

• 1 <= n <= 1000

算法

(模拟) $O(\log n)$

1. 判断 $n$ 的二进制位数，然后所有位都 置位 后返回答案。

时间复杂度

• 遍历的二进制位数的时间复杂度为 $O(\log n)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    int smallestNumber(int n) {
        int ans = 0;

        while (n) {
            ans = ans << 1 | 1;
            n >>= 1;
        }

        return ans;
    }
};