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

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);
}