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

2022-10-31 10:54:55 浏览数 (2)

Bit Twiddling Hacks

位运算基础概念

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

运算

运算符

解释

与

&

只有两个对应位都为 (1) 时才为 (1)

或

|

只要两个对应位有一个 (1) 时就为 (1)

异或

^

只有两个对应位不同时才为 (1)

取反

~

对二进制表示的每一位取反（有符号数的符号位也会取反）

左移

<<

对二进制表示向左移动 (1) 位所得的值

右移

>>

对二进制表示向右移动 (1) 位所得的值

1

时才为

1

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

1

时就为

1

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

1

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

1

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

1

位所得的值

运算符优先级

加减

移位

比较大小

位与

异或

位或

-

<< >>

> < == !=

&

^

|

二进制常用操作

操作

运算

取出整数 n 在二进制表示下的第 k 位

(n >> k) & 1

取出整数 n 在二进制表示下的第 0 ~ k-1 位 (后 k 位)

n & ((1 << k) - 1)

把整数 n 在二进制表示下的第 k 位取反

n xor (1 << k)

对整数 n 在二进制表示下的第 k 位赋值 1

n | (1 << k)

对整数 n 在二进制表示下的第 k 位赋值 0

n & (~(1 << k))

位运算的应用

基本分类：

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

2 的幂次相关

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

向下取整，而非向零取整

代码语言：javascript复制
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

代码语言：javascript复制
bool isPowerOfTwo(int n)
{
    return n > 0 && (n & (n - 1)) == 0;
}

对 2 的非负整数次幂取模

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

代码语言：javascript复制
int modPowerOfTwo(int x, int mod)
{
    return x & (mod - 1);
}

模拟集合操作

操作

集合表示

位运算语句

交集

(a cap b)

a & b

并集

(a cup b)

a | b

补集

(overline{a})

~a

差集

(a setminus b)

a & (~b)

对称差

(a Delta b)

a ^ b

a cap b

a & b 并集

a cup b

a | b 补集

overline{a}

~a 差集

a setminus b

a & (~b) 对称差

a Delta b

a ^ b

子集遍历

时间复杂度：

O(2^{popcount(u)})

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

O(3^n)

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

代码语言：javascript复制
// 遍历 u 的非空子集
for (int s = u; s; s = (s - 1) & u)
{
  // s 是 u 的一个非空子集
}

成对变换

n

为奇数时，

n oplus 1 = n - 1
n

为偶数时，

n oplus 1 = n 1

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

oplus

是成对变换的

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

lowbit 运算

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

[ mathrm{lowbit}(x) = x & -x = x & (sim x 1) ]

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

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

代码语言：javascript复制
int lowbit(int u)
{
    return u & -u;
}

习题

a^b

题目描述

求

a

的

b

次方对

p

取模的值。

输入格式

三个整数

a

,

b

,

p

,在同一行用空格隔开。

输出格式

输出一个整数，表示

a^b bmod p

的值。

数据范围

0≤a,b≤10^9
1≤p≤10^9

输入样例：

代码语言：javascript复制
3 2 7

输出样例：

代码语言：javascript复制
2

解析

快速幂模板

时间复杂度：

O(log_2 b)
代码语言：javascript复制
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位整数乘法

题目描述

求

a

乘

b

对

p

取模的值。

输入格式

第一行输入整数

a

，第二行输入整数

b

，第三行输入整数

p

。

输出格式

输出一个整数，表示

a * b bmod p

的值。

数据范围

1≤a,b,p≤10^{18}

输入样例：

代码语言：javascript复制
3
4
5

输出样例：

代码语言：javascript复制
2

解析一

龟速乘模板

时间复杂度：

O(log_2 b)
代码语言：javascript复制
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;
}

解析二

公式：

a * b bmod p = a * b - lfloor{dfrac{a * b}{p}}rfloor * p

时间复杂度：

O(1)

虽然

a * b

和

lfloor{dfrac{a * b}{p}}rfloor * p

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

0

~

p-1

之间

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

代码语言：javascript复制
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路径

题目描述

给定一张

n

个点的带权无向图，点从

0

∼

n−1

标号，求起点

0

到终点

n−1

的最短 Hamilton 路径。

Hamilton 路径的定义是从

0

到

n−1

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

输入格式

第一行输入整数

n

。

接下来

n

行每行

n

个整数，其中第

i

行第

j

个整数表示点

i

到

j

的距离（记为

a[i,j]

）。

对于任意的

x

,

y

,

z

，数据保证

a[x,x]=0

，

a[x,y]=a[y,x]

并且

a[x,y] a[y,z]≥a[x,z]

。

输出格式

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

数据范围

1≤n≤20

，

0≤a[i,j]≤10^7

输入样例：

代码语言：javascript复制
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

输出样例：

代码语言：javascript复制
18

解析

代码语言：javascript复制
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 扇防御门组成。

每扇防御门包括一个运算

op

和一个参数

t

，其中运算一定是

OR,XOR,AND

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

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

x

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

x op t

。

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

x

依次经过所有

n

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

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

0

到

m

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

0,1,…,m

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

m

的限制）。

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

输入格式

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

n,m

，表示 drd 有

n

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

0

到

m

之间的整数。

接下来

n

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

op

和一个非负整数

t

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

op

在前，

t

在后，

op

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

t

表示对应的参数。

输出格式

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

数据范围

2 le n le 10^5

，

2 le m le 10^9

，

0 le t le 10^9
op in {OR, XOR, AND}

输入样例：

代码语言：javascript复制
3 10
AND 5
OR 6
XOR 7

输出样例：

代码语言：javascript复制
1

样例解释

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

0,1,…,10

。

假设初始攻击力为

4

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

代码语言：javascript复制
4 AND 5 = 4

4 OR 6 = 6

6 XOR 7 = 1

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

1,3,5,7,9

时最终攻击力为

0

，初始攻击力为

0,2,4,6,8,10

时最终攻击力为

1

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

1

。

解析

代码语言：javascript复制
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;
    }
}
xor 二进制

0 人点赞