JavaScript生成集合幂集：位运算筛选元素的逻辑解析

核心逻辑一句话讲透：用整数的二进制每一位，对应数组元素是否出现在子集中，而if(i & Math.pow(2, j))就是判断当前位是否为1的关键。

1. 幂集的数量对应关系 #

对于长度为n的数组，幂集包含2ⁿ个集合（包括空集）。代码外层循环i从1到2ⁿ-1，加上一开始push的空数组，正好覆盖所有2ⁿ个子集。

2. 二进制位与元素的对应 #

每个整数i的二进制表示，恰好可以标记子集的构成：

• 二进制的每一位（从右往左数，第0位、第1位…第n-1位）对应数组的第0个、第1个…第n-1个元素。
• 某一位是1，就表示对应的元素要加入当前子集；是0则不加入。

以数组[1,2,3]（长度3）为例，i的取值和对应关系：

• i=1 → 二进制001 → 第0位是1 → 子集[1]
• i=2 → 二进制010 → 第1位是1 → 子集[2]
• i=3 → 二进制011 → 第0、1位是1 → 子集[1,2]
• i=4 → 二进制100 → 第2位是1 → 子集[3]
• …以此类推

3. Math.pow(2, j)的作用 #

Math.pow(2, j)计算的是2的j次方，对应的二进制数是只有第j位为1，其余位都是0的数：

• j=0 → 2⁰=1 → 二进制001
• j=1 → 2¹=2 → 二进制010
• j=2 → 2²=4 → 二进制100

4. 按位与运算的判断逻辑 #

按位与&的规则是：只有当两个数的对应位都是1时，结果的该位才是1，否则为0。

所以i & Math.pow(2, j)的结果：

• 如果不为0，说明i的二进制第j位是1 → 对应数组的第j个元素要加入子集
• 如果为0，说明i的二进制第j位是0 → 不加入该元素

举个具体例子：i=5（二进制101），j=0时，5 & 1 = 1≠0，加入array[0]；j=1时，5 & 2 = 0，不加入；j=2时，5 &4=4≠0，加入array[2]，得到子集[1,3]，正好对应二进制第0和第2位为1的情况。

补充：更高效的写法 #

原代码用Math.pow(2,j)，其实可以用位运算1 << j代替——左移一位等价于乘以2，1<<j就是2的j次方，计算效率更高，逻辑完全一致。修改后的判断条件是：

if(i & (1 << j))

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