如何快速实现含k个置位比特、长度为b的比特序列与索引双向映射？

这是个非常经典的组合编码问题，完全可以实现无需预生成所有序列的双向快速映射，核心是利用组合数的性质直接计算索引和序列，不用遍历前置或后置项。下面我详细拆解两种方向的实现逻辑：

核心思路 #

从最高位到最低位依次判断每一位是否为1：对于当前剩余的m位（还没确定的位数），如果我们还需要选t个1，计算组合数C(m-1, t)——这个数代表「当前位为0时，后面m-1位能凑出t个1的序列总数」。如果给定的索引小于这个数，说明当前位是0（因为所有当前位为0的序列都排在前面）；如果索引大于等于这个数，说明当前位是1，同时把索引减去C(m-1, t)（跳过所有当前位为0的序列），并把t减1（已经选了一个1）。重复这个过程直到所有位确定。

示例验证（b=4, k=2, 索引4） #

初始状态：总位数m=4，需要选t=2个1，索引idx=4

1. 第一位（最高位）：计算C(3,2)=3，因为4 >=3，所以第一位是1，idx=4-3=1，t=1，m=3
2. 第二位：计算C(2,1)=2，因为1 <2，所以第二位是0，m=2
3. 第三位：计算C(1,1)=1，因为1 >=1，所以第三位是1，idx=1-1=0，t=0，m=1
4. 第四位：t=0，直接设为0
   最终得到序列：1010，和你的例子完全匹配。

核心思路 #

从最高位到最低位遍历每一位：每当遇到一个1，就累加「当前位为0时，后面剩余位数能凑出剩余需要选的1的数量-1个1的组合数」——这些序列都排在当前序列的前面。每遇到一个1，就把剩余需要选的1的数量减1，直到遍历完所有位，累加的结果就是索引。

示例验证（序列1010, b=4, k=2） #

初始状态：剩余需要选的t=2个1，索引idx=0

1. 第一位是1：计算「当前位为0时，后面3位选2个1的组合数」C(3,2)=3，idx +=3（此时idx=3），t=1
2. 第二位是0：跳过，不做处理
3. 第三位是1：计算「当前位为0时，后面1位选1个1的组合数」C(1,1)=1，idx +=1（此时idx=4），t=0
4. 第四位是0：跳过
   最终得到索引：4，完全正确。

为了快速计算组合数C(n,k)，建议提前预处理一个二维数组（或用动态规划递推），边界条件为：

• C(n,0)=1，C(n,n)=1
• C(n,k)=C(n-1,k-1)+C(n-1,k)（当0<k<n时）
• C(n,k)=0（当k>n时）

如果b的范围不大（比如≤60），也可以用公式直接计算（注意用64位整数避免溢出）：C(n,k) = n!/(k!*(n-k)!)，但递推的方式更高效且不易溢出。

这种方法的时间复杂度是O(b)，不管C(b,k)多大（哪怕b=60, k=30，C(60,30)是1e17量级），都只需要遍历b次就能完成双向转换，比预生成所有序列的O(C(b,k))方法高效几个数量级，完全满足你的需求。

内容的提问来源于stack exchange，提问作者Eduard