位运算
主要记录一下平时遇到的一些使用位运算处理问题的小技巧，也许会不断更新把。。。
二进制枚举子集
对于用二进制表示的集合 x，如下方式可以枚举其每一个子集
for (int i = x; i; i = ((i - 1) & x)) {
//TODO
}Gosper's Hack
这个算法可以快速枚举一个 n 元集合中的 k 元子集
比如 n = 7, k = 4，那么最小的一个二进制数就是 0001111，最大的一个二进制数是1111000。
那么我们需要枚举的就是 0001111 ~ 1111000 之间全部的 1 的个数为 4 的二进制数。
所以，我们需要做的是，从一个二进制数得到下一个数呢。比如上面的 0001111 -> 0010111 -> 0011011。
而1的个数不能变，很容易想到，想要一个数变大，那么就把二进制位中的1，往左侧与更高位的0进行交换即可。那么如何保证变大的幅度最小呢？那就是在尽可能低的位进行这样的交换，总结下来就是如下两句话：
- 从右往左，找到第一个
01，交换这两个位 - 把第一个
01右侧的全部1，全部移动到最右侧
实现
首先是第一步：找到 01
int low_bits(int n) {
return n & -n;
}这个操作可以求得一个二进制数的从高位到低位的最后一个 1
这个 low_bits 可以帮助我们找到第一个 01，并交换他们。比如 x = 10110，其 lb = 00010，我们计算 x + lb = 11000。由于 lb 是最后一个 1，加上 lb 之后就能不断进位，直到把第一个 01 变为 10
接下来需要求解一下 01 右侧多少个 1，并且要把这些 1 全部放在最右侧。
由于 lb 是 x 中最后一个 1，且 x + lb 后，会一直进位到遇到第一个 01。那么第一个 01 右侧的，就是 lb 最后一位 1 所在的位置，到第一个 01 的 0 所在的位置，中间的位数。
由于 x + lb 会从最后一个 1，一直进位到第一个 0，那么 x 和 x + lb，在右侧第一个 1，和后续第一个 0 之间，都是相反数，而其他的位都相同，那么我们可以做一下异或，将 x 中右侧连续的 1 提取出来
x = 011001110
lb = 000000010
x + lb = 011010000
x ^ (x + lb) = 000011110
x ^ (x + lb) / lb = 000001111
x ^ (x + lb) / lb >> 2 = 000000011上面就是一个例子，提取的结果就是 000011110，注意这里因为 01 和 10 异或的原因，1 的数量多了两个，后续要移除两个。
这个数里所有的 1 还没有被移动到右侧，这里只需要除以 lb 即可，因为 lb 记录的就是第一个 1 的位置
最终，我们通过计算 x + lb 得到左侧的部分，通过 x ^ (x + lb) / lb >> 2 得到右侧部分，拼接起来即得到下一个数。
统计集合元素状态
这个说法其实有点模糊，因为我也不知道应该怎么描述，直接来看题吧
给你一个整数
n，对于0 <= i <= n中的每个i，计算其二进制表示中1的个数 ，返回一个长度为n + 1的数组ans作为答案。
对于这道题来说，最简单的方法就是对每个 i 使用 i&(i-1)的方法统计数量。
如果想要达到 O(n) 的时间复杂度，就需要如下的方法
class Solution {
public:
vector<int> countBits(int n) {
vector<int> bits(n + 1);
int highBit = 0;
for (int i = 1; i <= n; i++) {
if ((i & (i - 1)) == 0) {
highBit = i;
}
bits[i] = bits[i - highBit] + 1;
}
return bits;
}
};对于每个数来说，我们可以在遍历过程中确定当前的最高位是多少，然后利用动态规划的思想，借助之前的结果快速计算。
其实思路还是很简单的，为什么我要把它写下来呢？
因为这让我想到了之前碰到的一道题 1655. 分配重复整数 ，其中也用到了这个思路，只是这时候的状态不是每一位是否为1，而是每一位对应的数组值，这样就可以快速得到每个集合对应的和。不过当时并没有想到这点。