9 min read1,856 words

位运算与数学技巧

简介

位运算与数学技巧是算法竞赛与面试中不可或缺的利器，它们以极高的效率和简洁的代码解决看似复杂的问题。位运算直接操作整数的二进制位，其速度远超常规算术运算，常用于状态压缩、权限管理、快速计算等场景。而数学技巧则提供了对问题本质的洞察，将时间复杂度从多项式级别降至对数甚至常数级别，例如快速幂算法、欧几里得算法等。掌握这两类技巧，不仅能提升解题速度，更能培养对数据底层表示和数学规律的深刻理解，是区分普通程序员与算法高手的关键能力。本章将系统性地讲解常用位运算操作、其巧妙应用，以及相关的核心数学算法，并通过经典例题加以巩固。

核心概念

位运算的核心在于直接对二进制位进行操作。主要操作符包括： 1. 与（&）：两位都为1时，结果才为1。常用于掩码操作，提取或清零特定位。 2. 或（|）：两位中有一个为1时，结果就为1。常用于设置特定位为1。 3. 异或（^）：两位不同时，结果为1。具有自反性：a ^ a = 0, a ^ 0 = a。常用于不借助临时变量交换两数、寻找唯一出现一次的数字。 4. 取反（~）：一元操作符，对每一位取反。~x 等价于 -x - 1。 5. 左移（<<）：将二进制位全部左移若干位，高位丢弃，低位补0。左移n位相当于乘以 2^n。 6. 右移（>>）：将二进制位全部右移若干位，低位丢弃。对于无符号数，高位补0；对于有符号数，高位补符号位（算术右移）。右移n位相当于除以 2^n 并向下取整。

数学技巧则侧重于利用数学定理和性质优化算法： 1. 质数判断：从试除法到基于6的倍数的优化，再到更高效的米勒-拉宾素性测试。 2. 最大公约数（GCD）：使用欧几里得算法（辗转相除法）及其更高效的二进制实现（Stein算法）。 3. 快速幂：通过将指数二进制分解，将乘方运算的时间复杂度从O(n)降至O(log n)。

下图展示了位运算与数学技巧在解决算法问题时的核心思路与关联：

graph TD A["问题输入"] --> B{“问题类型分析”} B -->|“涉及状态、集合、二进制特征”| C[“位运算技巧”] B -->|“涉及数论、计算、公式优化”| D[“数学技巧”] C --> E[“常用操作: & | ^ ~ << >>”] D --> F[“核心算法: 质数判断 GCD 快速幂”] E --> G[“典型应用: 判断奇偶交换数字找唯一数”] F --> H[“典型应用: 模运算分数化简高效幂乘”] G --> I[“输出结果”] H --> I

实战示例

以下是一个综合示例，演示了如何利用位运算寻找数组中“只出现一次的数字”（其他数字均出现两次），并使用快速幂算法计算一个数的正整数次方。

def single_number(nums):
"""
使用异或运算找出数组中只出现一次的元素。
异或的性质： a ^ a = 0, a ^ 0 = a，且满足交换律和结合律。
因此，所有出现两次的数字异或后结果为0，最后剩下的就是只出现一次的数字。
"""
result = 0
for num in nums:
result ^= num  # 对数组中所有元素进行异或操作
return result
def fast_pow(x: float, n: int) -> float:
"""
快速幂算法计算 x 的 n 次方。
将指数 n 用二进制表示，例如 x^13 = x^(1101)_2 = x^(8) * x^(4) * x^(1)。
通过不断将底数平方（x -> x^2 -> x^4 ...）和判断 n 的二进制位是否为1来决定是否乘入结果。
"""
if n < 0:  # 处理负指数
x = 1 / x
n = -n
result = 1.0
current_product = x
while n > 0:
# 如果当前二进制位为1，则将当前的乘积累乘到结果中
if n & 1:  # 等价于 n % 2 == 1，判断奇偶/二进制最低位
result *= current_product
# 将底数平方，为下一次位判断做准备
current_product *= current_product
# 右移一位，相当于 n //= 2，检查下一个二进制位
n >>= 1
return result
def count_bits(n: int) -> list:
"""
计算从 0 到 n 的每个数字的二进制表示中 1 的个数（Brian Kernighan 算法）。
利用 n & (n-1) 可以消去 n 的二进制表示中最低位的 1 这一特性。
"""
ans = [0] * (n + 1)
for i in range(1, n + 1):
# i & (i-1) 的结果比 i 的二进制表示中少一个 1
ans[i] = ans[i & (i - 1)] + 1
return ans
if __name__ == "__main__":
# 示例1: 只出现一次的数字
arr1 = [4, 1, 2, 1, 2]
print(f"在数组 {arr1} 中，只出现一次的数字是: {single_number(arr1)}")  # 输出 4
# 示例2: 快速幂
base, exponent = 2.0, 10
print(f"{base} 的 {exponent} 次方是: {fast_pow(base, exponent)}")  # 输出 1024.0
# 示例3: 位1的个数
num_bits = 5
bit_counts = count_bits(num_bits)
print(f"从 0 到 {num_bits} 各数字的位1计数: {bit_counts}")  # 输出 [0, 1, 1, 2, 1, 2]

对比分析

下表对比了解决“计算一个数的幂”问题的几种不同方法：

方案	优势	劣势	适用场景
库函数直接调用 (如 `math.pow`)	代码极其简洁，无需自己实现；通常经过高度优化，对于常规用例足够快且准确。	隐藏了算法细节，不利于理解原理；在某些编程环境或算法题中可能不允许使用。	日常开发、对性能无极端要求的快速原型。
迭代连乘法	逻辑直观，易于理解和实现；对于非常小的指数（n<3）可能最简单。	时间复杂度为 O(n)，当指数 n 很大时（如 10^9）完全不可行，效率极低。	仅用于教学演示或指数极小（n<10）的场合。
递归快速幂	代码简洁，直接体现了分治思想（幂次减半）；时间复杂度为 O(log n)。	递归调用有函数调用开销，且存在栈溢出风险（对于极深的递归，尽管 log n 通常不大）。	适合在支持尾递归优化的语言中，或作为快速幂的原理性说明。
迭代快速幂（位运算）	时间复杂度为 O(log n)，且无递归开销，常数因子更小；利用位运算，效率极高。	代码相对递归版本稍复杂，需要理解二进制和位运算。	算法竞赛、面试、高性能计算场景的首选方案，尤其当 n 可能很大时。

最佳实践

善用异或（XOR）的性质：牢记 a ^ a = 0 和 a ^ 0 = a。这不仅是解决“只出现一次的数字”系列问题的关键，还可用于简单的加密、校验和计算以及不使用临时变量交换两个整数（a ^= b; b ^= a; a ^= b;）。
使用 n & (n-1) 操作：这是一个非常强大的技巧。它可以：
- 判断一个数是否是2的幂：如果 n > 0 且 n & (n-1) == 0，那么n就是2的幂。
- 计算二进制中1的个数（Brian Kernighan 算法）：不断执行 n = n & (n-1) 直到n为0，操作的次数就是1的个数。
- 消除二进制表示中最低位的1：这在状态压缩DP中常用于枚举子集。
理解算术移位与逻辑移位的区别：在大多数语言（如Java、C++）中，对有符号整数使用 >> 是算术右移（高位补符号位），而对无符号整数使用是逻辑右移（高位补0）。在Python中，>> 是算术右移。明确这一点可以避免在处理负数时出现意外结果。
快速幂的模板化：将迭代快速幂算法作为模板记忆。其核心循环结构是固定的：在 while(n > 0) 循环内，判断 n & 1，累乘结果，平方底数，然后 n >>= 1。此模板可推广到矩阵快速幂或需要取模的大数运算中。
数学优化先行：在尝试编码之前，先思考问题是否可以用数学公式或性质简化。例如，计算从1到n的和可以用公式 n*(n+1)/2 在O(1)时间内完成，而非O(n)的循环。判断质数时，只需遍历到 sqrt(n) 即可。

小结

位运算与数学技巧是提升算法效率与代码优雅性的核心手段。位运算通过对二进制位的直接操控，实现了诸如状态判断、快速计算和空间压缩等高级功能。数学技巧则利用数论和代数知识，将复杂运算化简，典型代表是快速幂算法和欧几里得算法。掌握这些技巧的关键在于理解其背后的二进制原理与数学定理，并通过大量练习将常见模式内化。在实际应用中，应优先考虑能否用位运算或数学方法优化暴力解法，这往往是通往最优解的关键一步。

下一节：实战整合与求职路线图