# 476 Number Complement

Given a positive integer, output its complement number. The complement strategy is to flip the bits of its binary representation.
Note:
1. 1.
The given integer is guaranteed to fit within the range of a 32-bit signed integer.
2. 2.
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.
Complexity: O(1) time, O(1) space
The Idea: First we find the first maximum significant bit. We do this by simply shifting 1 to the maximum bit location (30) (side note: 31 is reserved as the complement). Then we continue to shift this number to the right by 1 until it reaches the first 1. Then using `MAX_INT`, we can obtain all 1's and shift these to the right until we obtain the maximum significant digit that we found. Finally, `xor` 'ing this number with the result toggles everything.
int getMostSignificantDigit(int num)
{
int count = 0;
int maxLeftPower2 = 1 << 30;
while ((num & maxLeftPower2) == 0) {
maxLeftPower2 >>= 1;
count++;
}
return count;
}
int findComplement(int num)
{
int allOnesToMaxSigFig = INT_MAX >> getMostSignificantDigit(num);
return num ^ allOnesToMaxSigFig;
}
int main()
{
assert(findComplement(5) == 2);
assert(findComplement(1) == 0);
assert(findComplement(42) == 21);
}