生成所有n位数字，其中i位为0

Question

我需要生成所有

2^(n-1)

n

位数字，其中位

i

始终为

0

且

j

是可能数字列表中数字的索引。这是一个简单的表格，说明当

i

从 0 到 2 变化且

n

为 3 时，因此

j

从 0 到 3 变化。结果是一个 3 位数字，因此

n

将为 3，并且可能的数字是 4。

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 // Note the LSB (1s place) bit is never set in this line
01  000 001 100 101 // The 2s place bit is not set in this line
10  000 001 010 011 // The 4s place bit is not set in this line

这是我能想到的最好的：

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

但是，单独检查

i

并进行比较并不能扩展，并且仅适用于上述表格，不适用于

n

或

i

的任意值。

任何人都可以想到一种更通用、更有效的方法来生成所有

n

位数字，其中第

i

位为 0？

Answer 1

你要求的东西比不起作用的东西“更简单”。对我来说，最好从获得真正有效的东西开始。一旦掌握了这些，您就可以寻求改进和优化。

这里值得的是一个应该可以工作的函数（为了简单起见，省略了边界检查）：

unsigned f(unsigned j, unsigned i)
{
    unsigned mlow = (1 << i) - 1;
    unsigned mhigh = ~mlow << 1;
    return (2*j & mhigh) | (j & mlow);
}

查看实际效果：

int main(void) {
    unsigned bits = 5;
    unsigned combs = 1 << (bits - 1);
    
    for (unsigned i = 0; i < bits; ++i)
    {
        for (unsigned j = 0; j < combs; ++j)
        {
            printf("%2u ", f(j, i));
        }
        puts("");
    }
    return 0;
}

输出：

 0  2  4  6  8 10 12 14 16 18 20 22 24 26 28 30 
 0  1  4  5  8  9 12 13 16 17 20 21 24 25 28 29 
 0  1  2  3  8  9 10 11 16 17 18 19 24 25 26 27 
 0  1  2  3  4  5  6  7 16 17 18 19 20 21 22 23 
 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 

Answer 2

这是生成这些数字的经典方法：

// make mask of the bits that can change
uint32_t mask = setNlowestBits(n) & ~(UINT32_C(1) << i);
uint32_t x = 0;
do {
    // use x
    ...
    // masked increment
    x = (x - mask) & mask;
} while (x != 0);

按照你想要的方式实现

setNlowestBits

，互联网上有各种实现方式。

mask

在每个允许更改的位上都有一个 1，

x - mask

就像从整数中减去 -1，但有一些“漏洞”。任何借用都会通过“孔”传播，因为“孔”中有零。然后

& mask

重置“孔”中由通过它的借位设置的任何位。在这种情况下，只有一个孔，但此技术也适用于更多孔。

使用x86平台的现代指令，您可以直接将

j

一步转换为所需的数字：

_pdep_u32(j, mask)

其中

mask

与之前相同，或者如果您愿意，只需

~(UINT32_C(1) << i)

。

Answer 3

使用

j >> i << i

清除低

i

位并将其添加到

j

以使高位加倍，有效地将它们左移一位：

t = j + (j >> i << i);