《算法竞赛进阶指南》学习笔记 0x01位运算——从二进制到快速幂和 lowbit前言学习这一节时我用 C 练了二进制位操作、快速幂和几道 Codeforces 题。比记住某个公式更难的是弄清楚当前这一位代表什么、代码里的变量此刻存着什么、一次操作究竟改变了什么。比如学快速幂时我问过“ans是干什么的”“为什么要取模”“b右移和a平方的顺序能不能换”。这些问题后来成了我检查代码时很有用的切入点。这篇笔记按我手头《算法竞赛进阶指南》0x01 位运算的内容顺序整理书外练习会单独标明。1. 先把整数看成二进制位二进制从右往左编号最低位是第0位。例如位号3 2 1 0 13 1 1 0 1所以13 2 3 2 2 2 0 8 4 1 132^32^22^084113232220841。第0、2、3位是1。一个十六进制位对应四个二进制位因此0x3F可以写成0011 1111。读位运算代码时我会先确认两个约定位号是否从0开始以及参与运算的整数类型有多少位。与、或、异或、取反运算C对单个二进制位做什么与两边都是1才得到1或|至少一边是1就得到1异或^两边不同得到1相同得到0取反~把0、1互换注意C 中^是异或不是乘方。~x也不能只对纸上写出的几位取反它作用于整数类型的位表示。补码和一个容易误用的初始化值在教材讨论的固定 32 位补码表示下负数可以通过“按位取反再加1”理解。例如用 8 位演示-550000 0101 取反1111 1010 加 11111 1011书中还讲到0x3F3F3F3F四个字节都是0x3F。因此memset(a, 0x3f, sizeof(a))是逐字节填充不是把数组中的每个int赋值为0x3f。2. 移位移动的是位不是随便改数字对非负整数在结果仍可表示的前提下左移k位相当于乘2 k 2^k2k右移k位相当于除以2 k 2^k2k后向下取整3 0011₂ 3 2 1100₂ 12 13 1101₂ 13 2 0011₂ 3负数右移、以及超出有符号类型范围的左移需要格外小心。写竞赛代码时我尽量不让算法正确性依赖这些边界行为。几种常见的单个位操作如下。这里假设n是无符号整数且k没有超出类型的位数(nk)1U;// 取出第 k 位结果是 0 或 1n(1Uk);// 检查第 k 位结果非 0 表示这一位是 1n|1Uk;// 第 k 位设为 1n~(1Uk);// 第 k 位清为 0n^1Uk;// 翻转第 k 位这里有个小区别n (1U k)得到的是一个掩码不一定是数字1如果想明确得到0或1用(n k) 1U更直观。3. 快速幂把指数拆开选中的幂累乘求a b a^bab时不一定要乘b次。把指数写成二进制例如6 110 2 4 2 , a 6 a 4 ⋅ a 2 . 6110_242,\qquad a^6a^4\cdot a^2.61102​42,a6a4⋅a2.这里我曾经把“二进制位的权值是2 2 2^222、2 1 2^121”和“底数的幂”说混。写完整之后就清楚了拆开的是指数6底数仍然是a。若底数是5则是5 6 5 4 ⋅ 5 2 5^65^4\cdot5^25654⋅52不是把底数换成2。快速幂循环里有三个角色b还没处理的指数b 1查看当前最低位b 1移到下一位。a当前位对应的幂依次是原底数的1 、 2 、 4 、 8 … 1、2、4、8\ldots1、2、4、8…次幂。ans已经选中的幂的乘积。因为做的是乘法初值是1。题目要求a b m o d p a^b\bmod pabmodp、且模数不大到使long long的中间乘法溢出时可以写成longlongqpow(longlonga,longlongb,longlongp){a%p;longlongans1%p;while(b0){if(b1)ansans*a%p;aa*a%p;b1;}returnans;}处理当前位时必须先判断b 1并在需要时把**当前的a**乘进ans。之后才为下一位更新变量。时间复杂度是O ( log ⁡ b ) O(\log b)O(logb)。我还问过“mod是取模吗为什么要取模数取7还是取谁都可以”答案是mod p表示求除以题目指定的p后的余数不能自己换模数。每步取模不会改变最终余数却能控制中间结果但先乘后取模仍可能在乘法那一步溢出。不需要取模时二进制拆指数的思路不变只是去掉% p。快速幂减少的是乘法次数不会扩大long long的存储范围。例如2 100 2^{100}2100即使用快速幂也不能用long long精确保存。我的 P1226 练习在 P1226【模板】快速幂 中我已经写出了按b 1累乘、平方底数和每步取模的循环。不过第一次输出把题目要求的a^b mod ps写成了没有空格的形式。这提醒我算法主体对了也要按题目逐字检查输出格式。4. 乘法取模这次按位累加教材接着讨论更大的a 、 b 、 p a、b、pa、b、p。如果直接算a * b乘法可能在% p之前就超出long long。一种处理方法与快速幂很像把b拆成二进制但这次是在计算乘法所以把选中的倍数相加。例如7 × 5 7 × ( 4 1 ) 28 7 7\times57\times(41)2877×57×(41)287。对应的模板是longlongmul_mod(longlonga,longlongb,longlongp){a%p;longlongans0;while(b0){if(b1)ans(ansa)%p;a(aa)%p;b1;}returnans;}我学习时问过“快速幂是累乘取模是累加吗”准确说法是快速幂按位选取后累乘这里的乘法取模算法按位选取后累加。“取模”本身只是求余数不等于累加。这份倍增代码还要检查约束在教材给出的p ≤ 10 18 p\le10^{18}p≤1018范围内每轮取模后ans、a均小于p下一次两数相加小于2 × 10 18 2\times10^{18}2×1018能放进long long。不能把它推广成“加法永远不会溢出”。书中还有借助浮点数估计商的另一种方法初学阶段我先保留这份更容易检查中间值范围的写法。5. 状态压缩一个整数也能记录“选过谁”教材把长度为m的布尔状态压进一个整数第i位为1表示第i个对象已选为0表示未选。例如0101₂中第0、2位是1表示编号0、2被选中。我曾把这里的位号看错现在会先从最右边的第 0 位开始标号再读集合。“最短 Hamilton 路径”是书中的状态压缩例子。可以用S记录已走过的点集用F [ S ] [ j ] F[S][j]F[S][j]表示“从起点出发恰好经过S中的点、当前停在点j时的最短路长”。S和j记录的是状态整个F [ S ] [ j ] F[S][j]F[S][j]才是这个状态对应的答案。当前阶段我主要记住这种表达方式完整的状态压缩 DP 还需要继续学习。书中的“起床困难综合症”则用了另一个特点AND、OR、XOR对各位分别运算可以逐位考虑。我当时用自己的话说过“二进制每一位都是独立的换成普通加法会混淆”。更严谨的限定是这些位运算在本题中各位独立普通加法可能产生进位低位就会影响高位。6.n ^ 1与lowbitn ^ 1只翻转最低位因此会在相邻的偶数、奇数之间切换0 ↔ 1 2 ↔ 3 4 ↔ 5lowbit(n) n -n则取得最低位那个1所对应的数值。例如22 10110₂ lowbit 00010₂ 2在固定字长的补码表示下-n可以理解为~n 1。取反再加一之后n与-n按位与只会留下最低位的那个1。反复减掉lowbit便能逐个删除二进制中的1while(n0){intbitn-n;// 最低位的 1 所对应的数值// 处理 bitn-bit;}注意bit是2 k 2^k2k这个数值不是位号k。这段循环执行的次数等于原数二进制中1的个数。7. 教材外练习从会手算走向会实现在 CF1095C Powers Of Two 中我最初想“遍历有没有恰好k个 2 的幂相加为n”但还没明确该遍历什么。后来我能自己手算13 1 4 8 1 4 4 4 1 2 2 4 4每次把一个2 i 2^i2i拆成两个2 i − 1 2^{i-1}2i−1总和不变项数加1。我第一次写统计二进制1的代码时直接把n一直右移到0后面又用k n判断结果这个条件总会成立。这里的教训很具体遍历时如果后面还要用原值就用副本。这道题目前记录的是手算、思路和辅导后的代码理解不是我已独立提交通过的战绩。同样CF1514B、CF1362A 等题也还在练习中。8. 这节我会反复检查的几件事位号从右往左、从0开始k是位号还是项数必须由题意决定。^是异或不是乘方n (1 k)得到的是掩码不一定是0或1。快速幂中的ans存累乘结果乘法倍增中的ans存累加结果mod p只是求余。% p不能补救已经发生的乘法溢出快速幂也不能让结果突破类型的表示范围。写出思路后还要检查变量是否被改掉、循环处理的是哪一位以及题目要求输出什么。参考资料李煜东《算法竞赛进阶指南》0x01 位运算。本文是结合我的学习提问、代码尝试和教材内容写成的复盘不是教材原文摘录。