This post is completed by 2 users

Add to List 
420. Number's Complement  2 Approaches
Objective: Given a number N, write a program to find a complement number of the given number.
Flip all the bits of a number to get the complement of that number.
Example:
N = 8 Output: 7 Explanation: N = 8, binary representation: 1 0 0 0 Flip all the bits = 0 1 1 1 => 7 ____________________________________ N = 13 Output: 2 Explanation: N = 13, binary representation: 1 1 0 1 Flip all the bits = 0 0 1 0 => 2 ____________________________________
Approach: Power of 2
 Let's say given number is N.
 Take x = 1, power = 1.
 while x < N, do power = power * 2 and x = x + power.
 result = x  N.
Example: N = 8
x = 1, power = 1, x < 8 power = power * 2 = 1 * 2 = 2, x = x + power = 1 + 2 = 3 x = 3, power = 2, x < 8 power = power * 2 = 2 * 2 = 4, x = x + power = 3 + 4 = 7 x = 7, power = 7, x < 8 power = power * 2 = 4 * 2 = 8, x = x + power = 7 + 8 = 15 x = 15, Now x > 8 result = x  N => 15  8 = 7
Output:
N = 10, Complement: 5
Approach: XOR + Most Significant Bit
 Let's say given number is N.
 Create a mask (it would be all 1's) for the number N.
 Do mask^N will produce the complement of N.
Mask: The XOR returns TRUE (1) only when one of the bits is true, else return FALSE (0). This means, 1^1=0 and 0^0=0. If we XOR 1 and 0 bit, we will get 1. Thus effectively flipping the bits. That's the reason we need mask will all 1's.
Explanation:
Let's say N = 1 0 1 0 mask = 1 1 1 1 Complement = N^mask = 0 1 0 1
How to create Mask:
Method 1:
 Find the most significant bit location (say it is msb) and take x = 1.
 while msb>0, left shift x by 1 and do x = x OR 1 (this will put 1 at that position).
Example: N = 1 0 1 0, most significant bit = 3 while(3>0) msb = 3,x = 1, x << 1 => 1 0 then 1 0 OR 1 => 1 1 msb = 2, x = 1 1, x<<1 => 1 1 0 then 1 1 0 OR 1 => 1 1 1 msb = 1, x = 1 1 1, x<<1 => 1 1 1 0 then 1 1 1 0 OR 1 => 1 1 1 1 msb = 0, mask = 1 1 1 1 x = 1, left shift by 3 => x = 1 0 0 0 0 Mask = x  1 = 1 1 1 1
Method 2: Find the highest set bit. left shift by 1 and then subtract 1 from it.
Example: N = 1 0 1 0, highest set bit= 1 0 0 0 left shift by 1 => 1 0 0 0 0 Mask = x  1 = 1 1 1 1
Output:
N = 10, Complement: 5 N = 10, Complement: 5