2026-05-29：二进制中恰好K个1的第N小整数。用go语言，给定两个正整数 n 和 k，要求你找到这样一个数：在它的二进制表示中，恰好有 k 个比特位为 1。把所有满足条件的正整数按大小从小到大

2026-05-29：二进制中恰好K个1的第N小整数。用go语言，给定两个正整数 n 和 k，要求你找到这样一个数：在它的二进制表示中，恰好有 k 个比特位为 1。把所有满足条件的正整数按大小从小到大排序，返回其中第 n 个数。题目保证这个答案一定小于 2⁵⁰。

1 <= n <= 2⁵⁰。

1 <= k <= 50。

答案严格小于 2⁵⁰。

输入： n = 4, k = 2。

输出： 9。

解释：

二进制表示中恰好包含 k = 2 个 1 的前 4 个正整数分别是：

3 = 11₂。

5 = 101₂。

6 = 110₂。

9 = 1001₂。

题目来自力扣3821。

解题过程详解

一、前置准备：预处理组合数

这是算法的初始化步骤，在程序启动时自动执行，核心作用是提前计算好所有需要用到的组合数，为后续快速判断做准备。

1. 组合数的含义：C(i, j)表示从 i 个位置中选 j 个位置放1的总方案数，这正好对应「二进制数有j个1」的数量。
2. 预处理范围：因为答案严格小于 2⁵⁰，所以我们只需要计算到最高位50位的所有组合数（i 最大取49，j 最大取50）。
3. 计算规则：用动态规划递推
   • 边界：任何数选0个位置放1，都只有1种方案（全0）；
   • 递推：C(i,j) = C(i-1,j-1) + C(i-1,j)（选当前位为1 + 选当前位为0）。
4. 作用：后续每一步判断，都能直接查表得到方案数，不用重复计算。

二、核心逻辑：逐位构造答案（从高位到低位）

算法的核心思想：从最高位（第49位）到最低位（第0位），一位一位确定当前二进制位是0还是1，最终拼出第n小的数。

我们的目标：找二进制恰好2个1、从小到大排序后的第4个数。
已知满足条件的数排序：3(11)、5(101)、6(110)、9(1001)。

初始状态

• 当前待确定的位：最高位（第49位）
• 剩余需要填的1的个数：k=2
• 目标排名：n=4
• 答案初始值：0（二进制全0）

步骤1：遍历高位（第49位 ~ 第4位）

这些位的位置非常高，我们计算：如果当前位填0，剩余位置能填出多少个「恰好2个1」的数。
公式：C(剩余位数, 剩余1的个数)

• 剩余位数 = 当前位的下标
• 剩余1的个数 = 2

计算发现：这些高位填0时，能生成的方案数远大于4。
这意味着：第4个数一定不包含这些高位，所以所有高位全部填0。

• 状态不变：k=2，n=4，ans=0

步骤2：处理第3位（二进制 8 的位置，值为8）

1. 计算：当前位填0时，剩余3个位置选2个1的方案数 →C(3,2)=3；
2. 比较：目标排名 n=4 ＞ 方案数3；
3. 判断：第4个数不在当前位填0的范围内，当前位必须填1；
4. 更新状态：
   • 排名减去当前位填0的方案数：n=4-3=1（剩下只需要找新排名第1的数）；
   • 答案加上当前位的值：ans=0+8=8；
   • 剩余需要填的1的个数减1：k=2-1=1。

步骤3：处理第2位（二进制 4 的位置，值为4）

1. 计算：当前位填0时，剩余2个位置选1个1的方案数 →C(2,1)=2；
2. 比较：目标排名 n=1 ＜= 方案数2；
3. 判断：第1个数在当前位填0的范围内，当前位填0；
4. 状态不变：k=1，n=1，ans=8。

步骤4：处理第1位（二进制 2 的位置，值为2）

1. 计算：当前位填0时，剩余1个位置选1个1的方案数 →C(1,1)=1；
2. 比较：目标排名 n=1 ＜= 方案数1；
3. 判断：第1个数在当前位填0的范围内，当前位填0；
4. 状态不变：k=1，n=1，ans=8。

步骤5：处理第0位（二进制 1 的位置，值为1）

1. 剩余需要填的1的个数 k=1，必须填1才能满足条件；
2. 更新答案：ans=8+1=9；
3. 剩余1的个数减1：k=0，结束遍历。

三、最终结果

最终构造的数是9，与题目示例输出一致。

时间复杂度 & 额外空间复杂度

1. 总时间复杂度

分为两部分：

• 初始化组合数：双重循环遍历 mx×mx 次（mx=50），时间复杂度为O(mx²)；
• 核心构造逻辑：从高位到低位遍历50位，单次遍历仅做查表和判断，时间复杂度为O(mx)。

mx 是固定常数50，因此总时间复杂度为 O(1)（常数级时间）。

2. 总额外空间复杂度

我们只开辟了一个固定大小的二维数组comb[mx][mx+1]存储组合数，mx=50 是固定常数，没有其他动态开辟的空间。
因此总额外空间复杂度为 O(1)（常数级空间）。

总结

1. 整体流程：预处理组合数 → 从高位到低位逐位确定二进制位（0/1） → 构造出答案；
2. 核心判断：用组合数计算当前位填0的方案数，对比排名决定填0还是1；
3. 复杂度：时间和空间都是常数级 O(1)，效率极高，完全适配题目数据范围。

Go完整代码如下：

packagemainimport("fmt")constmx=50varcomb[mx][mx+1]int64funcinit(){// 预处理组合数fori:=rangecomb{comb[i][0]=1forj:=1;j<=i;j++{comb[i][j]=comb[i-1][j-1]+comb[i-1][j]}}}funcnthSmallest(nint64,kint)(ansint64){fori:=mx-1;k>0;i--{c:=comb[i][k]// 第 i 位填 0 的方案数ifn>c{// n 比较大，第 i 位必须填 1n-=c ans|=1<<i k--// 维护剩余的 1 的个数}}return}funcmain(){n:=int64(4)k:=2result:=nthSmallest(n,k)fmt.Println(result)}

Python完整代码如下：

# -*-coding:utf-8-*-mx=50# 预处理组合数comb=[[0]*(mx+1)for_inrange(mx)]foriinrange(mx):comb[i][0]=1forjinrange(1,i+1):comb[i][j]=comb[i-1][j-1]+comb[i-1][j]defnth_smallest(n:int,k:int)->int:""" 找到第 n 个恰好包含 k 个 1 的二进制数（从小到大） 返回对应的整数值 """ans=0i=mx-1whilek>0andi>=0:c=comb[i][k]# 第 i 位填 0 的方案数ifn>c:# n 比较大，第 i 位必须填 1n-=c ans|=1<<i k-=1# 维护剩余的 1 的个数i-=1returnansif__name__=="__main__":n=4k=2result=nth_smallest(n,k)print(result)

C++完整代码如下：

#include<iostream>#include<cstdint>constintmx=50;int64_tcomb[mx][mx+1];voidinit_comb(){for(inti=0;i<mx;++i){comb[i][0]=1;for(intj=1;j<=i;++j){comb[i][j]=comb[i-1][j-1]+comb[i-1][j];}}}int64_tnthSmallest(int64_tn,intk){int64_tans=0;for(inti=mx-1;k>0;--i){int64_tc=comb[i][k];// 在第 i 位填 0 的方案数if(n>c){// n 比较大，第 i 位必须填 1n-=c;ans|=(1LL<<i);--k;// 剩余 1 的个数减 1}}returnans;}intmain(){init_comb();int64_tn=4;intk=2;int64_tresult=nthSmallest(n,k);std::cout<<result<<std::endl;return0;}