Number Complement

Problem

The complement of an integer is the integer you get when you flip all the 0’s to 1’s and all the 1’s to 0’s in its binary representation.

• For example, The integer 5 is "101" in binary and its complement is "010" which is the integer 2.

Given an integer num, return its complement.

Constraints

• 1 <= num < 231

Solution

The problem Number Complement can be solved by creating a mask which can mask off leading zero bits. Using the bitwise technique n & (n-1) from Power of Two, rightmost bits can be unset until only a MSB is left. Next, by shifting the mask to left by 1 and subtracting 1, a mask which has all bits other than leading zero bits set can be created. By applying the mask to the complement of a given number, it’s possible to select only the valid bits.

Implementation

class Solution
{
  public:
    int findComplement(int num)
    {
        unsigned int mask = num;
        while (mask & (mask - 1))
            mask &= mask - 1;
        mask = (mask << 1) - 1;

        return mask & ~num;
    }
};