位運算完全指南：核心口訣、常用技巧與實戰範例

位運算核心口訣

清零取反要用與，某位置一可用或
若要取反和交換，輕輕鬆鬆用異或

移位運算要點

• 左移 <<：右側補0，左側位丟棄，等價於乘2
• 右移 >>：右側位丟棄，正數左側補0，負數視系統而定（算術/邏輯右移）
• 無符號右移 >>>：左側一律補0（Java等語言特有）

三大位運算符應用模式

補碼運算恆等式

-x = ~x + 1 = ~(x-1)
~x = -x - 1
x + y = (x | y) + (x & y)
x - y = (x | ~y) - (~x & y)
x ^ y = (x | y) - (x & y)

經典實戰技巧

1. 判斷奇偶

a & 1 == 0  // 偶數
a & 1 == 1  // 奇數

2. 取第k位

(a >> k) & 1

3. 清零/置1/翻轉第k位

a &= ~(1 << k)  // 清零
a |= (1 << k)     // 置1
a ^= (1 << k)     // 翻轉

4. 循環移位 (16-bit例)

// 左循環 k 位
a = (a << k) | (a >> (16-k))

// 右循環 k 位
a = (a >> k) | (a << (16-k))

5. 安全求平均值 (避免溢位)

int average(int x, int y) {
    return (x & y) + ((x ^ y) >> 1);
}

6. 判斷2的冪次

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

7. 無暫存變數交換

x ^= y; y ^= x; x ^= y;

8. 位運算替代乘除模 (2的冪次)

a * (2^n)  →  a << n
a / (2^n)  →  a >> n
a % (2^n)  →  a & (2^n - 1)

進階位運算技巧表

實戰範例：計算區間內1的個數

public static int countOnesInRange(int highBit, int lowBit, ushort value) {
    int count = 0;
    for (int i = lowBit; i <= highBit; i++) {
        count += ((value >> (i - 1)) & 1);
    }
    return count;
}