位运算
主要记录一下平时遇到的一些使用位运算处理问题的小技巧,也许会不断更新把。。。
二进制枚举子集
对于用二进制表示的集合 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,而是每一位对应的数组值,这样就可以快速得到每个集合对应的和。不过当时并没有想到这点。