Medium

# 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
```

Code:

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

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

Code:

Output:

```N = 10, Complement: 5
N = 10, Complement: 5
```