使用按位运算生成子序列的逻辑是什么？

Question

我有一个数组，A=[1,2,3,4]（其中 n=4）。我想从这个数组生成子序列。子序列数为 (2^n -1)

运行从计数器 0001 到 1111

for (int counter = 1; counter < 2^n; counter++)
{
    for (int j = 0; j < n; j++)
    {

检查计数器中的第 j 位是否已设置。如果设置则打印 arr[]

中的第 j 个元素

        if (counter & (1<<j))
            cout << arr[j] << " ";
    }
    cout << endl;
}
}

谁能解释一下？它是如何工作的 " counter & (1<

Answer 1

逻辑是这样的。假设，就像您在示例中所说的那样，您有 n = 4，并且为了避免混淆，假设数组是 A = [5, 7, 8, 9]。然后你想要所有可能的序列包含来自原始数组的一些元素（至少一个）。所以你想要一个只包含第一个的序列，一个包含第一个和第二个，第一个和第三个等等的序列。每个打印的序列可能包含也可能不包含数组中的每个元素。所以你可以把它看成这样：

| 5 | 7 | 8 | 9 |    Sequence
-----------------    --------
| 1 | 0 | 0 | 0 | -> 5
| 1 | 1 | 0 | 0 | -> 5 7
| 1 | 0 | 1 | 0 | -> 5 8
...

即每个序列可以表示为一个位列表，每个位表示是否包含数组的每个成员。

在此循环中：

for (int counter = 1; counter < 2^n; counter++)

程序从 1 迭代到 2^n - 1，在本例中为 15。因此，您为 counter 获得的值是：

Dec  Binary
---  ------
  1    0001
  2    0010
  3    0011
  4    0100
  5    0101
  6    0110
  7    0111
  8    1000
  9    1001
 10    1010
 11    1011
 12    1100
 13    1101
 14    1110
 15    1111

如果你仔细观察，你会发现我们有所有可能的由 0 和 1 组成的四个元素的二进制序列（除了 0000，它是空序列，我们不感兴趣）。在这个循环中：

for (int j = 0; j < n; j++)

程序只是遍历 counter 的每一位，从 0（最右边）到 n - 1，每当它找到 1 时，它就会输出相应的数组元素。条件：

if (counter & (1<<j))

简单地计算数字 1<<j，即 1 加上其右侧的 j 个零（因此，例如，对于 j = 0 它将是 1 而对于 j = 2 它将是 100) 然后是按位和操作，所以它基本上是 "filters" 第 j 位（例如 1101 & 100 = 0100)，如果结果不为零，则表示有一个，因此必须打印 arr[j]。

显然，该函数的问题在于它受限于变量 counter 可以容纳的位数。这取决于它声明的类型和您的 architecture/compiler，但通常它是 32 或 64。

使用按位运算生成子序列的逻辑是什么？

What is the logic to use bitwise operation in generating subsequences?

c++

arrays

logic

subsequence