求m位二进制数中至多包含k个1的第n个数的闭式表达式或公式

看起来你需要的是按数值升序排列的、m位二进制中1的个数不超过k的第n个数（而不是统计符合条件的数的总数），而且你已经通过例子明确了需求——比如m=4、k=2时，序列是0,1,2,3,4,5,6,8,9,10,12这样的。结合你要并行处理的场景，直接通过索引n构造目标数确实是最高效的方式，不用先生成所有数再分片。

核心思路：用组合数逐位确定二进制位 #

我们可以从最高位到最低位依次判断每一位是0还是1，核心是利用组合数计算“如果当前位设为0，剩下的位数里能容纳的符合条件的数的总数”，以此来决定当前位的取值：

• 假设现在处理第i位（对应权重2^i，从m-1到0遍历），先计算剩下的i位中，1的个数不超过当前剩余k值的数的总数：count = sum_{t=0}^min(k, i)} C(i, t)，这里C(a,b)是组合数，表示从a个元素中选b个的组合数。
• 如果n < count：说明目标数在“当前位为0”的子集里，直接把当前位设为0，继续处理下一位即可。
• 如果n ≥ count：说明目标数在“当前位为1”的子集里，把当前位设为1，然后把n减去count（因为前面count个数都属于“当前位为0”的子集），同时k减1（因为已经用掉了一个1的配额），再继续处理下一位。

用你的例子验证一下 #

拿你给出的m=4、k=2，n=7（对应序列里的第8个数，也就是8）来走一遍：

1. 初始n=7，k=2，处理第3位（对应8的权重）：
   count = C(3,0)+C(3,1)+C(3,2) = 1+3+3=7
   7≥7，所以这一位设为1，n更新为7-7=0，k更新为2-1=1
2. 处理第2位（对应4的权重）：
   count = C(2,0)+C(2,1)=1+2=3
   0<3，所以这一位设为0，n和k保持不变
3. 处理第1位（对应2的权重）：
   count = C(1,0)+C(1,1)=1+1=2
   0<2，这一位设为0，n和k不变
4. 处理第0位（对应1的权重）：
   count = C(0,0)=1
   0<1，这一位设为0
   最终得到二进制1000，也就是十进制的8，和你的例子完全匹配。

编程实现的要点 #

• 先准备一个组合数计算工具：可以写一个函数计算C(a,b)，或者预计算一张组合数表（因为m是固定的，预计算会更快），注意边界情况：C(n,0)=1，当t>n时C(n,t)=0。
• 迭代每一位，从最高位到最低位，逐步构造二进制数的每一位，最后转换成十进制即可。
• 这种方法是直接构造目标数，不需要生成前面的所有数，所以每个处理器只需要知道自己负责的n的起始和结束索引，就能独立生成对应的批次，完全适配你并行处理的需求。

备注：内容来源于stack exchange，提问作者Yair Derry