算法思想总结：位运算

基础篇：二进制与位运算基础

1.1 为什么需要位运算

在现代计算机体系结构中，数据以二进制（0和1）的形式存储和运算。位运算直接操作内存中的比特位，具有以下无可比拟的优势：

• 极致的速度：位运算对应CPU指令集（如AND, OR, XOR, SHIFT）的单个指令周期，比加减乘除快数倍甚至数十倍。

• 极低的内存占用：利用位掩码（Bitmask），一个int（32位）可以表示32种布尔状态，常用于状态压缩DP。

• 代码优雅性：某些复杂逻辑（如权限判断、奇偶性、2的幂判断）用位运算表达极其简洁。

• 硬件控制基础：嵌入式、驱动开发、网络协议栈（TCP/IP头）、加密算法（AES、RSA）的核心均依赖位运算。

1.2 二进制表示与原码、反码、补码

在深入位运算前，必须明确计算机中整数的存储方式。

• 原码：最高位为符号位（0正1负），其余位表示数值。

  • 例如：+5 = 0000 0101，-5 = 1000 0101。

  • 缺点：0有两种表示（0000 0000和1000 0000），且减法运算复杂。

• 反码：正数不变，负数符号位不变，其余位取反。

  • -5反码 = 1111 1010。

  • 缺点：0仍有两种表示，且加减运算需循环进位。

• 补码：现代计算机唯一采用的整数编码。

  • 正数：原码相同。

  • 负数：反码 +1。

  • -5补码 = 1111 1011。

  • 优点：

  • 统一加减法：A – B = A + (~B + 1)，减法器可复用加法器。

  • 唯一零：-0的补码表示为1 0000 0000，超出范围自动丢弃，最终0000 0000。

  • 范围对称：int8_t范围是-128 ~ 127，负数比正数多一个。

关键注意：在C/C++/Java中，有符号整数右移（>>）是算术右移（补符号位），无符号整数右移（>>>在Java中）是逻辑右移（补0）。Python的整数是无限精度的，右移模拟算术右移。

1.3 六大基础位运算符

假设A = 60 (二进制 0011 1100)，B = 13 (二进制 0000 1101)。

1.3.1 按位与 (&)

• 特性：X & 1 = X (保留最低位)，X & 0 = 0。

• 用途：清零特定位、取指定位、判断奇偶。

1.3.2 按位或 (|)

• 特性：X | 1 = 1 (强制设为1)，X | 0 = X。

• 用途：将某些位设为1。

1.3.3 按位异或 (^)

• 特性：

  • X ^ 0 = X

  • X ^ X = 0

  • X ^ Y ^ Y = X (自反性)

  • 满足交换律和结合律。

• 用途：无临时变量交换、寻找单身数字、简单的加密解密。

1.3.4 左移 (<<) 与 右移 (>>)

• 左移：相当于乘以2^n，但需注意溢出风险（C/C++中左移溢出未定义行为）。

• 右移：相当于除以2^n并向下取整（针对正数）。对于负数，不同语言实现不同。

1.4 位运算的优先级与常见误区

位运算的优先级通常低于算术运算符（+、-、*、/），但高于比较运算符（==、!=）和逻辑运算符（&&、||）。

常见错误：

c

// 错误：期望判断 (a & b) == 0，但实际解析为 a & (b == 0)
if (a & b == 0) { … }

// 正确：
if ((a & b) == 0) { … }

建议：在涉及混合运算时，使用括号明确优先级，不仅避免错误，也提高可读性。

进阶篇：经典位运算技巧

2.1 判断奇偶性

传统方法：n % 2 == 0。
位运算方法：(n & 1) == 0 为偶数，(n & 1) == 1 为奇数。

• 原理：二进制最低位（LSB）为1则为奇数，为0则为偶数。

• 性能：取模运算通常较慢，位运算快一个数量级。

2.2 交换两数（不使用临时变量）

c

int a = 5, b = 3;
a = a ^ b; // a = 5^3
b = a ^ b; // b = (5^3)^3 = 5
a = a ^ b; // a = (5^3)^5 = 3

• 原理：利用异或的自反性 a ^ b ^ b = a。

• 注意：当 a 和 b 指向同一内存地址时（如 swap(&a, &a)），会出错（值被清零）。在工程代码中，除非极度追求性能，否则不推荐使用（可读性差），但在算法面试中常出现。

2.3 消去二进制中的最后一个1 (x & (x-1))

这是最强大的技巧之一，用于将二进制中最右边的1变为0。

• 示例：x = 12 (1100)，x-1 = 11 (1011)，x & (x-1) = 1000 (8)。

• 应用：

• 统计二进制中1的个数：循环执行直到x变为0。

• 判断2的幂：如果 x & (x-1) == 0 且 x != 0，则 x 是2的幂。

• 计算x是2的多少次幂的变体：如求x的二进制表示中最低位1的权值。

2.4 获取最低位的1 (x & -x)

• 原理：-x在补码下等于~x + 1。x & -x 得到的结果是 x 的最低位1所代表的数值。

• 示例：x = 12 (1100)，-x = 0100 (补码)，1100 & 0100 = 0100 (4)。

• 应用：树状数组（Fenwick Tree）的lowbit函数、提取集合中的最小元素。

2.5 位掩码（Bitmask）与状态压缩

位掩码是利用一个整数的二进制位来表示集合状态的技术。

• 基本操作：

  • 空集：mask = 0

  • 添加元素i：mask |= (1 << i)

  • 删除元素i：mask &= ~(1 << i)

  • 检查元素i：(mask >> i) & 1 或 mask & (1 << i)

  • 切换元素i：mask ^= (1 << i)

  • 集合大小：__builtin_popcount(mask) (GCC) 或 Integer.bitCount(mask) (Java)

• 状态压缩DP：当状态维度较少（通常n <= 20）时，可以将每个元素“选/不选”的状态压缩成一个整数，作为DP的维度。

  • 经典问题：TSP问题（旅行商问题），DP[mask][u] 表示访问过 mask 集合中的城市，最后在 u 的最短路径。

2.6 异或运算的四大定律与应用

异或是位运算中最具数学美感的操作，遵循以下定律：

衍生应用：

• 出现奇数次的数字：在一个数组中，只有一个数字出现奇数次，其余均出现偶数次，求该数字。遍历异或即可。

• 无临时变量交换：已介绍。

• 格雷码（Gray Code）：相邻两个数的二进制只有一位不同。生成公式：n ^ (n >> 1)。

• 简单的对称加密：

  • 加密：cipher = plain ^ key

  • 解密：plain = cipher ^ key

实战篇：LeetCode高频题解

3.1 基础题型

136. 只出现一次的数字

题目：给定一个非空整数数组，除了某个元素只出现一次外，其余每个元素均出现两次。找出那个只出现一次的元素。

思路：利用异或的归零律和恒等律。遍历所有数字，进行异或运算，最终结果即为落单的数字。

python

def singleNumber(nums):
res = 0
for num in nums:
res ^= num
return res

复杂度：时间O(n)，空间O(1)。

191. 位1的个数

题目：编写一个函数，输入是一个无符号整数，返回其二进制表示中数字位数为 '1' 的个数。

解法一：逐位检查（右移）

python

def hammingWeight(n):
count = 0
while n:
count += n & 1
n >>= 1
return count

解法二：n & (n-1) 优化（跳过0位）

python

def hammingWeight(n):
count = 0
while n:
n &= (n – 1) # 消去最低位的1
count += 1
return count

内置方法：bin(n).count('1') 或 n.bit_count() (Python 3.8+)。

231. 2的幂

题目：给定一个整数，编写一个函数来判断它是否是 2 的幂次方。

思路：

python

def isPowerOfTwo(n):
return n > 0 and (n & (n – 1)) == 0

3.2 中等题型

260. 只出现一次的数字 III

题目：给定一个整数数组，其中恰好有两个元素只出现一次，其余所有元素均出现两次。找出只出现一次的那两个元素。

思路：

python

def singleNumber(nums):
diff = 0
for num in nums:
diff ^= num
# 获取最低位的1
mask = diff & -diff
a, b = 0, 0
for num in nums:
if num & mask:
a ^= num
else:
b ^= num
return [a, b]

338. 比特位计数

题目：给定一个非负整数 n，对于 0 ≤ i ≤ n，计算每个数字二进制中 1 的个数，返回一个数组。

思路：动态规划 + 位运算。

• DP 公式：dp[i] = dp[i >> 1] + (i & 1)。

  • i >> 1 相当于去掉最低位，(i & 1) 是判断最低位是否为1。

• DP 公式二：dp[i] = dp[i & (i-1)] + 1。

python

def countBits(n):
dp = [0] * (n + 1)
for i in range(1, n + 1):
dp[i] = dp[i >> 1] + (i & 1)
return dp

371. 两整数之和

题目：不使用运算符 + 和 -，计算两整数之和。

思路：利用位运算模拟加法器。

• 注意：Python 整数无溢出，需要模拟32位有符号整数的截断（& 0xFFFFFFFF）。

python

def getSum(a, b):
# 32位掩码
mask = 0xFFFFFFFF
while b != 0:
carry = (a & b) & mask
a = (a ^ b) & mask
b = (carry << 1) & mask
# 如果a是负数（超过32位有符号范围），转换
return a if a <= 0x7FFFFFFF else ~(a ^ mask)

3.3 困难题型

85. 最大矩形（结合位运算优化）

题目：给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

常规解法：柱状图法（单调栈），复杂度 O(m * n)。
位运算优化解法：

982. 按位与为零的三元组

题目：给定一个整数数组 A，找出满足 (A[i] & A[j] & A[k]) == 0 的三元组个数。

思路：

python

def countTriplets(A):
freq = [0] * (1 << 16)
n = len(A)
for i in range(n):
for j in range(n):
freq[A[i] & A[j]] += 1
res = 0
for k in range(n):
val = A[k]
# 枚举 complement 的子集
complement = (~val) & ((1 << 16) – 1)
sub = complement
while True:
res += freq[sub]
if sub == 0:
break
sub = (sub – 1) & complement
return res

高阶篇：系统底层与工程应用

4.1 快速幂与快速乘法

快速幂（Exponentiation by squaring）利用二进制分解指数，将 O(n) 的乘法次数降至 O(log n)。

• 快速幂（模意义下）：

python

def pow_mod(a, b, mod):
res = 1
base = a % mod
while b > 0:
if b & 1: # 如果当前二进制位是1
res = (res * base) % mod
base = (base * base) % mod
b >>= 1
return res

• 快速乘（防止溢出）：类似原理，将加法代替乘法，用于大数乘法取模。

4.2 布隆过滤器（Bloom Filter）

布隆过滤器是一种空间效率极高的概率性数据结构，用于判断一个元素是否在集合中。

原理：

位运算角色：布隆过滤器的底层存储就是位掩码，设置位（bits[hash] = 1）和检查位（bits[hash] & 1）均依赖位运算。
应用：防止缓存穿透（Redis）、恶意URL过滤、数据库查询优化。

4.3 内存对齐与位域（Bit Fields）

在C/C++系统编程中，位域（Bit Fields）允许开发者精确控制结构体的内存布局，按位分配存储空间。

c

struct DeviceConfig {
unsigned int enabled : 1; // 占用1位
unsigned int mode : 2; // 占用2位
unsigned int speed : 4; // 占用4位
unsigned int : 1; // 无名位域，填充对齐
};

• 作用：节省内存、直接映射硬件寄存器。

• 位运算关联：编译底层即转化为位移和掩码操作。

4.4 权限系统设计（RBAC 位运算实现）

在中小型系统的权限设计中，使用位掩码可以极简地实现权限的组合与判断。

设计：

• 定义权限枚举（2的幂）：

  • CREATE = 1 << 0 (1)

  • READ = 1 << 1 (2)

  • UPDATE = 1 << 2 (4)

  • DELETE = 1 << 3 (8)

• 角色权限：

  • ADMIN = CREATE | READ | UPDATE | DELETE (15)

  • USER = READ (2)

• 判断权限：

  • if (user_permission & required_perm)

• 授予权限：

  • user_permission |= perm

• 撤销权限：

  • user_permission &= ~perm

优点：单字段存储，数据库查询友好，且权限组合无数量限制（32位系统最多32种权限）。

总结：位运算的思维模型

位运算不仅是算法竞赛的“神器”，更是连接软件与硬件的桥梁。从最简单的奇偶判断，到复杂的 CPU 指令优化，再到庞大的分布式系统（如 Bloom Filter），位运算无处不在。希望这篇 2 万字的详解能帮助你建立完整的位运算知识体系，在算法学习和工程实践中游刃有余。

附录：常用位运算速查表