掌握C++位操作高级技巧（从入门到精通的位运算优化指南）

一、位运算基础回顾

C++提供了以下基本位运算符：

• &：按位与（AND）
• |：按位或（OR）
• ^：按位异或（XOR）
• ~：按位取反（NOT）
• <<：左移
• >>：右移

例如，5 & 3 的结果是 1，因为二进制 101 & 011 = 001。

二、常用位操作技巧

1. 判断奇偶数

使用最低位判断奇偶：

bool isOdd(int n) {    return (n & 1) == 1;}

比 n % 2 更快！这是典型的位运算优化案例。

2. 设置/清除/翻转特定位

假设我们要操作第 k 位（从0开始）：

// 设置第k位为1x |= (1 << k);// 清除第k位（设为0）x &= ~(1 << k);// 翻转第k位x ^= (1 << k);

3. 检查某位是否为1

bool isSet(int x, int k) {    return (x & (1 << k)) != 0;}

三、高级技巧：位掩码（Bitmask）应用

位掩码是用一个整数的每一位表示某种状态，常用于状态压缩、权限控制、子集枚举等场景。

1. 枚举所有子集

void enumerateSubsets(int n) {    // n 表示有 n 个元素    for (int mask = 0; mask < (1 << n); ++mask) {        std::cout << "Subset: ";        for (int i = 0; i < n; ++i) {            if (mask & (1 << i)) {                std::cout << i << " ";            }        }        std::cout << "\n";    }}

2. 快速计算二进制中1的个数（Brian Kernighan算法）

int countSetBits(int n) {    int count = 0;    while (n) {        n &= (n - 1); // 清除最低位的1        count++;    }    return count;}

这个技巧在处理位掩码应用时非常高效。

四、实战：用位运算实现快速幂

快速幂算法利用二进制分解指数，时间复杂度从 O(n) 降到 O(log n)：

long long fastPower(long long base, long long exp) {    long long result = 1;    while (exp > 0) {        if (exp & 1) {          // 如果当前位是1            result *= base;        }        base *= base;        exp >>= 1;              // 右移一位，相当于除以2    }    return result;}

这正是C++高级位运算在算法中的经典体现。

五、注意事项与最佳实践

• 对有符号整数进行右移时，行为依赖于编译器（算术右移 vs 逻辑右移），建议使用无符号类型如 uint32_t。
• 避免对负数进行位操作，除非你完全理解其补码表示。
• 使用 std::bitset 可提高代码可读性（但可能牺牲一点性能）。

结语

掌握C++位操作技巧不仅能让你写出更高效的代码，还能在面试和竞赛中脱颖而出。通过本文的学习，你已经了解了从基础到高级的多种位运算方法。记住：位运算是工具，合理使用才能发挥最大价值。

关键词回顾：C++位操作技巧、位运算优化、C++高级位运算、位掩码应用。