python/TangDou/AcWing/StateCompression/529_Prepare.cpp

#include <bits/stdc++.h>
using namespace std;

/*
二进制数的子集数量计算
子集指的是在原二进制数中1的选择，假设对应的二进制数中有数字1共n个，那么最少选择1个，最多选择n-1个，请找出所有的这样的二进制数子集。
比如二进制数13=(1101)b，有3个位置存在数字1，
那么：
包含1个1的：1000,0100,0001
包含2个1的：1100,1001,0101
共6个
*/

// 输出十进制对应的二进制数(模板)
void print(int n) {
    printf("%2d:", n);
    // 输出4个数位的二进制数
    for (int i = 3; i >= 0; i--) // 由高到低位
        printf("%d", n >> i & 1);
    puts("");
}

/*
输出n的所有二进制子集
方法1：逻辑清晰，但性能差

理解一下：
(1) i=n-1:显然，子集不包含自身，也就是最大是比自己小1的才可能是第一个最大子集
(2) for (int i = n - 1; i; i--),从可能的最大子集开始，一个个减少，当然可以遍历到每个可能的子集
(3) if ((i & n) == i)  这个位运算，就是通过数位上数字1的与运算，只有超集与之相与，才能保证得到自身，挺好理解
*/
void sub1(int n) {
    for (int i = n - 1; i; i--)
        if ((i & n) == i) print(i);
}

/*
方法2：优化
*/
void sub2(int n) {
    for (int i = n - 1; i; i = (i - 1) & n)
        print(i);
}

int main() {
    int st = 13; // 1101
    sub1(st);
    printf("==================================\n");
    sub2(st);
    return 0;
}