1009. Complement of Base 10 Integer

📘 題目敘述

整數的 complement，指的是把它的二進位表示中的每一個 0 變成 1，每一個 1 變成 0 之後得到的整數。

例如，整數 5 的二進位是 "101"，它的 complement 是 "010"，也就是十進位的 2。

給你一個整數 n，請回傳它的 complement。

條件限制

0 <= n < 10^9

🧠 解題思路

這題的想法很直接：

先找出 n 的二進位總共有幾位，然後做出一個「同樣位數、每一位都是 1」的數，再直接拿它減掉 n 就可以了。

例如：

n = 5
二進位是 101
它有 3 位
3 位全部都是 1 的數就是 111，也就是十進位的 7
7 - 5 = 2

而 2 的二進位剛好就是 010，這就是 5 的 complement。

所以這題的核心就是：

先找到這個位數對應的 111...111 是多少，再直接減掉 n。

不過這題有一個特例要先處理：

如果 n == 0
它的二進位可以看成 "0"
把它翻轉之後會得到 "1"
所以答案是 1

其餘情況就：

算出 n 的二進位位數 len
做出 len 位全部都是 1 的數 sum
回傳 sum - n

所有變數

len：n 的二進位位數
sum：和 n 同樣位數、每一位都是 1 的數

🪜 主要流程步驟

1. 先處理 n = 0 的特例

if (n == 0) {
    return 1;
}

這一步要先做，因為如果直接去算 log2(0) 會有問題。

而且題目的 complement 定義下：

0 的二進位看成 0
翻轉後就是 1

所以這個情況直接回傳 1。

2. 算出 n 的二進位位數 len

int len = log2(n) + 1;

這行的意思是：

log2(n) 可以找到最高位 1 在第幾層
再加 1，就是總位數

例如：

n = 5，二進位是 101
log2(5) 介於 2 和 3 之間，取整後是 2
所以 len = 3

代表 5 的二進位有 3 位。

3. 做出同樣位數的全 1 數字

int sum = pow(2, len) - 1;

這一步是在做：

2^len 會得到 1000...000
再減 1，就會變成 111...111

例如：

len = 3
2^3 = 8，二進位是 1000
8 - 1 = 7，二進位是 111

這就是和 n 同樣位數的「全 1」數字。

4. 用全 1 數字直接減掉 n

return sum - n;

因為 sum 的每一位都是 1，所以拿它減掉 n，效果就等於把 n 的每一個 bit 翻轉。

例如：

n = 10
二進位是 1010
len = 4
sum = 1111，也就是十進位 15
15 - 10 = 5

而 5 的二進位就是 0101，剛好就是 1010 翻轉後的結果。

⏱️ 複雜度

時間複雜度：O(1) 只有幾次數學運算。
空間複雜度：O(1) 只用了幾個整數變數。

💻 程式碼實作

class Solution {
public:
    int bitwiseComplement(int n) {
        if (n == 0) {
            return 1;
        }
        int len = log2(n) + 1;
        int sum = pow(2, len) - 1;
        return sum - n;
    }
};

🔗 題目連結

https://leetcode.com/problems/complement-of-base-10-integer/