PU Number Complement

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

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

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.

C Solution 1:

int findComplement(int num) {
    unsigned _num = num, mask = 1
    int res = 0;
    while (_num) {
        if (!(_num & 1)) res |= mask;
        mask <<= 1;
        _num >>= 1;
    }
    return res;
}

• There is some tricks underneath the solution.
• First, I used unsigned _num instead of using int num, the reason is that I need to make sure >> is a logic(unsigned) shift, rather than a arithmetic(signed) shift.
  • If >> is a arithmetic shift and the condition num I used in while is negative, the loop will never stop.
• Second, res doesn't need to be unsigned, it is because that whether num is positive or not doesn't affect the result when there is no leading zero.
• Finally, if I use int num, the submission is also accepted, but for the above solution, it's a coincidence.

C Solution 2:

int findComplement(int num) {
    int mask = ~0;
    while (num & mask) mask <<= 1;
    return ~num & ~mask;
}

• It's much better than the previous. Concise.
• no ambiguousness at all.

Summary:

• nothing to say.

LeetCode: 476. Number Complement