位运算

位运算（bitwise operations）是所有算法和底层逻辑的核心之一。

🧩 一、什么是位运算？

计算机底层存储的所有数据都是二进制的 0 和 1。
位运算就是直接对这些二进制位（bit）进行操作的运算。

它的好处是：

• ⚡ 极快（比普通加减乘除还快）
• 💡 可以高效实现一些数学逻辑、掩码、集合、状态压缩、DP 等技巧
• 💪 很多算法题和面试题都用它（如 位计数、子集生成、奇偶判断、异或和）

---

⚙️ 二、常见位运算符

运算	符号	含义	示例
按位与	&	两个位都为 1 才为 1	6 & 3 = 2 (110 & 011 = 010)
按位或	|	有一个为 1 就为 1	6 | 3 = 7 (110 | 011 = 111)
按位异或	^	相同为 0，不同为 1	6 ^ 3 = 5 (110 ^ 011 = 101)
按位取反	~	0→1，1→0（符号位也反）	~6 = -7（在补码中解释）
左移	<<	所有位左移，右边补 0	3 << 1 = 6 (11 → 110)
右移	>>	所有位右移，符号位补	6 >> 1 = 3 (110 → 11)
无符号右移	>>>	右移，左边补 0	-1 >>> 1 = 2147483647

---

📘 三、常见技巧与应用

1️⃣ 判断奇偶

if ((x & 1) == 0) // 偶数
if ((x & 1) == 1) // 奇数

因为二进制最后一位为 1 表示奇数。

---

2️⃣ 乘除 2 的幂（高效版）

x << 1   // 相当于 x * 2
x >> 1   // 相当于 x / 2
x << k   // 相当于 x * 2^k
x >> k   // 相当于 x / 2^k

⚠️ 注意：右移是向下取整（丢弃小数部分）。

---

3️⃣ 清除最低位的 1

x = x & (x - 1);

👉 这个操作会 把 x 的二进制中最右边的那个 1 变成 0。

举例：

x = 1100 (12)
x-1 = 1011 (11)
x & (x-1) = 1000 (8)

用途：

• 统计 1 的个数
• 子集枚举
• 最低位分析（比如 countBits）

---

4️⃣ 提取最低位的 1

lowbit = x & (-x);

举例：

x = 1100 (12)
-x = 0100 (补码)
x & (-x) = 0100 (4)

👉 这个结果就是「最低位的 1」对应的值。
在 树状数组（Fenwick Tree）、子集状态压缩、位掩码 DP 中都非常常用。

---

5️⃣ 翻转某一位

如果想把第 k 位翻转：

x ^= (1 << k);

例：

x = 1010
k = 1
→ 1010 ^ 0010 = 1000

---

6️⃣ 置 1 或 清 0 某一位

// 置 1
x |= (1 << k);

// 清 0
x &= ~(1 << k);

---

7️⃣ 判断某一位是否为 1

if ((x >> k & 1) == 1)

---

8️⃣ 统计二进制中 1 的个数（手动版）

int count = 0;
while (x > 0) {
    x &= (x - 1); // 每次消掉最低的 1
    count++;
}

时间复杂度 O(1 的个数)，比逐位判断快多了。

---

9️⃣ 异或的特殊性质

异或（^）是位运算中最有“魔法”的操作，常用于：

• 去重
• 加密
• 不用额外空间交换变量

常见性质：

a ^ 0 = a
a ^ a = 0
a ^ b ^ a = b   // 可交换、可抵消

示例：

// 不用临时变量交换
a = a ^ b;
b = a ^ b;
a = a ^ b;

---

🔟 子集枚举技巧（超常用）

在很多「集合 DP」或「子集和」问题中，用 bitmask 表示集合：

int mask = 0b1011; // 表示集合 {0,1,3}

for (int sub = mask; sub > 0; sub = (sub - 1) & mask) {
    System.out.println(Integer.toBinaryString(sub));
}

这个循环能枚举出 mask 的所有 非空子集。

---

🧠 四、位运算与 DP 的结合（典型例子）

在 countBits 题中：

dp[i] = dp[i >> 1] + (i & 1);

表示：

• i >> 1 去掉最低位；
• (i & 1) 判断最低位是不是 1；
• 所以 i 的 1 数量 = “i/2 的 1 数量 + 最低位是否为 1”。

或者：

dp[i] = dp[i & (i - 1)] + 1;

表示：

• i & (i - 1) 去掉最低位的 1；
• 所以只要在“少一个 1 的状态”上 +1。

---

🧩 五、总结口诀

功能	位运算技巧
判断奇偶	x & 1
乘除 2^k	x << k, x >> k
清除最低位的 1	x &= (x - 1)
提取最低位的 1	x & -x
翻转第 k 位	x ^= (1 << k)
置第 k 位为 1	`x	= (1 << k)`
清第 k 位为 0	x &= ~(1 << k)
判断第 k 位	(x >> k) & 1