竞赛算法(3) 位运算

简单的跳过, 从典型trick开始.

lowbit#

1
inline u32 lowbit(u32 x) {
2
    return x & (-x);
3
}

分类求缺失数#

数组中只有2种数出现次数为奇数, 其他数出现次数均为偶数, 找到出现次数为奇数的数.

设这两个数为a和b.
取异或和sum, 则显然sum = a ^ b.
sum中至少存在一个1, 我们取任意一个1. 这里方便起见取一定存在的lowbit(sum).
lowbit(sum)一定由0和1异或而成, 所以a和b在lowbit(sum)这位上必然一个为0一个为1.
我们将所有数分类成lowbit(sum)位上为0的数组arr0和为1的数组arr1, 则arr0中只有一个出现奇数次的数, arr1中只有一个出现奇数次的数. 问题转化为在数组中寻找唯一的出现次数为奇数的数. 取异或和即可.

判断2的整幂#

1
bool is2pow(u32 n) {
2
    return n == 0 ? 0 : n == lowbit(n);
3
}
4

5
// 另一种写法
6
bool is2pow(u32 n) {
7
    return n == 0 ? 0 : __builtin_popcount(n) == 1;
8
}

判断n的整幂#

1
bool is3pow(u32 n) {
2
    return n == 0 ? 0 : (1162261467 % n == 0);
3
    // 其中1162261467是int范围内最大的3的整数次幂. 其它数字同理.
4
}

将最高位后的所有位填充为1#

1
inline u32 highbit(u32 n) {
2
    if (n == 0) return 0;
3
    return 1 << (31 - __builtin_clz(n));
4
}
5

6
inline u32 fillbit(u32 n) {
7
    if (n == 0) return 0;
8
    u32 m = highbit(n);
9
    return (m - 1) + m;
10
}
11

12
// 应用: 找到大于等于n的最小2整幂
13
u32 find2powgt(u32 n) {
14
    // 要求n <= 2^31
15
    return n == 0 ? 1 : fillbit(n - 1) + 1;
16
}

求[l, r]所有数字按位与的结果#

1
u32 andsum(u32 l, u32 r) {
2
    // [l, r]
3
    while (r > l) {
4
        r -= lowbit(r);
5
    }
6
    return r;
7
}

二进制低位与高位翻转#

神人代码, 但很快. 状压中可能会用上.

1
inline u32 bitrvs(u32 n) {
2
    n = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1);
3
    n = ((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2);
4
    n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4);
5
    n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8);
6
    n = (n >> 16) | (n << 16);
7
    return n;
8
}

二进制中1的数目#

1
// 直接使用内置函数
2
int __builtin_popcount(unsigned int x);
3
int __builtin_popcountll(unsigned long long x);
4
// 注意参数类型(虽然会自动转换).

子集枚举#

设s是用二进制表示的集合. 以 $O(2^{popcnt(n)})$ 的复杂度枚举s的子集.

1
for (int i = s; ; i = (i - 1) & s) {
2
    // ...
3
    if (i == 0) {
4
        break;
5
        // 处理0, 如果无需处理0的话就移到开头或for语句中.
6
    }
7
}

遍历所有子集的子集#

可以在 $O(3^n)$ 的时间内遍历大小为n的集合s的子集的所有子集.

1
for (int m = 0; m < (1 << n); m++) {
2
    for (int i = m; i > 0; i = (i - 1) & m) {
3
        // ...
4
    }
5
}

std::bitset#

相当于超长二进制整数.

1
bitset<N> b;
2
b[i]       // 访问第 i 位 (0 或 1)
3
b.set(i);  // 将第 i 位设为 1
4
b.reset(i);// 将第 i 位设为 0
5
b.flip(i); // 将第 i 位取反 (0变1, 1变0)
6

7
b.set();   // 全部设为 1
8
b.reset(); // 全部设为 0
9
b.flip();  // 全部取反
10

11
b.count(); // 返回 1 的个数
12
b.any();   // 是否存在 1
13
b.none();  // 是否全为 0
14

15
bitset<N> x, y, z;
16

17
z = x & y; // 交集
18
z = x | y; // 并集
19
z = x ^ y; // 异或
20
z = ~x;    // 取反
21
z = x << 2; // 整体左移 2 位
22

23
b._Find_first(); // 返回第一个(最低位)1的下标
24
b._Find_next(idx);// 返回高于idx的位中, 第一个(最低位)1的下标

数据结构: 位图#

除了std::bitset外还可以手写bitset, 好处是可以实现范围填充, 以进行时间上的优化(详见P5539 【XR-3】Unknown Mother-Goose).

一般应具有以下操作.

1
inline int div64(int n) {
2
    return n >> 6;
3
}
4
inline int mul64(int n) {
5
    return n << 6;
6
}
7
u64 bs[div64(N) + 1];
8
void initbitset(int n);
9
void set(int p);
10
void clear(int p);
11
void flip(int p);
12
bool check(int p);  // 查询p位的状态.
13

14
// 扩展操作
15
void setall();
16
void clearall();
17
void flipall();
18
void allset();
19
void allclear();
20
int popcnt();
21
void leftshift();
22
void rightshift();
23
void biand(bs a, bs b);    // 需要先封装
24
void bior(bs a, bs b);
25
void bixor(bs a, bs b);

一些其他的内置函数#

1
int __builtin_clz(unsigned int x); // 求前导0
2
int __builtin_clzll(unsigned long long x);
3

4
int __builtin_ctz(unsigned int x); // 求后导0
5
int __builtin_ctzll(unsigned long long x);

位运算trick合集#

从popcount角度看进位: 每个进位均使popcount - 1.
求某个集合的子集的异或和: 先按位枚举, 对于每一位来说, 我们把集合分成两类: A集合在这一位上是0, B集合在这一位上是1. 所以只有在B集合中取奇数个, A集合中任意取, 这一位才能是1. 最终这一位是1的子集将会有 $2^{n - 1}$ 个.