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

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。一、先梳理手动解题步骤以输入n4为例完整过程遍历区间内所有数字依次检查 0、1、2、3、4 这5个数字逐个判断是否为单比特数数字0二进制0→ 全0 → 是单比特数数字1二进制1→ 全1 → 是单比特数数字2二进制10→ 有1有0 → 不是数字3二进制11→ 全1 → 是单比特数数字4二进制100→ 有1有0 → 不是统计符合条件的数量0、1、3 共3个 → 最终结果为3二、代码实现的核心逻辑分步解析代码没有逐个遍历判断而是用数学规律直接计算效率更高步骤如下步骤1确定核心规律所有合法的单比特数全1数有固定格式1位全11(2¹-1)、2位全13(2²-1)、3位全17(2³-1)、4位全115(2⁴-1)……再加上数字0就是全部的单比特数。步骤2计算数字 n1 的二进制位数代码中执行n 1再用bits.Len()计算这个数的二进制有效位数示例中 n4n155的二进制是101有效位数为3这个位数代表[0,n]内的全1单比特数最多有多少位步骤3推导单比特数总个数二进制位数 全1单比特数的个数再加上数字0就是最终总数位数3 → 对应3个全1数1(1位)、3(2位)、7(3位)过滤掉超过n的数74排除剩余1、3两个全1数加上数字0总个数213和题目结果一致步骤4输出最终结果代码直接返回计算出的总数完成统计。三、复杂度分析1. 时间复杂度代码仅执行了固定次数的数学运算加法、二进制位数计算没有循环、没有遍历无论n的取值是0还是1000运算次数都不变结论时间复杂度为 O(1)常数级2. 额外空间复杂度代码只定义了几个普通变量n、result没有使用数组、切片、map等动态数据结构没有随输入规模增长而占用更多内存结论额外空间复杂度为 O(1)常数级总结解题核心利用单比特数的二进制规律不遍历直接计算完整流程计算n1的二进制位数 → 确定全1单比特数 → 加上数字0统计总数复杂度时间O(1)额外空间O(1)。Go完整代码如下packagemainimport(fmtmath/bits)funccountMonobit(nint)int{returnbits.Len(uint(n1))}funcmain(){n:4result:countMonobit(n)fmt.Println(result)}Python完整代码如下# -*-coding:utf-8-*-defcount_monobit(n:int)-int: 计算需要多少个单比特数形如 2^k - 1才能覆盖到 n 等价于计算 (n1) 的二进制位数 return(n1).bit_length()defmain():n4resultcount_monobit(n)print(result)if__name____main__:main()C完整代码如下#includeiostream#includebit#includeclimits// 如果编译器支持C20使用std::bit_widthintcountMonobit(intn){// std::bit_width返回无符号整数类型的二进制位数// 注意std::bit_width(0)返回0与bits.Len行为一致returnstd::bit_width(static_castunsignedint(n1));}intmain(){intn4;intresultcountMonobit(n);std::coutresultstd::endl;return0;}