1. 进制与补码
1.1 为什么用补码
计算机用补码表示整数，核心收益：减法与加法用同一套电路。n 位补码的表示范围是 -2^(n-1) ~ 2^(n-1)-1，负数 = 对应正数按位取反加一。
# 4 位补码示例
# 5 = 0101
# -5 = 1011（0101 取反 = 1010，+1 = 1011）
# 溢出判定: 同号相加得异号 → 溢出
补码的工程启示：溢出是「静默环绕」而非报错。整数运算要防溢出（用更大类型或检查边界），尤其 C/C++ 场景。
2. 位运算基础与技巧
2.1 六种基本运算
# 与 & | 或 ^ 异或 ~ 取反 << 左移 >> 右移
# 关键性质
# x ^ 0 = x, x ^ x = 0 —— 异或的可逆性
# x & (x-1) = 去掉最低位 1 —— 统计 1 的个数核心
# x & (-x) = 取出最低位 1（lowbit）
# (x & 1) == 0 判断偶数
# x >> k & 1 取第 k 位
2.2 常见技巧
# 统计二进制中 1 的个数
def popcount(x):
cnt = 0
while x:
x &= x - 1 # 每次去掉最低位 1
cnt += 1
return cnt
# 判断是否为 2 的幂
# x > 0 and (x & (x-1)) == 0
# 交换两数（不推荐，仅为演示异或性质）
# a ^= b; b ^= a; a ^= b
工程上尽量避免用位运算换"炫技"，可读性优先；但底层优化（标志位、权限位图、状态压缩）离不开位运算。
3. 位图与集合表示
3.1 Bitmap 的应用
**位图（Bitmap）**用每一位表示「存在/不存在」，是空间极省的集合表示：10 亿个 ID 去重只需约 125MB。
# 用整数数组实现位图
# 位 i 表示数字 i 是否出现
# set(i): arr[i>>6] |= 1L << (i & 63)
# clear(i): arr[i>>6] &= ~(1L << (i & 63))
# test(i): (arr[i>>6] >> (i & 63)) & 1
工程经典场景：Bloom Filter（位图 + 哈希近似集合，允许误判）、状态压缩 DP（用位表示集合子集）、权限系统（每位一个权限）。位图适合「元素范围有限、只问存在性」的场景。
4. 取模与同余
4.1 模运算的性质
模运算对加、减、乘保持分配律，对除法不成立（需用逆元）：
# (a + b) % m = ((a % m) + (b % m)) % m
# (a * b) % m = ((a % m) * (b % m)) % m
# 除法: a/b 在模 m 下 = a * b^(m-2)（m 为素数，费马小定理）
# 负数取模: 先加 m 再取模，保证非负
工程上取模的两个坑：负数行为因语言而异（Python 与 C 对 -1 % 5 结果不同）；大数乘法先取模再乘防溢出。
5. 最大公约数与扩展欧几里得
5.1 欧几里得算法
辗转相除法求 GCD，复杂度 O(log min(a,b))：
def gcd(a, b):
return a if b == 0 else gcd(b, a % b)
# 最小公倍数
def lcm(a, b):
return a // gcd(a, b) * b # 先除后乘防溢出
5.2 扩展欧几里得
求解 ax + by = gcd(a,b) 的一组整数解 (x, y)，是模逆元与线性同余方程的基础：
def exgcd(a, b):
if b == 0:
return a, 1, 0
g, x1, y1 = exgcd(b, a % b)
return g, y1, x1 - (a // b) * y1
扩展欧几里得的工程价值：求模逆元（用于 RSA、模除法）、求解一次不定方程（编程竞赛与数论应用的常用工具）。
6. 素数与质因数分解
6.1 素数筛法
埃拉托斯特尼筛 O(n log log n)，线性筛 O(n)：
# 线性筛（欧拉筛）：每个合数只被最小质因子筛一次
def sieve(n):
primes, is_comp = [], [False] * (n + 1)
for i in range(2, n + 1):
if not is_comp[i]:
primes.append(i)
for p in primes:
if i * p > n:
break
is_comp[i * p] = True
if i % p == 0: # p 是 i 的最小质因子，break
break
return primes
6.2 质因数分解
试除法 O(sqrt(n))：从小到大除，每除尽一个因子记一次。工程上「1 亿以内判断素数」用试除 + 平方根边界即可；超大数用 Miller-Rabin + Pollard-Rho。
7. 快速幂
7.1 二分幂
快速幂把求 a^b 从 O(b) 降到 O(log b)，是数论算法与工程中的高频基础：
def fast_pow(a, b, m):
res = 1
while b:
if b & 1:
res = res * a % m
a = a * a % m
b >>= 1
return res
要点：每次平方底数、按位累乘结果。配合取模可算超大次幂；矩阵快速幂扩展用于递推式（斐波那契、线性递推）的 O(log n) 求解。
8. 位运算在工程中的经典应用
8.1 三个高频场景
- 状态压缩：棋盘/子集类 DP 用位表示状态，
visited | (1<<i)打标记。 - 集合运算：用位运算做并集（|）、交集（&）、差集（&~）。
- 标志位：单个 int 存多个开关（读
flags & FLAG_A，写flags |= FLAG_A），省内存、快。
# 只出现一次的数字（经典异或题）
# 其他数字都成对，找唯一单身数字
# xor = 0
# for x in arr: xor ^= x → 最后 xor 就是答案
8.2 何时用位运算
规则：优先可读性，瓶颈处才用位优化。枚举集合、权限标志、状态压缩这类「天然是位」的场景放心用；普通业务逻辑强行位运算反而难维护。
9. 常见陷阱
- 右移对有符号负数的行为：算术右移（补符号位）vs 逻辑右移——不同语言不同，明确语义再用。
- int 溢出：
1<<31在 32 位 int 溢出，大位移用 long。 - 负数右移循环：popcount 类操作对负数要转无符号或用 while 条件。
- 浮点与取模：浮点数没有精确取模，别对 float 用
%。
参考文章
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。