# 【LeetCode】 1009. Complement of Base 10 Integer

## Description
> Every non-negative integer `N` has a binary representation. For example, `5` can be represented as `"101"` in binary, `11` as `"1011"` in binary, and so on. Note that except for `N = 0`, there are no leading zeroes in any binary representation.

> The complement of a binary representation is the number in binary you get when changing every `1` to a `0` and `0` to a `1`. For example, the complement of `"101"` in binary is `"010"` in binary.

> For a given number `N` in base-10, return the complement of it's binary representation as a base-10 integer.

> Note:
> * `0 <= N < 10^9`
> This question is the same as 476: https://leetcode.com/problems/number-complement/

> 每個非負整數`N`都有一個二進位代表數字。例如`5`在二進制可以表示成`"101"`，`11`則可以表示成`"1011"`等等。注意，除了`N = 0`以外，沒有其他以零當作開頭的數字。

> 一個二進制數字的補數是指把全部的`1`換成`0`然後`0`換成`1`。例如`"101"`的二進制補數就會是`"010"`。

> 給予一個十進制數字`N`，回傳它的二進制補數並換為十進制。

> 提示：
> * `0 <= N < 10^9`
> 這個問題和476是一樣的：https://leetcode.com/problems/number-complement/

## Example:

Example 1:

Input: 5
Output: 2
Explanation: 5 is "101" in binary, with complement "010" in binary, which is 2 in base-10.


Example 2:

Input: 7
Output: 0
Explanation: 7 is "111" in binary, with complement "000" in binary, which is 0 in base-10.


Example 3:

Input: 10
Output: 5
Explanation: 10 is "1010" in binary, with complement "0101" in binary, which is 5 in base-10.

## Solution

* 這裡是一樣的題目的[詳解](https://hackmd.io/@Zero871015/LeetCode-476)
* 當一個數字和`1`做XOR運算後，就會變得相反。因此現在的問題變成要怎麼避免前面多餘的零也變成一。
* 最簡單的方法就是利用位移`>>`去計算`N`有幾個位元`digits`，再將`digits`個`1`去和`N`做XOR就是答案了。
* 注意`0`是個特例，要另做判斷。

### Code

class Solution {
public:
    int bitwiseComplement(int N) {
        if(N == 0) return 1;
        int digits = 0;
        int XOR = 0;
        while(N >> digits)
        {
            digits++;
            XOR = (XOR << 1) + 1;
        }
        return N ^ XOR;
    }
};

###### tags: `LeetCode` `C++`