位运算
发布于2021-02-25
上次编辑2021-02-25
| x = x & -x; // 将除最低位的 1 之外的其余位置 0
x = x & (~(x - 1)); // 同上
x = x & (x - 1); // 将最低位的 1 置 0
x = x & ~(1 << k); // 将第 k (最低位为 0) 位置 0
x = x | (1 << k); // 将第 k (最低位为 0) 位置 1
x = (x >> k) & 1; // 获取第 k (最低位为 0) 位
|
连续 1 出现的最多次数
| for (int i = 0; x; x &= (x >> 1), ++i);
|
遍历 x 的非空子集
| for (int y = x; y; --y &= x);
|
最大值/最小值
| // 若 a>=b，则 (1LL * a - b) >> 63 返回 0, ~(1LL * a - b) >> 63 返回 -1 即 0xffffffffffffffff
int max(int a, int b) { return b & ((1LL * a - b) >> 63) | a & (~(1LL * a - b) >> 63); }
int min(int a, int b) { return a & ((1LL * a - b) >> 63) | b & (~(1LL * a - b) >> 63); }
|
遍历元素个数为 N 的集合的所有子集
| for (int i = 0; i < (1 << N); ++i) {
for (int j = 0; j < N; ++j) {
if ((i >> j) & 1) {
// Code here
}
}
}
|
遍历元素个数为 N 的集合的元素个数为 K 的子集 (字典序生成) (Gosper’s hack)
| int n, k;
int x = (1 << k) - 1, c, r;
while (x < (1 << n)) {
// cout << x << '\n';
c = x & -x, r = x + c, x = (((r ^ x) >> 2) / c) | r;
}
|
例题