C语言 生成所有n位数字,其中位i为0

5f0d552i  于 2023-10-16  发布在  其他
关注(0)|答案(3)|浏览(105)

我需要生成所有2^(n-1)n位数,其中位i始终是0j是可能数字列表中数字的索引。下面是一个简单的表格,当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

或者在binary中:

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不会缩放,并且仅适用于上述表,而不适用于ni的任意值。
有没有人能想出一种更通用,更有效的方法来生成所有n位的数字,其中i位为0?

k2fxgqgv

k2fxgqgv1#

使用j >> i << i清除低i位,并将其添加到j以使高位加倍,有效地将它们左移一位:
t = j + (j >> i << i);

esyap4oy

esyap4oy2#

下面是一个生成这些数字的经典方法:

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

oogrdqng

oogrdqng3#

你要求的是比不起作用的东西“更简单”的东西。对我来说,最好是从真正有效的东西开始。一旦你有了它,你可以寻找改进和优化。
这里值得一提的是一个应该工作的函数(为了简单起见,省略了边界检查):

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

相关问题