476.Number Complement

Tags: Easy Bit Manipulation

Links: https://leetcode.com/problems/number-complement/

---

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

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 output2.

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.

Note:

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

---

class Solution {
public:
    int findComplement(int num) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        unsigned int mask = INT_MAX;
        while (mask & num) mask <<= 1;

        return (~num) & (~mask);
    }
};

按位取反很自然的联想到运算符~，但是如果能够固定数量的按位取反，其实可以考虑利用INT_MAX的移位操作，不断左移，直到和num的与运算为0，那么就可以确定需要按位取反的有多少位了，注意输入都是正整数，所以不存在输入为0的情形。另外要用unsigned int类型。

1009就是输入存在0的情况。