引言

位运算是计算机底层最基础的操作，直接操作二进制位（0 和 1）。尽管现代编程语言提供了高级抽象，但理解位运算的本质能显著提升代码效率和解决特定问题的能力。本文将深入探讨位运算的核心原理、常见技巧及其实际应用场景。

一、位运算的本质：二进制视角

所有位运算都基于二进制数的逐位操作。以下是六种基本操作：

1. 与（AND） &

   • 规则：两位均为 1 时结果为 1，否则为 0。
   • 示例：1010 & 1100 = 1000
   • 本质：掩码操作（保留/清除特定位）。

2. 或（OR） |

   • 规则：任意一位为 1 时结果为 1。
   • 示例：1010 | 1100 = 1110
   • 本质：组合标志位（如权限合并）。

3. 异或（XOR） ^

   • 规则：两位不同时结果为 1，否则为 0。
   • 示例：1010 ^ 1100 = 0110
   • 本质：开关特性（两次异或还原原值）。

4. 非（NOT） ~

   • 规则：按位取反。
   • 示例：~1010 = 0101（假设 4 位）
   • 本质：数值取反（~x = -(x+1)）。

5. 左移（SHL） <<

   • 规则：二进制位向左移动，低位补 0。
   • 示例：1010 << 2 = 101000
   • 本质：乘以 (2^n)（无溢出时）。

6. 右移（SHR） >>

   • 规则：二进制位向右移动，高位补符号位（算术右移）或 0（逻辑右移）。
   • 示例：1010 >> 2 = 0010（逻辑右移）
   • 本质：除以 (2^n)（向下取整）。

二、位运算的实用技巧

1. 判断奇偶性

   csharp
   bool isOdd = (num & 1) == 1; // 末位为 1 则为奇数  
   

2. 交换两个数（无临时变量）

   csharp
   a ^= b; // a = a ^ b  
   b ^= a; // b = b ^ (a ^ b) = a  
   a ^= b; // a = (a ^ b) ^ a = b  
   

3. 求绝对值（整数）

   csharp
   int mask = num >> 31; // 负数得全1，正数得0  
   int abs = (num ^ mask) - mask; // 负数取反加1  
   

4. 检查第 k 位是否为 1

   csharp
   bool isSet = (num & (1 << k)) != 0;  
   

三、实际应用场景

1. 状态压缩

   • 场景：用单个整数表示布尔集合（如背包问题、子集枚举）。
   • 示例：用 bitmask 表示开关状态：

     csharp
     int state = 0;  
     state |= (1 << 3); // 打开第3位  
     state &= ~(1 << 3); // 关闭第3位  
     

2. 高效数学计算

   • 乘法模拟：a * 7 = a << 3 - a（因 (7 = 8-1)）。
   • 2的幂判断：(n & (n-1)) == 0（如 8 & 7 = 0）。

3. 数据加密

   • 简单加密：通过异或密钥实现快速加解密：

     csharp
     byte encrypted = data ^ key;  
     byte decrypted = encrypted ^ key; // 还原  
     

4. 位图（Bitmap）

   • 场景：海量数据去重（如 40 亿整数中找重复值）。
   • 原理：用 1 位表示一个数是否存在，内存占用仅为传统数组的 1/32。

四、注意事项

1. 运算符优先级：位运算优先级低于算术运算，建议多用括号：

   csharp
   int result = (a & b) << 2; // 避免歧义  
   

2. 位移边界

   • 左移丢弃高位，右移丢弃低位。
   • 避免位移位数超过数据类型宽度（如 int << 32 未定义）。

3. 有符号数处理

   • 算术右移（>>）保留符号位，逻辑右移（>>>）补 0（C# 用 >>>）。

结语

位运算将复杂问题转化为底层二进制操作，在算法优化、系统编程等领域至关重要。掌握其本质后，可灵活应用于性能敏感场景（如游戏引擎、嵌入式系统）。后续文章将探讨位运算在算法题中的实战技巧。