第 3 章 运算符与位运算¶
配套例题：BISHI30、BISHI31、BISHI32 被打乱的异或和、BISHI57 最大公因数与最小公倍数 来源：菜鸟教程 Python3 运算符；S2
bit_op.cpp
本章讲全部七类运算符。位运算只讲语法层面，算法技巧（lowbit、枚举子集、状压） 在 46-位运算 展开。
3.1 算术运算符¶
| 运算符 | 含义 | 例（a=7, b=2） |
|---|---|---|
+ - * |
加减乘 | 9 5 14 |
/ |
真除法，永远返回 float | 3.5 |
// |
向下取整除法 | 3 |
% |
取模，符号随除数 | 1 |
** |
幂 | 49 |
/ 的陷阱¶
>>> 10 / 2
5.0 # 是 float 不是 int！
>>> 10 ** 18 // 3 # 333333333333333333 精确
>>> 10 ** 18 / 3 # 3.333333333333333e+17 丢精度了
算法题里几乎永远该用 //。用了 / 会有两个后果：结果变成 float（大数丢精度），
以及不能作为列表下标（a[n/2] 直接 TypeError）。
** 与 pow¶
2 ** 10 # 1024
pow(2, 10) # 1024，等价
pow(2, 10, 1000) # 24，三参数版本 = 快速幂取模
2 ** 0.5 # 1.4142135623730951，指数可以是小数
x ** 0.5和math.sqrt(x)都返回 float，大整数开方会丢精度。 需要整数平方根时用math.isqrt(x)（Python 3.8+），它精确且返回 int：原因：float 只有 53 位有效位（约 \(9 imes 10^{15}\)）。 超过这个范围的整数转成 float 时先被舍入，开方结果可能比真值大也可能比真值小， 两个方向都会出错——大了让试除多跑几轮，小了直接漏掉因子，把合数判成质数。
isqrt走的是纯整数牛顿迭代，没有浮点参与，任何规模都精确。
负数取整的完整对照¶
| 表达式 | Python | C++ |
|---|---|---|
-7 / 2 |
-3.5 |
-3（整数除法） |
-7 // 2 |
-4 |
-3 |
-7 % 2 |
1 |
-1 |
divmod(-7, 2) |
(-4, 1) |
— |
牢记：Python 的 // 向下（floor），% 结果符号跟除数。
3.2 比较运算符¶
== != > < >= <=，返回 bool。
链式比较¶
Python 独有的语法糖，且语义正确（不像 C++ 里 1 < x < 3 会被解析成 (1<x)<3）：
链式比较中间的表达式只求值一次：
容器的比较¶
列表、元组按字典序逐元素比较：
[1, 2, 3] < [1, 3] # True 第二个元素 2 < 3
(1, 2) < (1, 2, 0) # True 前缀相同则短的小
"abc" < "abd" # True 字符串按码点比较
这是元组排序的基础——排序时把关键字按优先级放进元组即可，见 12-自定义排序。
3.3 赋值运算符¶
a = 1
a += 2 # 等价 a = a + 2
a -= 1; a *= 3; a /= 2; a //= 2; a %= 3; a **= 2
a &= 1; a |= 2; a ^= 3; a <<= 1; a >>= 1
多重赋值与解包¶
a, b = 1, 2
a, b = b, a # 交换，不需要临时变量
a = b = c = 0 # 链式赋值
first, *rest = [1, 2, 3, 4] # first=1, rest=[2,3,4]
*init, last = [1, 2, 3, 4] # init=[1,2,3], last=4
a, b = b, a的原理是先把右边求值成元组，再解包赋给左边， 所以真的能安全交换。C++ 里必须借助临时变量或std::swap。同理，斐波那契可以写成一行：
增强赋值对可变对象的特殊行为¶
a = [1, 2]
b = a
a += [3] # 就地扩展，等价 a.extend([3])
print(b) # [1, 2, 3] ← b 也变了
a = [1, 2]
b = a
a = a + [3] # 创建新列表并重新绑定
print(b) # [1, 2] ← b 没变
+= 对 list 是就地修改，对 int/str/tuple 是重新绑定。这个差异在函数传参时会咬人。
海象运算符 :=（3.8+）¶
在表达式内部赋值：
竞赛里最常见的用途是在 while 条件里读入并判断，省掉重复代码。
3.4 逻辑运算符¶
and or not——注意 Python 用英文单词，不是 && || !。
短路求值与返回值¶
and/or 返回的是操作数本身，不是布尔值：
>>> 1 and 2 # 2 前者为真，返回后者
>>> 0 and 2 # 0 前者为假，短路返回前者
>>> 1 or 2 # 1 前者为真，短路返回前者
>>> 0 or 2 # 2 前者为假，返回后者
>>> None or [] # []
实用写法：
坑：
x = val or 0在val本身就是0时也会取到0，看似没问题； 但x = val or 10在val == 0时会得到10，这通常不是本意。 需要严格区分时用x = val if val is not None else 10。
三元表达式¶
顺序是「值 - if - 条件 - else - 值」，和 C 的 cond ? a : b 相反，容易写反。
3.5 成员与身份运算符¶
in 的复杂度取决于容器类型，这是竞赛里的核心性能点：
| 容器 | x in c 复杂度 |
|---|---|
list / tuple |
\(O(n)\) 线性扫描 |
str |
\(O(n \cdot m)\) 子串搜索 |
set / frozenset |
\(O(1)\) 平均 |
dict |
\(O(1)\) 平均（查的是键） |
# ❌ 循环里用 list 判存在 → O(n²)，n=1e5 就 TLE
seen = []
for x in a:
if x not in seen:
seen.append(x)
# ✅ 换成 set → O(n)
seen = set()
for x in a:
if x not in seen:
seen.add(x)
这是 Python 算法题最高频的 TLE 原因，没有之一。 只要写出
in且左边是循环变量，就停下来问一句：右边是set还是list？
3.6 位运算符¶
| 运算符 | 名称 | 例（a=60=0b111100, b=13=0b1101） |
|---|---|---|
& |
按位与 | a & b = 12 = 0b1100 |
\| |
按位或 | a \| b = 61 = 0b111101 |
^ |
按位异或 | a ^ b = 49 = 0b110001 |
~ |
按位取反 | ~a = -61 |
<< |
左移 | a << 2 = 240 |
>> |
右移 | a >> 2 = 15 |
Python 位运算的三个特殊之处¶
1. 整数是无限位的补码。 ~x 等于 -x - 1，永远成立：
因为没有固定位宽，所以没有「符号位溢出」这回事，
C++ 里 ~x 的结果依赖 int 是 32 还是 64 位，Python 里不会。
2. 左移不会溢出。 1 << 1000 是合法的巨大整数。这让状压 DP 的状态数不受 64 位限制，
但也意味着位运算不再是 \(O(1)\)——大整数的位运算是 \(O(\text{位数})\)。
3. 负数右移是算术右移（补符号位）：
所以不要对可能为负的数做右移当除法，除非确实需要向下取整的语义。
常用位技巧速查¶
x & 1 # 取最低位，判奇偶
x >> 1 # 除以 2（向下取整）
x & (x - 1) # 消去最低位的 1
x & (-x) # lowbit：只保留最低位的 1（树状数组核心）
x | (1 << k) # 把第 k 位置 1
x & ~(1 << k) # 把第 k 位清 0
x ^ (1 << k) # 翻转第 k 位
(x >> k) & 1 # 取第 k 位
bin(x).count("1") # 数 1 的个数（3.9 环境下的写法）
Python 3.10 引入了
int.bit_count()，比bin(x).count("1")快很多。 本教程的运行环境是 3.9，所以统一用bin(x).count("1")； 如果 OJ 的 Python 版本 ≥ 3.10，可以换成x.bit_count()。
异或的三条性质¶
这是位运算题的核心，BISHI32 直接考它：
- \(x \oplus x = 0\)（自反）
- \(x \oplus 0 = x\)（幺元）
- 满足交换律和结合律
推论：一组数全部异或起来，出现偶数次的会互相抵消。
3.7 运算符优先级¶
从高到低（同一行内左结合）：
** 幂（右结合）
+x -x ~x 一元
* / // % 乘除
+ - 加减
<< >> 移位
& 按位与
^ 按位异或
| 按位或
in not in is is not
< <= > >= != == 比较
not 逻辑非
and
or
if - else 三元
lambda
:= 海象
最容易踩的两条：
# 1. 位运算的优先级「比比较高、比算术低」，前半截和 C 恰好相反
if x & 3 == 1: # Python 解析成 (x & 3) == 1 ← 和直觉一致
# 同一行代码在 C/C++ 里是 x & (3 == 1) = x & 0 = 0，含义完全不同
mask = 1 << n + 1 # ← 真正的坑：加减比移位优先级高，这里是 1 << (n + 1)
mask = 1 << (n + 1) # ✅ 想表达什么就写什么，别让读者去查表
# 2. ** 是右结合
2 ** 3 ** 2 # = 2 ** 9 = 512，不是 (2**3)**2 = 64
规则：写位运算就加括号。理由不是「记不住优先级」， 而是同一行代码在 C/C++ 和 Python 里可能解析成两个不同的表达式， 加了括号两边就都只有一种读法。
3.8 例题¶
BISHI32 被打乱的异或和（简单）¶
题面见 BISHI32 原题（牛客）。
原数组 \(b\) 长度为 \(n-1\)，令 \(x = b_1 \oplus \cdots \oplus b_{n-1}\)， 把 \(x\) 追加到末尾得到长度 \(n\) 的数组并打乱。给出打乱后的数组，求 \(x\)；答案不唯一时输出任意一个。
这题的答案比看上去简单得多，全部来自 3.6 的三条性质。
设新数组为 \(a\)，则
即新数组的全体异或恒为 0。现在要找一个 \(a_i\) 使得「去掉它之后其余元素的异或等于它自己」。 而去掉 \(a_i\) 后其余元素的异或是
对每一个 \(a_i\) 都成立。所以任意一个元素都是合法答案——直接输出第一个即可：
import sys
def main():
data = sys.stdin.buffer.read().split()
p = 0
t = int(data[p]); p += 1
out = []
for _ in range(t):
n = int(data[p]); p += 1
out.append(data[p].decode()) # 任取一个元素即可，这里取第一个
p += n
sys.stdout.write("\n".join(out) + "\n")
main()
样例输出的是
3、7……而本节代码输出4、6……两者都对， 因为题面写明「若存在多种可能的 \(x\)，可输出任意一个」。 这类 special judge 题如果按样例逐字符比对，会误以为自己写错了。 见 20-输入输出处理 §20.6。
顺带一提，「全体异或」的惯用写法是：
# [片段]
from functools import reduce
from operator import xor
reduce(xor, a, 0) # 等价于 a[0] ^ a[1] ^ ...，初值 0 保证空列表也正确
BISHI57 最大公因数与最小公倍数（简单）¶
求两个数的 gcd 与 lcm。
a // g * b 而不是 a * b // g——两者数学上等价，但前者的中间值更小。
在 C++ 里这是防溢出的必要写法；Python 虽然不会溢出，但大整数乘法是 \(O(\text{位数}^{1.58})\)，
先除能显著减少中间值规模。养成习惯没坏处。
Python 3.9 起
math.gcd支持多个参数：math.gcd(a, b, c)。math.lcm也是 3.9 引入的，可以直接用math.lcm(a, b)。
3.9 本章速查¶
| 要点 | 结论 |
|---|---|
| 整数除法 | 永远用 //，/ 返回 float 且丢精度 |
| 整数开方 | math.isqrt(x)，不要用 x ** 0.5 |
| 负数取整 | // 向下，% 符号随除数 |
| 交换变量 | a, b = b, a |
| 链式比较 | 0 <= i < n 语义正确，放心用 |
and/or |
返回操作数本身，可用于取默认值 |
in 的容器 |
set/dict 是 \(O(1)\)，list 是 \(O(n)\) ← 最高频 TLE 原因 |
| 位运算优先级 | 一律加括号 |
~x |
等于 -x - 1，Python 无位宽概念 |
| 数 1 的个数 | 3.9 用 bin(x).count("1")，3.10+ 用 x.bit_count() |
| lcm | a // g * b，先除后乘 |