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. 1. 遍历区间内所有数字：依次检查 0、1、2、3、4 这5个数字
2. 2. 逐个判断是否为单比特数
   • • 数字0：二进制0 → 全0 → 是单比特数
   • • 数字1：二进制1 → 全1 → 是单比特数
   • • 数字2：二进制10 → 有1有0 → 不是
   • • 数字3：二进制11 → 全1 → 是单比特数
   • • 数字4：二进制100 → 有1有0 → 不是
3. 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. 1. 解题核心：利用单比特数的二进制规律，不遍历直接计算；
2. 2. 完整流程：计算n+1的二进制位数 → 确定全1单比特数 → 加上数字0统计总数；
3. 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++完整代码如下：

.

#include <iostream>
#include <bit>
#include <climits>

// 如果编译器支持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<unsigned int>(n + 1));
}

int main() {
    int n = 4;
    int result = countMonobit(n);
    std::cout << result << std::endl;
    return0;
}

在这里插入图片描述

·