693. Binary Number with Alternating Bits

📘 題目敘述

給定一個正整數，請判斷它的二進位表示是否為「交替位元」：也就是任意兩個相鄰位元的值永遠不同。

條件限制

• 1 <= n <= 2^31 - 1

🧠 解題思路（一）用 int 除法

我這份寫法的核心是用位元操作做一個很漂亮的判斷。

先把 n 右移一位得到 k = n / 2（等價於 n >> 1），這樣 k 就是「少了最後一個 bit」的版本。接著做 n ^ k：

• 如果 n 的 bits 是交替的（例如 101010...）
• 那 n 跟右移一位的 k 每一位都會不同
• XOR 後就會變成全 1（例如 11111...）

而「是不是形如 111... 的數」可以用經典技巧判斷：

x 是全 1（二進位形如 111...）
當且僅當 (x & (x + 1)) == 0

所以我最後直接檢查 ((k ^ n) & ((k ^ n) + 1)) == 0。

所有變數

• k：n 右移一位後的結果（用來和 n 做 XOR）

🪜 主要流程步驟（一）

1. 先把 n 右移一位得到 k

k = n / 2 代表把 n 的二進位整體往右移一格，少掉最低位那一個 bit。

2. 用 XOR 把「交替」轉成「全 1」

x = k ^ n

如果 n 是交替位元，那 n 和 k 在每一個對齊的位置都不同，因此 XOR 會得到 111... 這種全 1 的形狀。

3. 判斷 x 是否為全 1

用位元性質檢查：(x & (x + 1)) == 0。如果成立，代表 x 是 111...，也就代表原本 n 的相鄰位元確實都不同。

⏱️ 複雜度（一）

• 時間複雜度：O(1)
• 空間複雜度：O(1)

💻 程式碼實作（一）

class Solution {
public:
    bool hasAlternatingBits(int n) {
        long long k = n / 2; // 沒有最後一個位元
        return ((k ^ n) & ((k ^ n) + 1)) == 0;
    }
};

🧠 解題思路（二）用移位

這份寫法的重點是把「交替」轉成一個很容易判斷的形狀。

如果 n 的二進位是交替的（例如 101010... 或 010101...），那把它右移一位後，兩個數在每一個對齊的位置都會是相反的。因此做 XOR：x = n ^ (n >> 1)，就會得到一個全部都是 1 的二進位數（像 11111...）。

接下來只要判斷 x 是不是「全 1」即可。而「全 1」有一個經典特徵：

• 111... 加 1 會變成 1000...
• 兩者做 AND 會變成 0

所以用 (x & (x + 1)) == 0，就能一行判斷是否為交替位元。

所有變數

• x：n 與 n >> 1 XOR 後的結果，用來判斷是否為全 1

🪜 主要流程步驟（二）

1. 先把 n 右移一位並做 XOR

x = n ^ (n >> 1)，這一步的效果是：如果原本相鄰位元都不同，XOR 後會得到 111...。

2. 判斷 x 是否為全 1

用位元性質：(x & (x + 1)) == 0。成立代表 x 是 111...，也就代表 n 是交替位元。

⏱️ 複雜度（二）

• 時間複雜度：O(1)
• 空間複雜度：O(1)

💻 程式碼實作（二）

class Solution {
public:
    bool hasAlternatingBits(int n) {
        long long x = n ^ (n >> 1); // 2進位移動一位
        return (x & (x + 1)) == 0;
    }
};

🔗 題目連結

https://leetcode.com/problems/binary-number-with-alternating-bits/