BitWise Operators - interview Questions

In this article I am going to present few interview problems that are directly based upon the concepts of bitwise operations. I would urge you to please go back and check BitWise Operators Basic Tutorial and BitWise Operators Advanced Tricks, as these articles forms the basis of many problems discussed here.

* Check if a number is a multiple of 3
A number is multiple of 3, if the difference between the count of SET bits in odd and even postions are also multiple of 3. Following is a recursive routine in C to accomplish this logic.

int isMult3(unsigned int n)
{
    int odd_c = even_c = 0; //variables to count odd and even SET bits
   
    // Terminating condition for the recursive routine.
    if (n == 0)    // return true if difference is 0.
    return 1;
    if (n == 1)    // return false if the difference is not 0.
    return 0;
   
    while(n) {
    if (n&1)   // odd bit is SET, increment odd_C
        odd_c++;
    n = n >> 1;
   
    if (n&1)   // even bit is SET, increment even_c
        even_c++;
    n = n >> 1;
    }
   
    // Recursive call this function till you get 0/1 as the difference
    return(isMult3(abs(odd_c - even_c)));
}


* Multiply by 7 using bitwise operators
  return ((n << 3) - n );

Explanation: n << 3 will produce the effect of multiplication by 2n i.e. 8. (refer section - multiply by 2n)

* bit position of rightmost SET bit

A 2's complement of a number gives us all the bits complemented except the rightmost SET bit. Using this attribute we can arrive at the following code snippet.

    return (log2(n & (-n))) + 1;

Explanation: Anding 2's complement with the original number leaves us with only the righmost bit SET and others as 0. Now, we can take a log base 2 of this binary representation using Finding the log base 2 of an integer with MSB set . Add 1 to get the correct bit position.

* In an array, all the numbers are occurring even number of times, except only one number that occurrs odd number of times.. Find the number.

a XOR b always return TRUE if and only if a and b are different. We can use this property to figure out the element occurring odd number of times. XORing all the even elements will result in 0 leaving the odd - one out :-).

int getOddNumber(int arr, int arrSize)
{
    int i;
    int temp = 0;
    for (i = 0; i < arrSize; i++)
    temp = temp ^ arr[i];
   
    return temp; //number occurring odd number of times.
}


* Find out the number of bits that needs to be reversed to transform A to B

Again, XOR operator is at our disposal, XORing A and B, will SET the bits that are different and hence require bit-reversal in both A and B. After this, we need to count the number of SET bits. (Refer Calculating the count of SET bits in an integer)

return countSetBits(A ^ B);

* Get A % B where B is power of 2.

If B is power of 2, then it has only single bit SET. Let us take an example where A=17(0001_0001) and B=4(0100). To get the result of A % B, we need to return the 2 right-most bits, as these are the remainder if you are going to divide any number with 4(0100).

return (A & (B - 1));  

* Circular Rotatation of Bits of a number.

Circular rotation refers to the shift operation where instead of filling '0' to the bit pattern, we fill the falling bits from the other end.

#define INT_BITS 32
/*left circular rotation of  n by d bits*/
int leftCRotate(int n, unsigned int d) {
    return (n << d)|(n >> (INT_BITS - d));
}

/*Right circular rotation of n by d bits*/
int rightCRotate(int n, unsigned int d) {
    return (n >> d)|(n << (INT_BITS - d));
}

That concludes the list of few interview questions based on bitwise operators. This is by far not an exhaustive list of questions, but I am hoping that this should atleast provide some idea how we can tweak bit logic to get through some effective solutions for such problems. If somebody, wants some specific point to be discussed and elaborative or You have any new request for any specific topic, please leave us a comment From 'Feedback And Query' section provided on Contact US;.

-Pankaj
Happy Programming

comments powered by Disqus