# 【LeetCode】 476. Number Complement

## Description
> Given a positive integer, output its complement number. The complement strategy is to flip the bits of its binary representation.

> Note:
> * The given integer is guaranteed to fit within the range of a 32-bit signed integer.
> * You could assume no leading zero bit in the integer’s binary representation.
> * This question is the same as 1009: https://leetcode.com/problems/complement-of-base-10-integer/

> 給予一個正整數，回傳它的補數。補數策略是反轉他的二進制表示法的每個位元。

> 提示：
> * 給予的數字的範圍是32位元的有號整數。
> * 你可以假設不會有任何零作為開頭位元的數字出現。
> * 這題和1009是一樣的題目：https://leetcode.com/problems/complement-of-base-10-integer/

## Example:

Example 1:

Input: 5
Output: 2
Explanation: The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. So you need to output 2.
 

Example 2:

Input: 1
Output: 0
Explanation: The binary representation of 1 is 1 (no leading zero bits), and its complement is 0. So you need to output 0.

## Solution

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

### Code

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

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