位运算算法完全指南

算法 位运算 优化

学习提示

位运算是底层优化的重要工具，虽然现代编译器很智能，但理解位运算能帮助你写出更高效的代码。预计学习时间 1-2 周。

一、什么是位运算？ 💻

位运算（Bit Manipulation）是直接对整数在内存中的二进制位进行操作的运算。它是计算机最底层的操作，速度极快。

基本位运算符

& 按位与
两个位都为 1 时结果为 1 示例：5 & 3 = 1
\| 按位或
两个位有一个为 1 时结果为 1 示例：5 \| 3 = 7
^ 按位异或
两个位不同时结果为 1 示例：5 ^ 3 = 6
<< 左移
所有位向左移动，右边补 0 示例：5 << 1 = 10
>> 右移
所有位向右移动，左边补符号位 示例：5 >> 1 = 2
~ 按位取反
0 变 1，1 变 0 示例：~5 = -6

位运算的真值表

A B A & B A \ B A ^ B
0 0 0 0 0
0 1 0 1 1
1 0 0 1 1
1 1 1 1 0

记忆技巧

二、位运算的基本性质 🔑

理解这些性质是掌握位运算技巧的关键。

1. 异或的性质

异或（XOR）是最神奇的位运算符，有许多有趣的性质。

异或的神奇应用 
# 1. 交换两个数（无需临时变量）
a, b = 5, 10
a ^= b
b ^= a
a ^= b
print(f"a={a}, b={b}")  # a=10, b=5

# 2. 找出数组中唯一的单个元素（其他都出现两次）
def find_single_number(nums):
    result = 0
    for num in nums:
        result ^= num
    return result

print(find_single_number([4, 1, 2, 1, 2]))  # 4

2. 位移的性质

左移和右移与乘除法的关系：

python 
# 左移 n 位 = 乘以 2^n
print(5 << 1)   # 10 (5 * 2)
print(5 << 2)   # 20 (5 * 4)
print(5 << 3)   # 40 (5 * 8)

# 右移 n 位 = 除以 2^n（向下取整）
print(10 >> 1)  # 5 (10 // 2)
print(20 >> 2)  # 5 (20 // 4)
print(40 >> 3)  # 5 (40 // 8)

注意事项

三、经典位运算技巧 🎯

1. 判断奇偶性

python 
def is_odd(n):
    """判断是否为奇数"""
    return n & 1 == 1

def is_even(n):
    """判断是否为偶数"""
    return n & 1 == 0

# 测试
print(is_odd(5))   # True
print(is_even(4))  # True

原理：奇数的最低位是 1，偶数的最低位是 0

2. 计算 2 的幂

python 
def is_power_of_two(n):
    """判断是否为 2 的幂"""
    return n > 0 and (n & (n - 1)) == 0

# 测试
print(is_power_of_two(1))   # True  (2^0)
print(is_power_of_two(2))   # True  (2^1)
print(is_power_of_two(4))   # True  (2^2)
print(is_power_of_two(8))   # True  (2^3)
print(is_power_of_two(6))   # False

原理：2 的幂的二进制表示只有一个 1，n & (n-1) 会消除最低位的 1

3. 统计二进制中 1 的个数

python 
def count_bits(n):
    """统计二进制中 1 的个数"""
    count = 0
    while n:
        n &= n - 1  # 消除最低位的 1
        count += 1
    return count

# 测试
print(count_bits(0))   # 0
print(count_bits(1))   # 1
print(count_bits(5))   # 2  (101)
print(count_bits(7))   # 3  (111)

时间复杂度：O(k)，k 为 1 的个数，比 O(log n) 更快

4. 获取最低位的 1

python 
def lowest_bit(n):
    """获取最低位的 1"""
    return n & (-n)

# 测试
print(lowest_bit(6))   # 2  (110 -> 010)
print(lowest_bit(12))  # 4  (1100 -> 0100)
print(lowest_bit(7))   # 1  (111 -> 001)

原理：-n 是 n 的补码，n & (-n) 只保留最低位的 1

5. 反转二进制位

python 
def reverse_bits(n, bits=32):
    """反转整数的二进制位"""
    result = 0
    for i in range(bits):
        result = (result << 1) | (n & 1)
        n >>= 1
    return result

# 测试
print(reverse_bits(43261596))  # LeetCode 190 题

四、位运算的高级应用 🚀

1. 子集枚举

使用位掩码枚举集合的所有子集。

子集枚举 
def enumerate_subsets(nums):
    """
    枚举数组的所有子集
    :param nums: 输入数组
    :return: 所有子集的列表
    """
    n = len(nums)
    subsets = []
    
    # 枚举 0 到 2^n - 1 的所有数字
    for mask in range(1 << n):
        subset = []
        for i in range(n):
            # 检查第 i 位是否为 1
            if mask & (1 << i):
                subset.append(nums[i])
        subsets.append(subset)
    
    return subsets

# 测试
print(enumerate_subsets([1, 2, 3]))
# [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]

原理：每个数字的二进制表示对应一个子集，第 i 位为 1 表示选择 nums[i]

2. 位掩码动态规划

在某些 DP 问题中，使用位掩码表示状态可以大幅优化空间。

旅行商问题（TSP）简化版 
def tsp_bitmask(distances):
    """
    旅行商问题 - 位掩码 DP
    :param distances: 距离矩阵
    :return: 最短路径长度
    """
    n = len(distances)
    # dp[mask][i] 表示访问过的城市集合为 mask，当前在城市 i 的最短距离
    dp = [[float('inf')] * n for _ in range(1 << n)]
    
    # 初始状态：从城市 0 出发
    dp[1][0] = 0
    
    # 遍历所有状态
    for mask in range(1 << n):
        for u in range(n):
            if dp[mask][u] == float('inf'):
                continue
            
            # 尝试访问下一个未访问的城市
            for v in range(n):
                if mask & (1 << v):  # v 已经访问过
                    continue
                
                new_mask = mask | (1 << v)
                new_dist = dp[mask][u] + distances[u][v]
                dp[new_mask][v] = min(dp[new_mask][v], new_dist)
    
    # 找到回到起点的最短路径
    full_mask = (1 << n) - 1
    result = min(dp[full_mask][i] + distances[i][0] for i in range(n))
    
    return result

# 测试
distances = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0]
]
print(tsp_bitmask(distances))  # 80

空间优化：从 O(n! ) 降到 O(2ⁿ × n)

3. Bitmap 索引

使用位图进行高效的数据存储和查询。

python 
class BitSet:
    """位集合实现"""
    def __init__(self, size):
        self.size = size
        # 使用整数数组存储位
        self.bits = [0] * ((size + 31) // 32)
    
    def set(self, index):
        """设置某位为 1"""
        if 0 <= index < self.size:
            self.bits[index // 32] |= (1 << (index % 32))
    
    def clear(self, index):
        """设置某位为 0"""
        if 0 <= index < self.size:
            self.bits[index // 32] &= ~(1 << (index % 32))
    
    def get(self, index):
        """获取某位的值"""
        if 0 <= index < self.size:
            return (self.bits[index // 32] >> (index % 32)) & 1
        return 0
    
    def count(self):
        """统计 1 的个数"""
        return sum(bin(x).count('1') for x in self.bits)

# 测试
bs = BitSet(100)
bs.set(5)
bs.set(10)
bs.set(20)
print(bs.get(5))   # 1
print(bs.get(6))   # 0
print(bs.count())  # 3

应用：

4. 格雷码

格雷码是一种相邻数字只有一位不同的编码方式。

python 
def gray_code(n):
    """
    生成 n 位格雷码
    :param n: 位数
    :return: 格雷码序列
    """
    return [i ^ (i >> 1) for i in range(1 << n)]

# 测试
print(gray_code(2))  # [0, 1, 3, 2]
# 二进制: 00, 01, 11, 10（相邻只有一位不同）

应用：

五、位运算的性能优势 ⚡

速度对比

1 cycle
位运算
3-5 cycles
加减法
10+ cycles
乘除法
位运算速度基准100%
乘法相对速度30%

实际应用案例

案例一：游戏开发

案例二：网络协议

案例三：密码学

六、位运算的陷阱与注意事项 ⚠️

陷阱一：优先级问题

位运算符的优先级低于比较运算符！

错误示例：

python
if n & 1 == 0:  # 错误！先计算 1 == 0

正确写法：

python
if (n & 1) == 0:  # 正确

建议：总是给位运算加括号

陷阱二：符号位处理

对有符号数进行右移时，不同语言行为不同。

Python：算术右移（保持符号） C/C++：实现定义（可能是逻辑右移）

解决方案：使用无符号类型或手动处理

陷阱三：溢出问题

左移可能导致溢出。

python
# Python 自动处理大整数，不会溢出
print(1 << 100)  # 正常工作

# C/C++ 中需要小心
# int x = 1 << 31;  // 可能溢出！
技巧：位运算优化

常用优化：

  1. 用 x & 1 代替 x % 2
  2. 用 x << n 代替 x * (2^n)
  3. 用 x >> n 代替 x / (2^n)
  4. 用 x ^ y 交换变量

注意：现代编译器会自动优化，手动优化主要为了可读性

七、位运算 vs 其他方法 ⚖️

操作 位运算 常规方法 优势
奇偶判断 n & 1 n % 2 更快
2 的幂判断 n & (n-1) 循环除法 O(1)
交换变量 XOR 三次 临时变量 无额外空间
子集枚举 位掩码 递归 更简洁
集合操作 位运算 哈希表 更快、更省空间

何时使用位运算

八、练习与挑战 🏆

推荐练习题

LeetCode 136. 只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。 难度：⭐ 简单 使用异或运算

LeetCode 191. 位 1 的个数

编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 '1' 的个数。 难度：⭐ 简单 使用 n & (n-1) 技巧

LeetCode 78. 子集

给你一个整数数组，返回该数组所有可能的子集（幂集）。 难度：⭐⭐ 中等 可使用位掩码枚举

LeetCode 338. 比特位计数

给定一个非负整数 num，对于 0 ≤ i ≤ num 范围中的每个数字 i，计算其二进制数中的 1 的数目并将它们作为数组返回。 难度：⭐⭐ 中等 DP + 位运算

九、学习路径建议 🗺️

第1-3天
基础运算
掌握所有位运算符和基本性质。
第4-7天
经典技巧
学习常见位运算技巧和套路。
第8-10天
高级应用
研究位掩码 DP、Bitmap 等高级应用。
第11-14天
实战练习
完成至少 15 道 LeetCode 位运算题目。

十、总结 🎯

位运算是程序员的基本功，虽然现代开发中不常直接使用，但理解它能让你成为更好的程序员。

掌握位运算艺术

位运算看似简单，但蕴含深刻的计算机科学原理。继续探索，你会发现更多惊喜！

查看位运算专题练习 下载完整代码

© 2026 AI未来实验室 · 用 AI 探索无限可能
站点地图 | Robots.txt | 关于