2025-06-18：仅含置位位的最小整数。用go语言，给定一个正整数 n，求一个不小于 n 的最小整数 x，且该整数的二进制表

2025-06-18：仅含置位位的最小整数。用go语言，给定一个正整数 n，求一个不小于 n 的最小整数 x，且该整数的二进制表示中，1 的个数与给定的“置位”数量相同。换句话说，x 的二进制中有指定数量的位是 1，且 x ≥ n，找到满足条件的最小的这样的 x。

1 <= n <= 1000。

输入： n = 5。

输出： 7。

解释：

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

题目来自力扣3370。

解决步骤（假设题目是求最小的全 1 数 ≥ n）

1. 1. 计算 n 的二进制位数：
   • • 使用 bits.Len(uint(n)) 得到 n 的二进制表示的长度（即最高有效位的位数）。
   • • 例如，n = 5（101），bits.Len(5) 返回 3。
2. 2. 构造全 1 的数：
   • • 全 1 的数的二进制表示是 k 个 1，其值为 2^k - 1。
   • • 例如，k = 3，2^3 - 1 = 7（111）。
3. 3. 检查是否满足 ≥ n：
   • • 如果 2^k - 1 ≥ n，则直接返回 2^k - 1。
   • • 否则，需要增加位数 k 并重新构造全 1 的数。
   • • 例如，n = 8：
     • • bits.Len(8) 返回 4（8 是 1000）。
     • • 2^4 - 1 = 15（1111），15 ≥ 8，返回 15。
   • • 例如，n = 5：
     • • bits.Len(5) 返回 3。
     • • 2^3 - 1 = 7，7 ≥ 5，返回 7。

时间复杂度和空间复杂度

• • 时间复杂度：
  • • bits.Len(uint(n)) 的时间复杂度是 O(1)（通常是通过硬件指令或快速位操作实现）。
  • • 构造 1 << k - 1 也是 O(1)。
  • • 因此，总时间复杂度是 O(1)。
• • 空间复杂度：
  • • 只使用了常数级别的额外空间（几个变量）。
  • • 因此，总空间复杂度是 O(1)。

总结

• • 题目可能是求“不小于 n 的最小全 1 数”。
• • 代码通过 bits.Len 找到 n 的二进制位数 k，然后返回 (1 << k) - 1。
• • 时间复杂度和空间复杂度均为 O(1)。

Go完整代码如下：

package main

import (
    "fmt"
    "math/bits"
)

func smallestNumber(n int)int {
    return1<<bits.Len(uint(n)) - 1
}

func main() {
    n := 5
    fmt.Println(smallestNumber(n))
}

Python完整代码如下：

# -*-coding:utf-8-*-

def smallest_number(n: int) -> int:
    # bits_len = n的二进制长度
    bits_len = n.bit_length()
    return (1 << bits_len) - 1

if __name__ == "__main__":
    n = 5
    print(smallest_number(n))