This post is completed by 2 users

  • 1
 Add to List
Medium

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

Related Problems: