## Bitwise operations

In previous post we discussed basics on bitwise operations.

In this post we would take some classic interview questions which can be easily solved if we apply some bit manipulations.

## Problem 1 : Find the missing number

Given a set of N numbers ranging from 1 to N, one number is missing, find the missing number.

Numbers are non-sorted order.

## Analysis

We can easily find the element by having a hash key being numbers in set and increasing the count of the index whenever we encounter number in given set.

This approach required O(N) extra space. We want to avoid that extra space usage.

Let’s look at XOR operation first.

0 XOR 0 = 0

0 XOR 1 = 1

1 XOR 0 = 1

1 XOR 1 = 0

Given above rules, we can derive that A XOR A = 0 because this will always make number of ones as even. For example,

9 XOR 9 = 1001 XOR 1001 = 0000.

Do we get some hint?

We know that range of numbers is 1 to N, if XOR all numbers from 1 to N let’s call result as X. and then XOR all numbers which are actually present in set, call it Y and then if we XOR both X and Y, we get the missing number as all the numbers from 1 to N which are present in set will cancel each other.

Example,

Range is 1 to 5

Set as {1,3,4,5} = {0001, 0011, 0100, 0101}

Step 1 : XOR all numbers 1 to 5

X =0001 XOR 0010 XOR 0011 XOR 0100 XOR 0101 = 0001

Step 2 : XOR all numbers in set

Y = 0001 XOR 0011 XOR 0100 XOR 0101 = 0011

Step 3 XOR X and Y

Result = 0001 XOR 0011 = 0010 = 2 which is over missing element.

## Code

@a as input set of numbers

@n as range of elements in input

int missing_elem(int a[], int n){

int X =0, Y=0;

int i, N;

/* XOR all elements in range 1 to n */

for(i=1; i<=n; i++){

X = X ^ i;

}

/* XOR all elements in input set */

for(i=0; i<n-1; i++){

Y = Y ^ a[i];

}

/* XOR X and Y will give us missing number.*/

return X ^ Y;

}

## Problem 2 : Find duplicate element

Given a set of numbers range from 1 to N, one number is missing and one number is duplicate.

Find the missing and duplicate number.

A = {1,2,3,3,4,5} Range as 5

Step 1 : XOR all numbers 1 to 5

*X =0001 XOR 0010 XOR 0011 XOR 0100 XOR 0101 = 0001*

Step 2 : XOR all numbers in set

*Y = 0001 XOR 0010 XOR 0011 XOR 0011 XOR 0100 XOR 0101 = 0010*

Step 3 XOR X and Y as Z

*Result = 0001 XOR 0010 = 0011*

Same logic mentioned above goes for this problem too.

One more problem which uses similar logic is “Find a number which occurs odd number of times in given input set”

## Problem 3 : Find the position of right most set bit

Example : Let be the number be 18 = 00010010

Now if reset all bits except the LSB bit which is set and then take log (base 2), we can get the position of LSB which is set.

*x & ! (x-1) = 00010010 & 11101110 = 0000010 =2*

Log2(2) = 1, that is the position of LSB set.

Hence our return value becomes

In next post we would discuss couple of more problems on bitwise operations like finding two duplicate elements in a given input set etc.