数学与位运算 解题模板

适用场景

数学规律、位运算技巧、进制转换、概率

常用技巧

位运算

 
# 常用操作
 
n & (n-1)  # 清除最低位的 1 → 数1的个数 / 判断2的幂
 
n & -n     # 取最低位的 1
 
a ^ a = 0  # 异或抵消
 
a ^ 0 = a
 
# 获取第 k 位: (n >> k) & 1
 

数学规律

 
# 阶乘后零：数 5 的因子
 
count = 0
 
while n: n //= 5; count += n
 
# 快速幂：O(log n)
 
res = 1
 
while n:
 
    if n & 1: res *= x
 
    x *= x
 
    n >>= 1
 

拒绝采样

 
# 用 Rand7 实现 Rand10
 
while True:
 
    num = (rand7()-1)*7 + rand7()
 
    if num <= 40:
 
        return (num-1) % 10 + 1
 

关键要点

• 位运算常作为优化手段

• n & (n-1) 是高频考点

• 注意溢出（Python 无溢出，但其他语言有）

• 数学题多从「手算规律」出发

→ 查看该分类题目：LeetCode学习路线图 > 十四、数学与位运算

---

关联题型

关联题型	常见结合方式	典型题目
数组	位运算代替哈希	136只出现一次
动态规划	数学归纳到DP	70爬楼梯