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

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

**Code:**

**Output:**

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