求通用高效方法：生成第j个i位固定为0的n位二进制数

需求是生成共 (2^{n-1}) 个第i位固定为0的n位二进制数，取其中按升序排列的第j个数。以n=3、i从0到2为例，对应结果如下：

十进制结果表 #

j   0 1 2 3
i
0   0 2 4 6
1   0 1 4 5
2   0 1 2 3

二进制形式 #

j    00  01  10  11
i
00  000 010 100 110 // 此行使最低位（1s位）始终为0
01  000 001 100 101 // 此行使中间位（2s位）始终为0
10  000 001 010 011 // 此行使最高位（4s位）始终为0

目前仅能写出针对该示例的硬编码实现：

unsigned result = (j&1)<<(i==0)|(j&2)<<(i!=2);

但该方法无法扩展至任意n或i值，寻求通用且高效的实现方式。

核心思路是把j的二进制位插入到结果的二进制位中，跳过第i位：通过拆分j的高低位，再移位合并，确保第i位固定为0，同时对应升序排列的结果。

代码实现 #

unsigned get_result(unsigned n, unsigned i, unsigned j) {
    unsigned high = j >> i;          // 取j中高于等于第i位的部分
    unsigned low = j & ((1U << i) - 1);  // 取j中低于第i位的部分
    return (high << (i + 1)) | low;  // 移位合并，跳过第i位
}

逻辑解释 #

1. 拆分j的二进制位：
   • high = j >> i：将j右移i位，得到的是j中从第i位开始的高位部分，这部分对应结果中高于第i位的位置
   • low = j & ((1U << i) - 1)：通过掩码保留j的前i位（低于第i位的部分），这部分直接对应结果中低于第i位的位置
2. 合并生成结果：
   • high << (i + 1)：把high部分左移i+1位，直接跳过结果中第i位的位置（确保该位为0）
   • 和low做或运算后，最终结果的第i位自然为0，其余位严格按照j的二进制顺序填充，正好对应升序排列的第j个数

示例验证（n=3, i=1） #

• j=1（二进制01）：high=1>>1=0，low=1&1=1 → (0<<2)|1=1（二进制001），与示例一致
• j=2（二进制10）：high=2>>1=1，low=2&1=0 → (1<<2)|0=4（二进制100），与示例一致

效率说明 #

该实现仅使用移位、与、或三种位运算，无分支判断，时间复杂度为O(1)，可以无缝扩展到任意合法的n和i值，性能拉满。

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