c - 使用 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 是可计算的最大值由 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，即00000000001100012，而i的当前值为16，即00000000000100002。那么对于 16 位 2 的补码算术，我们有:

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

这与众所周知的在无符号值 x 中查找最低“1”位的技术大致相似，即 x & -x，其工作原理是因为 AND 运算带有二进制补码的数字仅在结果中留下最低的“1”位。