生成所有第i位为0的n位数字

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

这是我能想到的最好的办法，除了简单地硬编码所有可能性：

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

但是，单独检查

i

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

n

或

i

的任意值。

任何人都可以想到一种更通用、更有效的方法来生成所有内容，特别是第

j

位数字，其中第

n

位为 0？

Answer 1

i

清除低

j >> i << i

位并将其添加到

i

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

j

Answer 2

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

按照你想要的方式实现

// 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

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

mask

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

x - mask

重置“孔”中由通过它的借位设置的任何位。在这种情况下，只有一个孔，但此技术也适用于更多孔。使用x86平台的现代指令，您可以直接将

& mask

一步转换为所需的数字：

j

其中 

_pdep_u32(j, mask)

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

mask

。

Answer 3

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

~(UINT32_C(1) << i)

查看实际效果：

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;
}