【位运算】常见算法公式使用

1. 基本位运算符

运算符	描述	示例（二进制）
&	按位与	1010 & 1100 = 1000
|	按位或	1010 | 1100 = 1110
^	按位异或	1010 ^ 1100 = 0110
~	按位取反	~1010 = 0101（结果依赖位数）
<<	左移	1010 << 2 = 101000
>>	右移（算术/逻辑）	1010 >> 2 = 0010（逻辑右移）

---

2. 常见位运算技巧

① 判断奇偶

• x & 1：结果为 1 是奇数，0 是偶数。

② 交换两个数

• 不用临时变量：

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

③ 取最低位的 1

• x & (-x)：获取二进制中最右边的 1（如 1010 → 0010）。

④ 清除最低位的 1

• x & (x - 1)：将最右边的 1 置 0（如 1010 → 1000）。

  • 应用：统计二进制中 1 的个数：

    int count = 0;
    while (x) {x &= (x - 1);count++;
    }

⑤ 判断是否为 2 的幂

• x & (x - 1) == 0：若为 true，则 x 是 2 的幂（如 1000）。

⑥ 确定某一位是 0 还是 1

int getBit(int num, int x) {return (num >> x) & 1;  // 将第 x 位移到最低位后取末位
}

⑦ 将某一位修改为 1

int setBit(int num, int x) {return num | (1 << x);  // 用或操作设置第 x 位
}

⑧ 将某一位修改为 0

int clearBit(int num, int x) {return num & ~(1 << x);  // 用与操作清零第 x 位
}