Description
Given a positive integer, output its complement number. The complement strategy is to flip the bits of its binary representation.
给定一个正整数，输出它的补数。补数是将原先数字的二进制表示按位取反，再换回十进制后得到的新数。
Examples
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.
Answer
There are several ways to solve the problem, but C++ compiler doesn’t allow left shift operations on negative numbers, thus, negative mask is banned. The main goal is to generate a mask with all bits equal to 1 except corresponding leading zero bits of input number.
Time Complexity
O(1) since the integer is guaranteed to fit within the range of a 32-bit signed integer, there are at most 32 loops.
Code
C++
class Solution {
public:
int findComplement(int num) {
int mask = 0, tmp=num;
while( tmp ) {
tmp = tmp >> 1;
mask = mask << 1;
mask = mask | 1;
}
return ~num & mask;
}
};
