C++ 位运算基础及巧算技巧

1. 基础位运算符

& 按位与 a & b 两位都为1才为1

| 按位或 a | b 至少一位为1则为1

^ 按位异或 a ^ b 相同为0，不同为1

~ 按位取反 ~a 0变1，1变0

<< 左移 a << n 左移n位，低位补0

">>" 右移 a >> n 右移n位，高位补符号位

2. 常用技巧（巧算）

2.1 判断奇偶性

// 传统: n % 2 == 0
// 位运算: 
bool isEven = (n & 1) == 0;   // 偶数
bool isOdd = (n & 1) == 1;    // 奇数
2.2 乘除2的幂
cpp
int x = 5;
x << 1;   // 乘以2 → 10
x << 3;   // 乘以8 → 40
x >> 1;   // 除以2 → 2（整数除法）

2.3 交换两个数

int a = 5, b = 3;
a ^= b;
b ^= a;
a ^= b;
// 结果: a=3, b=5

2.4 判断符号是否相同

bool sameSign = (x ^ y) >= 0;  // 相同返回true

2.5 取绝对值

int abs(int x) {
    int mask = x >> 31;        // 获取符号位
    return (x + mask) ^ mask;
}

2.6 求相反数

int negate(int x) {
    return ~x + 1;  // 补码取反加1
}

2.7 统计1的位数（Brian Kernighan算法）

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

2.8 获取/设置/清除某一位

// 获取第k位（0-indexed）
int getBit(int n, int k) {
    return (n >> k) & 1;
}

// 设置第k位为1
int setBit(int n, int k) {
    return n | (1 << k);
}

// 清除第k位（设为0）
int clearBit(int n, int k) {
    return n & ~(1 << k);
}

// 翻转第k位
int toggleBit(int n, int k) {
    return n ^ (1 << k);
}

2.9 判断2的幂

bool isPowerOfTwo(int n) {
    return n > 0 && (n & (n - 1)) == 0;
}

2.10 低/高位掩码

// 获取低n位
int lowMask = (1 << n) - 1;

// 获取高n位（32位系统）
int highMask = (~0) << (32 - n);

2.11 枚举子集

// 枚举mask的所有子集
int subset = mask;
do {
    // 处理子集
    subset = (subset - 1) & mask;
} while (subset != mask);

3. 实战示例

#include <iostream>
using namespace std;

int main() {
    // 快速计算2的10次方
    int pow2_10 = 1 << 10;  // 1024
    
    // 取模2的幂（替代取模运算）
    int mod = 15 & (8 - 1);  // 15 % 8 = 7
    
    // 大小写转换（ASCII）
    char lower = 'a';
    char upper = lower & ~0x20;  // 'A'
    
    // 获取最低位的1
    int x = 12;  // 1100
    int lowbit = x & -x;  // 100 (4)
    
    cout << "lowbit of 12: " << lowbit << endl;
    
    return 0;
}

4. 性能优势 速度：位运算通常比乘除、取模快10-30倍

内存：可用int作为bitset存储32个布尔值

原子性：位运算是CPU原子操作

5. 注意事项

⚠️ 右移负数：C++中右移负数是实现定义的，尽量避免

⚠️ 溢出：左移可能产生未定义行为（如1 << 31）

⚠️ 优先级：位运算优先级低于算术运算，注意加括号

掌握这些技巧可以写出更高效的C++代码，尤其在算法竞赛和嵌入式开发中非常实用。