解析位元運算公式 n & ~(((n + 1) & ~n) >> 1)

# 前言 在解決「尋找最小的 $x$ 使得 $x \lor (x + 1) = n$ 」這個問題時，我們得出了一個結論：對於奇數 $n$ ，答案是將 $n$ 的二進位表示中，「末尾連續的 1」序列裡最高位的那一個 `1` 修改為 `0`。 例如：如果 $n$ 的二進位是 `...01111`，我們目標是把它變成 `...00111`。 這個操作可以透過以下這行精簡的位元運算公式完成： ```cpp n & ~(((n + 1) & ~n) >> 1) ``` 這篇筆記旨在拆解這個複合表達式，逐步說明其工作原理。 --- # 公式拆解 這個公式可以分為三個主要步驟來理解，我們由內而外進行分析。 我們的目標 $n$ 範例設為 **23**，二進位表示為 `00010111`。 我們的目標是將末尾三個 `1` 中最左邊的那個（值為 4 的位元）關閉。 ## 步驟一：找出右邊數來第一個「0」的位置 **表達式核心：** `(n + 1) & ~n` 這是非常經典的位元操作技巧，用於定位最低位的 `0`。 1. **`n + 1` 的進位特性**： 當一個整數加 1 時，其二進位末尾所有的連續 `1` 都會因為進位而變成 `0`，直到遇到第一個 `0`，該位置會變成 `1`，進位停止。 * (23) = `00010111` * (24) = `00011000` (注意末尾三個 1 變成了 0，它們左邊的 0 變成了 1) 2. **`~n` 取反**： * `~n` = `11101000` 3. **`&` (AND) 運算**： 將上述兩個結果進行 AND 運算，只會保留同時為 `1` 的位元。 ``` 00011000 (n + 1) & 11101000 (~n) ---------------- 00001000 (結果為 8) ``` **小結**：這一步成功分離出了 從右側開始數第一個非 `1` 的位置。 ## 步驟二：鎖定目標位元（向右移位） **表達式：** `(步驟一的結果) >> 1` 我們在步驟一找到了第一個 `0` 的位置（在範例中是第 3 位，數值為 8）。 但我們的目標是修改這個 `0` 位置**右邊**的那一個 `1`（也就是末尾連續 `1` 序列的最高位）。 因此，我們將步驟一的結果向右移動一位： * `00001000 >> 1` = `00000100` (數值為 4) **小結**：這一步得到了一個「遮罩 (Mask)」，這個遮罩只有我們想要修改的那一個目標位元是 `1`，其他都是 `0`。 ## 步驟三：清除目標位元 **表達式：** `n & ~(步驟二的遮罩)` 現在我們有了目標遮罩 `Mask = 00000100`。我們要利用這個遮罩把 對應位置的 `1` 變成 `0`，並保持其他位置不變。 這是標準的「清除位元」操作： 1. **`~Mask` (遮罩取反)**： 製造一個工具，目標位置為 `0`，其他位置全為 `1`。 * `~Mask` = `11111011` 2. **`n & (~Mask)`**： 將原始的 與這個反向遮罩做 AND。 * 目標位置：`1 & 0` 結果為 `0`（成功清除）。 * 其他位置：`x & 1` 結果仍為 `x`（保持不變）。 ``` 00010111 (n, 即 23) & 11111011 (~Mask) ---------------- 00010011 (結果為 19) ``` # 總結 回顧整個流程： 1. `00010111` (原始 n) 2. `00001000` (找到第一個 0) 3. `00000100` (右移，鎖定目標 1) 4. `11111011` (取反，準備清除工具) 5. `00010011` (與原數 AND，完成清除) 這個公式 `n & ~(((n + 1) & ~n) >> 1)` 利用了加法進位的特性和基本的邏輯閘操作，在不使用任何迴圈的情況下，精確地完成了「關閉末尾連續 1 中最高位」的任務。這是一種高效且常見於底層優化的寫法。