二进制子集枚举

定义

设 x 为一正整数, 其二进制子集定义为(通过举例来定义):

• 如 x 为 4 位的二进制数 1010, 那么它的子集为{1010,1000,0010} 4 个.

通过上述举例, 显然有结论, 一个数 x 的二进制子集有$2^n$个, 其中 n 为 x 的二进制表示中 1 的个数.

算法

下面给出计算出 x 的所有二进制子集的算法.

typescript

// O(2^n)/O(1)
function binarySubsetOf(x: number) {
  console.log(x); // x本身是一个
  for (let m = x; m != 0; m = (m - 1) & x) {
    console.log(m); // 输出
  }
  console.log(m); // 0也是一个
}

原理

以 1010 模拟一下:

• 1010 本身记一个
• 1010 - 1 = 1001 & 1010 = 1000
• 1000 - 1 = 0111 & 1010 = 0010
• 0010 - 1 = 0001 & 1010 = 0000