位运算是信息学奥赛中非常重要的知识点，因为它在解决某些问题时非常高效。

一、基本位运算符

C++提供了6种位运算符：

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

二、运算符详解与示例

1. 按位与 (&)

规则：两个位都为1时，结果才为1

int a = 5;    // 0101
int b = 3;    // 0011
int c = a & b; // 0001 (1)

常用场景：

• 判断奇偶：n & 1（结果为1是奇数，0是偶数）
• 取特定位：n & 0xFF（取最低8位）

2. 按位或 (|)

规则：两个位有一个为1时，结果就为1

int a = 5;    // 0101
int b = 3;    // 0011
int c = a | b; // 0111 (7)

常用场景：

• 设置特定位为1

3. 按位异或 (^)

规则：两个位不同时结果为1，相同时为0

int a = 5;    // 0101
int b = 3;    // 0011
int c = a ^ b; // 0110 (6)

重要性质：

• a ^ a = 0
• a ^ 0 = a
• 满足交换律和结合律

常用场景：

• 交换两个数：a ^= b; b ^= a; a ^= b;
• 找唯一不重复的数字（其他数字都出现两次）

4. 按位取反 (~)

规则：0变1，1变0

int a = 5;    // 0101
int b = ~a;   // 1010 (补码表示，实际值为-6)

5. 左移 (<<)

规则：所有位向左移动，低位补0

int a = 5;     // 0101
int b = a << 1; // 1010 (10)

性质：

• 相当于乘以2的n次方（无溢出时）
• a << n = a × 2ⁿ

6. 右移 (>>)

规则：所有位向右移动，高位补符号位（算术右移）

int a = 6;     // 0110
int b = a >> 1; // 0011 (3)

性质：

• 相当于除以2的n次方（向下取整）
• a >> n = a ÷ 2ⁿ

三、常考应用场景

1. 判断第n位是否为1

bool isBitSet(int num, int pos) {
    return num & (1 << pos);
}

2. 设置第n位为1

int setBit(int num, int pos) {
    return num | (1 << pos);
}

3. 设置第n位为0

int clearBit(int num, int pos) {
    return num & ~(1 << pos);
}

4. 切换第n位（1变0，0变1）

int toggleBit(int num, int pos) {
    return num ^ (1 << pos);
}

5. 统计二进制中1的个数

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

6. 判断是否是2的幂

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

四、注意事项

1. 位运算符优先级较低，建议多用括号
2. 移位运算不要移动负数位或超过类型位数
3. 无符号数和有符号数的右移行为不同
4. 位运算常用于状态压缩，如用二进制表示集合