Number Complement

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

Example:

Input: num = 4
Output: 3
Explanation: The binary representation of 4 is 100 (no leading zero bits), and its complement is 011. So you need to output 3.

Approach: If you see the problem here is we don't want to flip all the 32 bits, we just want to flip bits till the most significant set bit so the problem here really is to find the most significant set bit which we just can get using Log2(num). Once we get it we can can use a mask (starting from most significant bit)11..1(least significant bit) and xor this mask with the given number to get the result. Lets take an example say 5 (101). Now the most significant bit number is Floor(log2(5)) is 2 (from the left). Now if we take a number 2 ^ (2 + 1) - 1 = 7 (111). Let's take an XOR of 5(101) and 7(111) = 2(010) which is our answer. 

Implementation in C#:

        public int FindComplement(int num)

        {

            return (int)(num ^ ((long)Math.Pow(2, (int)Math.Log2(num) + 1)) - 1);   

        }

Complexity: O(log(n)).