C++位运算技巧详解

位运算通过操作二进制位提升效率，常用于算法竞赛与底层开发。C++支持6种位运算符：&（按位与）、|（按位或）、^（异或）、~（取反）、<<（左移）、>>（右移）。例如5 & 3 = 1，5 | 3 = 7，5 ^ 3 = 6，~5 = -6，5 << 1 = 10，5 >> 1 = 2。常用技巧包括：x & 1判断奇偶，x << n实现乘2^n，x >> n实现除2^n，a ^= b ^= a ^= b交换变量，x & (x - 1)清除最右1，x & (-x)提取最右1，(x & (x - 1)) == 0且x > 0判断2的幂。在状态压缩中，用整数mask表示集合，mask |= (1 << i)添加元素i，mask & (1 << i)检查元素i，mask ^= (1 << i)切换元素i状态，便于高效处理集合操作。

在C++中，位运算直接对整数的二进制位进行操作，效率高且常用于优化和底层编程。掌握这些技巧能提升代码性能，尤其在算法竞赛、嵌入式开发和状态压缩中非常实用。

基本位运算符及其作用

C++提供了6个基本的位运算符：

• &（按位与）：两个对应位都为1时结果才为1
• |（按位或）：任一对应位为1结果就为1
• ^（按位异或）：对应位不同时为1，相同时为0
• ~（按位取反）：每一位0变1，1变0（包括符号位）
• <<（左移）：左移n位相当于乘以2^n
• >>（右移）：右移n位相当于除以2^n（向下取整）

例如：

常用技巧与应用场景

位运算有很多巧妙用法，能简化逻辑并提高效率。

• 判断奇偶性：x & 1 == 1 表示奇数，等于0为偶数
• 快速乘除2的幂：x << n 相当于 x * (2^n)，x >> n 相当于 x / (2^n)
• 交换两个数不用临时变量：a ^= b; b ^= a; a ^= b;
• 清除最低位的1：x & (x - 1) 可以将最右边的1变为0，常用于统计1的个数
• 提取最低位的1：x & (-x) 得到只保留最右边1的结果
• 判断是否为2的幂：(x & (x - 1)) == 0 且 x > 0 时，x是2的幂

状态压缩与集合操作

位运算特别适合表示集合或状态，每个位代表一个元素是否存在。

• 用整数mask表示集合，第i位为1表示元素i被选中
• 添加元素i：mask |= (1 << i)
• 删除元素i：mask &= ~(1 << i)
• 检查元素i是否存在：mask & (1 << i)
• 枚举所有子集：for(int sub = mask; sub; sub = (sub - 1) & mask)

这类技巧广泛用于动态规划中的状态压缩（如旅行商问题）。

小技巧与注意事项

使用位运算时要注意数据类型和优先级。

• 位运算优先级低于算术运算，记得加括号，比如 (x << 1) + y
• 右移负数是实现定义行为，通常为算术右移（符号位扩展）
• 避免对有符号数进行左移导致溢出
• 使用unsigned类型更安全，尤其是在做位操作时
• 可以用bitset辅助调试和查看二进制形式

基本上就这些。熟练运用这些技巧，能让代码更简洁高效。关键是理解二进制本质，多练习常见模式。不复杂但容易忽略细节。