2025-06-18:仅含置位位的最小整数。用go语言,给定一个正整数 n,求一个不小于 n 的最小整数 x,且该整数的二进制表示中,1 的个数与给定的“置位”数量相同。换句话说,x 的二进制中有指定数量的位是 1,且 x ≥ n,找到满足条件的最小的这样的 x。
1 <= n <= 1000。
输入: n = 5。
输出: 7。
解释:
7 的二进制表示是 "111"。
题目来自力扣3370。
1
数 ≥ n
)n
的二进制位数:bits.Len(uint(n))
得到 n
的二进制表示的长度(即最高有效位的位数)。n = 5
(101
),bits.Len(5)
返回 3
。1
的数:1
的数的二进制表示是 k
个 1
,其值为 2^k - 1
。k = 3
,2^3 - 1 = 7
(111
)。≥ 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)
。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))
}
# -*-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))