如何用位运算生成子序列？以数组A=[1,2,3,4]为例解析逻辑

这段代码的核心思路是用二进制掩码来对应数组的每一个非空子序列，咱们一步步拆解它的工作原理：

1. 外层循环：遍历所有可能的子序列掩码 #

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

这里的counter从1开始，到2^n - 1结束（因为counter < 2^n）。为什么是这个范围？

• 对于长度为n的数组，每个元素有两种状态：被包含在子序列里或不被包含。总共有2^n种组合，减去全不选的情况（对应counter=0），正好是2^n - 1个非空子序列，和题目要求一致。
• 每个counter的二进制形式，就是一个n位的掩码，每一位对应数组中一个元素的选择状态。

2. 内层循环：检查掩码的每一位 #

for (int j = 0; j < n; j++) {
    if (counter & (1<<j)) cout << arr[j] << " ";
}

内层循环遍历数组的每一个索引j，核心就是counter & (1<<j)这个位运算，咱们重点解释它：

先搞懂1<<j是什么 #

1<<j是左移运算：把数字1的二进制形式向左移动j位，得到的结果是一个只有第j位（从0开始数）为1，其余位都是0的二进制数。比如：

• 当j=0时，1<<0 = 1（二进制0001）
• 当j=1时，1<<1 = 2（二进制0010）
• 当j=2时，1<<2 = 4（二进制0100）
• 当j=3时，1<<3 = 8（二进制1000）

再看counter & (1<<j)的作用 #

&是按位与运算：两个二进制数对应位都为1时，结果的该位才是1，否则为0。

• 如果counter的第j位是1，那么counter & (1<<j)的结果就是1<<j（非0值，在C++中会被判定为true），这说明我们要把数组的第j个元素加入当前子序列。
• 如果counter的第j位是0，那么counter & (1<<j)的结果就是0（判定为false），跳过该元素。

举个实际例子：假设数组A=[1,2,3,4]，counter=5（二进制0101）：

• j=0：5 & 1 = 1（非0），输出1
• j=1：5 & 2 = 0，跳过
• j=2：5 & 4 = 4（非0），输出3
• j=3：5 & 8 = 0，跳过
  最终输出的子序列就是1 3，正好对应掩码0101标记的元素。

3. 整体流程总结 #

每一个counter对应一个唯一的二进制掩码，掩码的每一位决定是否包含数组的对应元素。通过遍历所有非零掩码（从1到2^n-1），再逐个检查掩码的每一位，就能生成所有的非空子序列。

内容的提问来源于stack exchange，提问作者miltonbhowmick