《算法竞赛进阶指南》0x01 位运算

Bit Twiddling Hacks

位运算基础概念

基本的位运算共 6 种，分别为按位与、按位或、按位异或、按位取反、左移和右移

时才为

或 | 只要两个对应位有一个

时就为

异或 ^ 只有两个对应位不同时才为

取反 ~ 对二进制表示的每一位取反（有符号数的符号位也会取反） 左移 << 对二进制表示向左移动

位所得的值 右移 >> 对二进制表示向右移动

位所得的值

运算符优先级

二进制常用操作

位运算的应用

基本分类：

1. 高效地进行某些运算，代替其他低效的方式
2. 表示集合（常用于 状态压缩DP）
3. 题目本来就要求进行位运算

2 的幂次相关

将一个数乘（除） 2 的非负整数次幂

向下取整，而非向零取整

int mulPowerOfTwo(int n, int m) // 计算 n*(2^m)
{
  return n << m;
}
int divPowerOfTwo(int n, int m) // 计算 n/(2^m)
{
  return n >> m;
}

判断一个数是不是 2 的非负整数次幂

二进制表示中只有一位 1

bool isPowerOfTwo(int n)
{
    return n > 0 && (n & (n - 1)) == 0;
}

对 2 的非负整数次幂取模

保留那一位以内的所有二进制

int modPowerOfTwo(int x, int mod)
{
    return x & (mod - 1);
}

模拟集合操作

a & b 并集

a | b 补集

~a 差集

a & (~b) 对称差

a ^ b

子集遍历

时间复杂度：

而遍历一个集合所有子集的子集，时间复杂度为

（每个元素只有三中状态）

// 遍历 u 的非空子集
for (int s = u; s; s = (s - 1) & u)
{
  // s 是 u 的一个非空子集
}

成对变换

为奇数时，

为偶数时，

因此，“0与1”、“2与3”、“4与5”、... 关于

是成对变换的

常用于 图论 中，无向图 用 链式前向星 存图时，找 反向边

lowbit 运算

获得一个二进制表示数的最低位是 1 的位:

lowbit运算 可以找出整数二进制表示下的所有是 1 的位

lowbit运算 也是 树状数组 实现中的一个基本运算

int lowbit(int u)
{
    return u & -u;
}

习题

a^b

题目描述

求

的

次方对

取模的值。

输入格式

三个整数

,

,

,在同一行用空格隔开。

输出格式

输出一个整数，表示

的值。

数据范围

输入样例：

3 2 7

输出样例：

2

解析

快速幂模板

时间复杂度：

int power(int a, int b, int p)
{
    int res = 1 % p;
    for (; b; b >>= 1)
    {
        if (b & 1) res = (long long) res * a % p;
        a = (long long) a * a % p;
    }
    return res;
}

64位整数乘法

题目描述

求

乘

对

取模的值。

输入格式

第一行输入整数

，第二行输入整数

，第三行输入整数

。

输出格式

输出一个整数，表示

的值。

数据范围

输入样例：

3
4
5

输出样例：

2

解析一

龟速乘模板

时间复杂度：

long long mul(long long a, long long b, long long p)
{
    long long res = 0;
    for (; b; b >>= 1)
    {
        if (b & 1) res = (res + a) % p;
        a = a * 2 % p;
    }
    return res;
}

解析二

公式：

时间复杂度：

虽然

和

都很大，但易知他们的差在

~

之间

因此，我们只需关注他们的低位即可

typedef unsigned long long ull;
ull mul(ull a, ull b, ull p) {
	a %= p, b %= p;  // 当a,b一定在0~p之间时，此行不必要
	ull c = (long double)a * b / p;
	ull x = a * b, y = c * p;
	long long ans = (long long)(x % p) - (long long)(y % p);
	if (ans < 0) ans += p;
	return ans;
}

最短Hamilton路径

题目描述

给定一张

个点的带权无向图，点从

∼

标号，求起点

到终点

的最短 Hamilton 路径。

Hamilton 路径的定义是从

到

不重不漏地经过每个点恰好一次。

输入格式

第一行输入整数

。

接下来

行每行

个整数，其中第

行第

个整数表示点

到

的距离（记为

）。

对于任意的

,

,

，数据保证

，

并且

。

输出格式

输出一个整数，表示最短 Hamilton 路径的长度。

数据范围

，

输入样例：

5
0 2 4 5 1
2 0 6 5 3
4 6 0 8 3
5 5 8 0 5
1 3 3 5 0

输出样例：

18

解析

int f[1 << 20][20];
int hamilton(int n, int weight[20][20])
{
    memset(f, 0x3f, sizeof(f));
    f[1][0] = 0;
    for (int i = 1; i < 1 << n; i ++ )
        for (int j = 0; j < n; j ++ ) if (i >> j & 1)
            for (int k = 0; k < n; k ++ ) if (i >> k & 1)
                f[i][j] = min(f[i][j], f[i ^ 1 << j][k] + weight[k][j]);
    return f[(1 << n) - 1][n - 1];
}

起床困难综合症

题目描述

21 世纪，许多人得了一种奇怪的病：起床困难综合症，其临床表现为：起床难，起床后精神不佳。

作为一名青春阳光好少年，atm 一直坚持与起床困难综合症作斗争。

通过研究相关文献，他找到了该病的发病原因： 在深邃的太平洋海底中，出现了一条名为 drd 的巨龙，它掌握着睡眠之精髓，能随意延长大家的睡眠时间。

正是由于 drd 的活动，起床困难综合症愈演愈烈， 以惊人的速度在世界上传播。

为了彻底消灭这种病，atm 决定前往海底，消灭这条恶龙。

历经千辛万苦，atm 终于来到了 drd 所在的地方，准备与其展开艰苦卓绝的战斗。

drd 有着十分特殊的技能，他的防御战线能够使用一定的运算来改变他受到的伤害。

具体说来，drd 的防御战线由 n 扇防御门组成。

每扇防御门包括一个运算

和一个参数

，其中运算一定是

中的一种，参数则一定为非负整数。

如果还未通过防御门时攻击力为

，则其通过这扇防御门后攻击力将变为

。

最终 drd 受到的伤害为对方初始攻击力

依次经过所有

扇防御门后转变得到的攻击力。

由于 atm 水平有限，他的初始攻击力只能为

到

之间的一个整数（即他的初始攻击力只能在

中任选，但在通过防御门之后的攻击力不受

的限制）。

为了节省体力，他希望通过选择合适的初始攻击力使得他的攻击能让 drd 受到最大的伤害，请你帮他计算一下，他的一次攻击最多能使 drd 受到多少伤害。

输入格式

第 1 行包含 2 个整数，依次为

，表示 drd 有

扇防御门，atm 的初始攻击力为

到

之间的整数。

接下来

行，依次表示每一扇防御门。每行包括一个字符串

和一个非负整数

，两者由一个空格隔开，且

在前，

在后，

表示该防御门所对应的操作，

表示对应的参数。

输出格式

输出一个整数，表示 atm 的一次攻击最多使 drd 受到多少伤害。

数据范围

，

，

输入样例：

3 10
AND 5
OR 6
XOR 7

输出样例：

1

样例解释

atm 可以选择的初始攻击力为

。

假设初始攻击力为

，最终攻击力经过了如下计算

4 AND 5 = 4

4 OR 6 = 6

6 XOR 7 = 1

类似的，我们可以计算出初始攻击力为

时最终攻击力为

，初始攻击力为

时最终攻击力为

，因此 atm 的一次攻击最多使 drd 受到的伤害值为

。

解析

int n, m, one = (1 << 30) - 1, non = 0, res = 0;
cin >> n >> m;
for (int i = 1; i <= n; i++ )
{
    string op; int t; cin >> op >> t;
    if (op == "AND") one &= t, non &= t;
    else if (op == "XOR") one ^= t, non ^= t;
    else one |= t, non |= t;
}
for (int i = 30; i >= 0; i -- )
{
    if (non >> i & 1) res += 1 << i;
    else if (one >> i & 1 && m >= 1 << i)
    {
        m -= 1 << i;
        res += 1 << i;
    }
}