位運算（Bitwise Operation）是直接對整數的二進制位進行操作的運算方式，在底層開發、性能優化、算法設計中廣泛使用。

---

1 基本位運算符及含義

運算符	名稱	示例（a=5, b=3）	運算過程（二進制）	結果
&	按位與	a & b = 1	0101 & 0011 = 0001	1
|	按位或	a | b = 7	0101 | 0011 = 0111	7
^	按位異或	a ^ b = 6	0101 ^ 0011 = 0110	6
~	按位取反	~a = -6	~0101 = 1010（補碼）	-6
<<	左移	a << 1 = 10	0101 << 1 = 1010	10
>>	右移	a >> 1 = 2	0101 >> 1 = 0010	2

---

2 常見用途

1. 判斷奇偶數

bool isOdd = (x & 1);  // 最低位為1是奇數

2. 清除最低位的1

x = x & (x - 1);  // 常用于統計1的個數

3. 統計一個數的二進制中1的個數（Brian Kernighan 算法）

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

4. 交換兩個變量（不使用臨時變量）

a ^= b;
b ^= a;
a ^= b;

5. 判斷某一位是否為1

bool isSet = (x & (1 << k));  // 判斷第 k 位是否為1

6. 設置/清除/翻轉某一位

x |= (1 << k);     // 設置第k位為1
x &= ~(1 << k);    // 清除第k位
x ^= (1 << k);     // 翻轉第k位

7. 將整數轉換為2的倍數（高效乘以2、除以2）

x << 1  // 相當于 x * 2
x >> 1  // 相當于 x / 2

8. 判斷是否為2的冪

bool isPowerOfTwo = (x > 0) && ((x & (x - 1)) == 0);

9. XOR 找不同元素（如只出現一次的數）

int result = 0;
for (int num : nums) {result ^= num;
}

10. 位掩碼（Bitmask）處理狀態組合

int state = 0;
state |= (1 << 2);    // 設置第2位表示某功能啟用
bool enabled = state & (1 << 2);

11. 得到最低有效位1

unsigned a = 12; // 1100
unsigned t = a & (-a); // 0b1100 & 0b0100 = 0b100

---

3 擴展技巧

• 最大/最小值冪（向上取最近2的冪）

unsigned int nextPowerOfTwo(unsigned int x) {if (x == 0) return 1;--x;x |= x >> 1;x |= x >> 2;x |= x >> 4;x |= x >> 8;x |= x >> 16;return x + 1;
}

• 子集枚舉

for (int subset = mask; subset; subset = (subset - 1) & mask) {// 枚舉 mask 的所有子集
}

---

4 位運算的優勢

• 高性能：CPU 原生命令，速度極快；
• 節省空間：可以用位表示多個布爾狀態；
• 用于狀態壓縮與組合計算；
• 應用廣泛：位圖、哈希、圖算法、壓縮、圖形、嵌入式、權限控制等。