2026-06-03：统计单比特整数。用go语言，给定一个整数 n。我们把形如其二进制表示中每一位都一样（全是 0 或全是 1）的整数称为“单比特

2026-06-03：统计单比特整数。用go语言，给定一个整数 n。我们把形如其二进制表示中每一位都一样（全是 0 或全是 1）的整数称为“单比特数”。

要求你统计在区间 [0, n]（包含 0 和 n）内一共有多少个“单比特数”。输出这个数量即可。

0 <= n <= 1000。

输入： n = 4。

输出： 3。

解释：

范围[0, 4]内的整数对应的二进制表示为”0″、”1″、”10″、”11″和”100″。

只有0、1和3满足单比特条件。因此答案是3。

题目来自力扣3827。

一、先梳理手动解题步骤

以输入n=4为例，完整过程：

1.遍历区间内所有数字：依次检查 0、1、2、3、4 这5个数字

2.逐个判断是否为单比特数

• 数字0：二进制0→ 全0 → 是单比特数

• 数字1：二进制1→ 全1 → 是单比特数

• 数字2：二进制10→ 有1有0 → 不是

• 数字3：二进制11→ 全1 → 是单比特数

• 数字4：二进制100→ 有1有0 → 不是

3.统计符合条件的数量：0、1、3 共3个 → 最终结果为3

二、代码实现的核心逻辑分步解析

代码没有逐个遍历判断，而是用数学规律直接计算，效率更高，步骤如下：

步骤1：确定核心规律

所有合法的单比特数（全1数）有固定格式：
1位全1：1(2¹-1)、2位全1：3(2²-1)、3位全1：7(2³-1)、4位全1：15(2⁴-1)……
再加上数字0，就是全部的单比特数。

步骤2：计算数字 n+1 的二进制位数

代码中执行n + 1，再用bits.Len()计算这个数的二进制有效位数：

• 示例中 n=4，n+1=5，5的二进制是101，有效位数为3

• 这个位数代表：[0,n]内的全1单比特数，最多有多少位

步骤3：推导单比特数总个数

二进制位数 = 全1单比特数的个数，再加上数字0，就是最终总数：

• 位数3 → 对应3个全1数：1(1位)、3(2位)、7(3位)

• 过滤掉超过n的数（7>4，排除），剩余1、3两个全1数

• 加上数字0，总个数=2+1=3，和题目结果一致

步骤4：输出最终结果

代码直接返回计算出的总数，完成统计。

三、复杂度分析 1. 时间复杂度

• 代码仅执行了固定次数的数学运算（加法、二进制位数计算），没有循环、没有遍历

• 无论n的取值是0还是1000，运算次数都不变

• 结论：时间复杂度为 O(1)（常数级）

2. 额外空间复杂度

• 代码只定义了几个普通变量（n、result），没有使用数组、切片、map等动态数据结构

• 没有随输入规模增长而占用更多内存

• 结论：额外空间复杂度为 O(1)（常数级）

总结

1. 解题核心：利用单比特数的二进制规律，不遍历直接计算；

2. 完整流程：计算n+1的二进制位数 → 确定全1单比特数 → 加上数字0统计总数；

3. 复杂度：时间O(1)，额外空间O(1)。

Go完整代码如下：

package main

 import (
    "fmt"
    "math/bits"
)

 func countMonobit(n int)int {
    return bits.Len(uint(n + 1))
}

 func main() {
    n := 4
    result := countMonobit(n)
    fmt.Println(result)
}

Python完整代码如下：

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

 def count_monobit(n: int) -> int:
    """
    计算需要多少个单比特数（形如 2^k - 1）才能覆盖到 n
    等价于计算 (n+1) 的二进制位数
    """
    return (n + 1).bit_length()

 def main():
    n = 4
    result = count_monobit(n)
    print(result)

 if __name__ == "__main__":
    main()

C++完整代码如下：

  

  

  



 // 如果编译器支持C++20，使用std::bit_width
int countMonobit(int n) {
    // std::bit_width返回无符号整数类型的二进制位数
    // 注意：std::bit_width(0)返回0，与bits.Len行为一致
    return std::bit_width(static_cast 
 
 int 
 >(n +  
 1 
 )); 
 
 
 } 
 
 
 
 
 int 
  main() { 
 
 
      
 int 
  n =  
 4 
 ; 
 
 
      
 int 
  result = countMonobit(n); 
 
 
     std::cout << result << std::endl; 
 
 
      
 return 
 0 
 ; 
 
 
 } 
 
 
 

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。