Bit Manipulation

心得寫在前頭

Bit Manipulation 對於一般軟體工程師的面試不太常出現。

我在準備 SDE 的面試時，通常會直接放掉 Bit Manipulation 的題目，你可以斟酌要不要加強這一塊內容的知識。

位元運算（Bit Manipulation）是直接對數字的二進位表示進行操作的技巧。因為是硬體層級的運算，速度極快，常被用來節省記憶體空間、加速運算，或是解決一些用「數學角度」很難想到、但從「二進位角度」一看就懂的問題。

白話理解

電腦裡的每個整數，本質上都是一串 0 與 1 組成的「開關」。位元運算就是直接去撥動這些開關，而不是像平常一樣用加減乘除去計算數字本身。

基本觀念：二進位表示

十進位的 13，用二進位表示是 1101（也就是 8 + 4 + 0 + 1）。

十進位 13 = 二進位 1101
                 ↑↑↑↑
                 8421   （由左到右，每一位代表 2 的次方）

常見運算子

運算子	名稱	範例	說明
`&`	AND	`5 & 3` → `1`	兩個位元都是 1，結果才是 1（`101 & 011 = 001`）
`\|`	OR	`5 \| 3` → `7`	兩個位元只要有一個是 1，結果就是 1（`101 \| 011 = 111`）
`^`	XOR（互斥或）	`5 ^ 3` → `6`	兩個位元不同才是 1，相同則是 0（`101 ^ 011 = 110`）
`~`	NOT	`~5` → `-6`	把每一位都反過來（0 變 1、1 變 0）
`<<`	左移	`5 << 1` → `10`	所有位元往左移一位，等於乘以 2
`>>`	右移	`5 >> 1` → `2`	所有位元往右移一位，等於整數除以 2（無條件捨去）

注意

&、| 是位元運算子，&&、|| 是邏輯運算子，兩者外觀相似但用途完全不同，千萬不要搞混。

位元運算子是對數字的每一個 bit 做運算，邏輯運算子則是對整個布林值（true / false）做判斷。

常見技巧

1. 判斷奇偶

Python
JavaScript
Java

def is_odd(n):
    return (n & 1) == 1  # 二進位最後一位是 1，代表是奇數

function isOdd(n) {
  return (n & 1) === 1; // 二進位最後一位是 1，代表是奇數
}

class BitManipulation {
    static boolean isOdd(int n) {
        return (n & 1) == 1; // 二進位最後一位是 1，代表是奇數
    }
}

2. 取得 / 設定 / 清除某一位元

Python
JavaScript
Java

def get_bit(n, i):
    return (n >> i) & 1  # 把第 i 位移到最後面，再用 &1 只看那一位

def set_bit(n, i):
    return n | (1 << i)  # 把第 i 位強制設成 1，其他位元不受影響

def clear_bit(n, i):
    return n & ~(1 << i)  # 把第 i 位強制設成 0，其他位元不受影響

function getBit(n, i) {
  return (n >> i) & 1; // 把第 i 位移到最後面，再用 &1 只看那一位
}

function setBit(n, i) {
  return n | (1 << i); // 把第 i 位強制設成 1，其他位元不受影響
}

function clearBit(n, i) {
  return n & ~(1 << i); // 把第 i 位強制設成 0，其他位元不受影響
}

class BitManipulation {
    static int getBit(int n, int i) {
        return (n >> i) & 1; // 把第 i 位移到最後面，再用 &1 只看那一位
    }

    static int setBit(int n, int i) {
        return n | (1 << i); // 把第 i 位強制設成 1，其他位元不受影響
    }

    static int clearBit(int n, int i) {
        return n & ~(1 << i); // 把第 i 位強制設成 0，其他位元不受影響
    }
}

3. 用 XOR 找出「唯一不重複」的數字

XOR 有兩個很好用的特性：a ^ a = 0（自己異或自己會歸零），a ^ 0 = a（跟 0 異或不變）。

題目：Leetcode: Single Number，陣列中除了一個數字只出現一次，其他數字都出現兩次，找出那個只出現一次的數字。

Python
JavaScript
Java

def single_number(nums):
    result = 0
    for num in nums:
        result ^= num  # 成對出現的數字，互相 XOR 後都會變成 0
    return result  # 最後剩下的，就是只出現一次的那個數字

function singleNumber(nums) {
  let result = 0;
  for (const num of nums) {
    result ^= num; // 成對出現的數字，互相 XOR 後都會變成 0
  }
  return result; // 最後剩下的，就是只出現一次的那個數字
}

class Solution {
    public int singleNumber(int[] nums) {
        int result = 0;
        for (int num : nums) {
            result ^= num; // 成對出現的數字，互相 XOR 後都會變成 0
        }
        return result; // 最後剩下的，就是只出現一次的那個數字
    }
}

逐步拆解：以 `nums = [4, 1, 2, 1, 2]` 為例

步驟	運算	result
初始	-	0
遇到 4	`0 ^ 4`	4
遇到 1	`4 ^ 1`	5
遇到 2	`5 ^ 2`	7
遇到 1	`7 ^ 1`	6
遇到 2	`6 ^ 2`	4

最後 result = 4，正是唯一只出現一次的數字。因為 1 出現兩次，兩次 XOR 會互相抵銷（... ^ 1 ^ ... ^ 1 部分相當於沒異或過），2 也是同樣道理，只有 4 沒有被抵銷，會被保留到最後。全程只需要 O(n) 時間、O(1) 額外空間，比用 Hash Table 記錄出現次數還省空間。

4. `n & (n - 1)`：消去最低位的 1

這個技巧可以把一個數字最右邊的 1，直接變成 0，常用來計算「二進位中有幾個 1」，或判斷一個數字是不是 2 的冪。

Python
JavaScript
Java

def count_ones(n):
    count = 0
    while n != 0:
        n = n & (n - 1)  # 每做一次，就消掉最右邊的一個 1
        count += 1
    return count

def is_power_of_two(n):
    # 2 的冪，二進位表示中只會有一個 1（例如 8 = 1000）
    # 消掉那唯一的 1 之後，結果會變成 0
    return n > 0 and (n & (n - 1)) == 0

function countOnes(n) {
  let count = 0;
  while (n !== 0) {
    n = n & (n - 1); // 每做一次，就消掉最右邊的一個 1
    count++;
  }
  return count;
}

function isPowerOfTwo(n) {
  // 2 的冪，二進位表示中只會有一個 1（例如 8 = 1000）
  // 消掉那唯一的 1 之後，結果會變成 0
  return n > 0 && (n & (n - 1)) === 0;
}

class BitManipulation {
    static int countOnes(int n) {
        int count = 0;
        while (n != 0) {
            n = n & (n - 1); // 每做一次，就消掉最右邊的一個 1
            count++;
        }
        return count;
    }

    static boolean isPowerOfTwo(int n) {
        // 2 的冪，二進位表示中只會有一個 1（例如 8 = 1000）
        // 消掉那唯一的 1 之後，結果會變成 0
        return n > 0 && (n & (n - 1)) == 0;
    }
}

複雜度

大部分的位元運算技巧都是 O(1)（單一個運算子），或是 O(log n)（需要逐一檢查每一個位元，位元數量與數字大小的對數成正比）。

適用情況

狀態壓縮（Bitmask）：用一個整數的每一個位元代表「某個東西是否被選中 / 拜訪過」，常見於搭配 Dynamic Programming 解決「有限集合的所有子集合」類型的題目。
找出唯一或缺漏的數字：利用 XOR 的特性，可以在 O(1) 額外空間內找出落單的數字，或是找出 0~n 中缺漏的那個數字。
節省記憶體的旗標（Flag）管理：例如用一個整數的每一位元代表一種使用者權限，比起用陣列或物件儲存多個布林值更省空間。
快速判斷 2 的冪、計算二進位中 1 的個數：這類問題用位元運算解，通常比用迴圈除以 2 或轉成字串處理快非常多。

常見誤區

忽略 JavaScript 位元運算的 32-bit 限制：JavaScript 的位元運算子（&、|、^、<<、>>）都會先把數字轉成 32 位元的有號整數再運算，如果數字超過這個範圍（大約 ±21 億），結果可能會不是預期的樣子，這點和 Python（整數位元運算沒有固定位元數限制）不太一樣。
把 &、| 和 &&、|| 搞混：如前面警告的，位元運算子和邏輯運算子外觀相似但用途完全不同，寫錯很難從錯誤訊息直接看出來，容易造成邏輯上難以察覺的 bug。
對負數的二進位表示理解錯誤：負數在電腦中通常用「二補數（Two's Complement）」表示，直接對負數做位元運算或右移（尤其是 >> 與 >>> 的差異，後者是無號右移）容易得到不符合直覺的結果，使用前建議先確認數字一定是非負整數。
看到「唯一值」類問題不一定都要用 XOR：XOR 技巧通常只適用於「其他數字都恰好出現偶數次」這種特定情境，如果出現次數規則不同（例如其他數字出現三次），需要用更進階的位元計數技巧，不能直接套用同一招。

基本觀念：二進位表示​

常見運算子​

常見技巧​

1. 判斷奇偶​

2. 取得 / 設定 / 清除某一位元​

3. 用 XOR 找出「唯一不重複」的數字​

逐步拆解：以 nums = [4, 1, 2, 1, 2] 為例​

4. n & (n - 1)：消去最低位的 1​

複雜度​

適用情況​

常見誤區​