Easy

题目描述

给你一个正整数 n。

返回大于等于 n 的最小整数 x，使得 x 的二进制表示只包含设置位（即所有位都是 1）。

示例 1：

输入：n = 5
输出：7
解释：7 的二进制表示是 "111"。

示例 2：

输入：n = 10
输出：15
解释：15 的二进制表示是 "1111"。

示例 3：

输入：n = 3
输出：3
解释：3 的二进制表示是 "11"。

约束条件：

  • 1 <= n <= 1000

提示：

  • 找到严格大于 n 的 2 的幂，然后减去 1。

解题思路

这道题要求找到大于等于 n 的最小数，使得其二进制表示全为 1。

核心思路：

只包含设置位的数字有：1、3、7、15、31…，它们的二进制表示分别是：1、11、111、1111、11111…，实际上这些数都可以表示为 2^k - 1 的形式。

解法一：位运算法（推荐） 我们可以从 n 的最高位开始，构造一个所有低位都为 1 的数。具体做法是：

  1. 找到 n 的最高位位置
  2. 构造 (1 << (最高位+1)) - 1，这样得到的数的二进制表示就是从最高位到最低位全为 1

解法二：循环法 从小到大枚举 2^k - 1，直到找到第一个大于等于 n 的值。

解法三：位操作优化 不断将 n 的所有位都设置为 1，直到得到结果。方法是：n |= (n >> 1)，重复这个过程。

推荐使用解法一，代码简洁且时间复杂度最优。

代码实现

class Solution {
public:
    int smallestNumber(int n) {
        // 找到n的最高位位置
        int pos = 0;
        int temp = n;
        while (temp) {
            pos++;
            temp >>= 1;
        }
        
        // 构造2^pos - 1
        int result = (1 << pos) - 1;
        
        // 如果结果小于n，需要再增加一位
        if (result < n) {
            result = (1 << (pos + 1)) - 1;
        }
        
        return result;
    }
};

class Solution:
    def smallestNumber(self, n: int) -> int:
        # 找到n的最高位位置
        pos = n.bit_length()
        
        # 构造2^pos - 1
        result = (1 << pos) - 1
        
        # 如果结果小于n，需要再增加一位
        if result < n:
            result = (1 << (pos + 1)) - 1
            
        return result

public class Solution {
    public int SmallestNumber(int n) {
        // 找到n的最高位位置
        int pos = 0;
        int temp = n;
        while (temp > 0) {
            pos++;
            temp >>= 1;
        }
        
        // 构造2^pos - 1
        int result = (1 << pos) - 1;
        
        // 如果结果小于n，需要再增加一位
        if (result < n) {
            result = (1 << (pos + 1)) - 1;
        }
        
        return result;
    }
}

/**
 * @param {number} n
 * @return {number}
 */
var smallestNumber = function(n) {
    // 找到n的最高位位置
    let pos = 0;
    let temp = n;
    while (temp > 0) {
        pos++;
        temp >>= 1;
    }
    
    // 构造2^pos - 1
    let result = (1 << pos) - 1;
    
    // 如果结果小于n，需要再增加一位
    if (result < n) {
        result = (1 << (pos + 1)) - 1;
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型数值说明
时间复杂度O(log n)需要找到 n 的最高位位置
空间复杂度O(1)只使用常数额外空间

相关题目