使用n位数生成数字(类似于生成n位值的子集)

Question

给定数字'n'和相应的二进制值.我想只使用'n'中设置的位来生成n的所有组合.

例如:如果n = 11且其二进制表示为1011,则组合为:

0000
0001
0010
0011
1000
1001
1010
1011

例2:如果n = 49且其二进制表示为11001,则组合为:

00000
00001
01000
01001
10000
10001
11000
11001

最简单的方法可能是编写一个C子程序来生成这些组合,但是,我需要一些有效的方法/算法来生成这些组合(一些位操作技术类似于bit twiddling hacks).

谢谢.

Answer 1

这是一个使用简单的比特琐事的技术的例证.它在无符号值上使用二进制算术的保证语义.

在该表达式中i = n & (i - n)的下方,所有的子表达式,i,n,(i - n)和n & (i - n)是相同的类型,unsigned int并且是由整数提升规则不受影响.在数学上,子表达式(i - n)以2 ^m为模进行计算,其中2 ^m - 1是可由a表示的最大值unsigned int.

#include <stdio.h>

int main(void)
{
    unsigned int n = 49;
    unsigned int i;

    for (i = 0; ; i = n & (i - n)) {
        printf("%u", i);
        if (i == n)
            break;
        putchar(' ');
    }
    putchar('\n');
    return 0;
}

示例步骤

假设n为49或0000000000110001 2,且当前值为i16或0000000000010000 2.那么对于16位,2的补码算法,我们有:

0000000000010000?
0000000000110001? -
----------------
1111111111011111?
0000000000110001? &
----------------
0000000000010001? (= 17)

这是隐约类似于众所周知的技术,找到一个无符号的最低值"1"比特x的x & -x,这工作,因为取与与它的两个补了一些,只保留了最低的"1"位在结果集中.