Tuesday, November 18, 2014

Clearing the right most set bit in a binary number

Given an integer, write a program to clear the right most set bit in it's binary representation.
For example, consider a number 54. It is represented in binary as  
1 1 0 1 1 0
The right most set bit is marked in bold. We need to convert this to 
1 1 0 1 0 0
Let us look at the approach step by step.

If you negate the number to -54, it is represented in computer's memory in 2's compliment.
0 0 1 0 1 0
Let us perform a bit-wise AND operation between these two.
1 1 0 1 1 0
0 0 1 0 1 0
0 0 0 0 1 0
Subtract this from the original number to get the result. So x - ( x & -x) gives the required answer.

Here is the simple program to test the above.

Wednesday, November 5, 2014

Number of characters appearing in all given strings

Given a set of n strings, we have to write a program to find out the number of characters appearing in all the strings.

For example consider the following strings
{"India", "China", "United states"}, the letters {a,i,n} appear in all the strings.

Let us think of the following solution.
  • We first add all the characters in the first string to a set. 
  • For each string we do the following.
    • For each letter in the set, we check if it can be found the string.
    • If it is not found, we delete it from the set
  • Finally the set contains only the elements which appear in all the given strings.
Here is the C++ code which implements the above approach. For simplicity this program assumes that all the strings contains lower case alphabets only.