【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

• 這裡是一樣的題目的詳解
• 當一個數字和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++