LeetCode 面試必考：(n & 1) 位元運算判斷奇偶的原理詳解

背景 : 這個問題通常出現在哪裡？

在寫 Leetcode, 面試題或是底層程式時, 常會看見以下程式碼

if ((n & 1) == 1) {

}

1 不是十進位的 1 嗎？其實關鍵在於電腦是用二進位在運算

重要觀念 : 二進位的『最右邊』

在二進位中：

最右邊那位 (LSB) : 代表這個數字是奇數或偶數, 右邊是 1 -> 奇數, 最右邊是 0 -> 偶數

範例 : 5 的二進為為 101, 6 的二進位為 110, 7 的二進位為 111

& (AND) 運算子在做什麼？

AND 的規則只有一條 : 兩邊都是 1, 結果才是 1

實際上的 (n & 1) 發生什麼事情

11 = 1011

1 = 0001

___________

& = 0001 -> 結果是 1

(n & 1) 到底在判斷什麼？

(n & 1) 只是在檢查 n 的『最右邊那一個 bit 是不是 1』

Java 範例

public class BitCheck {
	public static void main(String[] args) {
		int n = 11; 
		if ((n & 1) == 1) {
			System.out.println("奇數");
		} else {
			System.out.println("偶數");
		}
	}
}

延伸之後計算 bit 通常會這樣寫

while(n != 0) {
	count += (n & 1);
	n >>= 1;
}
​

n & 1 : 檢查目前最低位, n >>= 1 : 右移一位, 繼續檢查下一個 bit

總結

(n & 1) 是一個非常精準的位元檢查技巧。它利用了二進位與 AND 運算的特性，只關心數字的最低位， 因此能快速判斷奇偶或是否為 set bit。