解题思路

此题考查对于按位或运算的理解，以及一个处理状态压缩 $dp$ 问题时的常用技巧，子集枚举。 根据按位或运算的性质，不难发现 $a or b = a$ 当且仅当 $a$ 的二进制中 $0$ 的位置，$b$ 相对应的位置必须也是 $0$，$a$ 是 $1$ 的位置，$b$ 对应的位置可以为 $1$也可以为 $0$，首先最直观的一个想法就是暴力枚举比 $a$ 小的所有值去判断，但是这样我们会进行很多次无效的枚举，然后根据上述性质可以在枚举的过程中进行优化，接下来介绍子集枚举。

降序遍历 $m$ 的所有子集的代码(不会得到 $0$ ，对于某些题目 $0$ 可能也是合法的子集，需要特殊判断)

for (int i = m; i; i = (i - 1) & m)

证明为什么是降序遍历到所有子集

假设一个当前子集是 $i$ ，并且要访问下一个比 $i$ 小的子集，$i-1$ 代表的是，将 $i$ 的二进制中最右边的一个 $1$ 变成 $0$，并且将这个 $1$右边的所有 $0$ 全部变为 $1$(比如 $12$ 的二进制是 $1100$，$11$ 的二进制是 $1011$)，为了使$i-1$变成新的子集，需要将 $i-1$ 某些位的二进制是 $1$，在 $m$ 中相对应的位置是 $0$ 的去掉(这部操作可以通过 &m 实现)，这个操作等价于切割 $i-1$，以确定算术上可以取到的最大值，即按降序排列的 $i$ 之后的下一个子集。

遍历大小为 $n$ 的集合的每个子集的子集

for (int i = 0; i < (1 << n); ++i)
  
  for (int j = m; j; j = (j - 1) & i)

证明时间复杂度$O(3^{n})$,n为二进制中1的个数

考虑在第 $i$ 位，有三种情况：

(1)在 $m$ 中为 $0$，那么在子集 $i$ 中也为 $0$。

(2)在 $m$ 中为 $1$，在子集 $i$ 中也为 $1$。

(3)在 $m$ 中为 $1$，但是在子集中为 $0$。

总共有 $n$ 位，因此有$3^{n}$种组合。