Loading....
Coupon Accepted Successfully!

 

Question 1

Write a C program to count bits set in an integer?
 


This is one of the most frequently asked interview questions of all times...

There are a number of ways to count the number of bits set in an integer. Here are some C programs to do the same.

Method1

This is the most basic way of doing it.


#include
int main()
{
  unsinged int num=10;
  int ctr=0;
  
  for(;num!=0;num>>=1)
  {
    if(num&1)
    {
      ctr++;
    }
  }

  printf("\n Number of bits set in [%d] = [%d]\n", num, ctr);
  return(0);

}





Method2

This is a faster way of doing the same thing. Here the control goes into the while loop only as many times as the number of bits set to 1 in the integer!.


#include
int main()
{
  int num=10;
  int ctr=0;
  
  while(num)
  {
    ctr++;
    num = num & (num - 1); // This clears the least significant bit set.
  }

  printf("\n Number of bits set in [%d] = [%d]\n", num, ctr);
  return(0);

}




Method3
This method is very popular because it uses a lookup table. This speeds up the computation. What it does is it keeps a table which hardcodes the number of bits set in each integer from 0 to 256.

For example


0 - 0 Bit(s) set.
1 - 1 Bit(s) set.
2 - 1 Bit(s) set.
3 - 2 Bit(s) set.
...



So here is the code...

 

const unsigned char LookupTable[]     = {  0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,   
                                           1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,  
                                           1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,   
                                           2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,   
                                           1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,    
                                           2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,   
                                           2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,   
                                           3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,   
                                           1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,   
                                           2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,   
                                           2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,   
                                           3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,   
                                           2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,   
                                           3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,   
                                           3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,   
                                           4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8};


unsigned int num; 
unsigned int ctr;   // Number of bits set.

ctr = LookupTable[num & 0xff] +     
      LookupTable[(num >> 8) & 0xff] +     
      LookupTable[(num >> 16) & 0xff] +     
      LoopupTable[num >> 24]; 




Question 2

What purpose do the bitwise and, or, xor and the shift operators serve?
 


The AND operator


Truth Table
-----------
0 AND 0 = 0
0 AND 1 = 0
1 AND 0 = 0
1 AND 1 = 1

x AND 0 = 0
x AND 1 = x



We use bitwise "and" to test if certain bit(s) are one or not. And'ing a value against a pattern with ones only in the bit positions you are interested in will give zero if none of them are on, nonzero if one or more is on. We can also use bitwise "and" to turn off (set to zero) any desired bit(s). If you "and" a pattern against a variable, bit positions in the pattern that are ones will leave the target bit unchanged, and bit positions in the pattern that are zeros will set the target bit to zero.

The OR operator


Truth Table
-----------
0 OR 0 = 0
0 OR 1 = 1
1 OR 0 = 1
1 OR 1 = 1

x OR 0 = x
x OR 1 = 1




Use bitwise "or" to turn on (set to one) desired bit(s).

The XOR operator


0 XOR 0 = 0
0 XOR 1 = 1
1 XOR 0 = 1
1 XOR 1 = 0

x XOR 0 = x
x XOR 1 = ~x




Use bitwise "exclusive or" to flip or reverse the setting of desired bit(s) (make it a one if it was zero or make it zero if it was one).

The >>, <<, >>=, <<= operators

Operators >> and << can be used to shift the bits of an operand to the right or left a desired number of positions. The number of positions to be shifted can be specified as a constant, in a variable or as an expression. Bits shifted out are lost. For left shifts, bit positions vacated by shifting always filled with zeros. For right shifts, bit positions vacated by shifting filled with zeros for unsigned data type and with copy of the highest (sign) bit for signed data type. The right shift operator can be used to achieve quick multiplication by a power of 2. Similarly the right shift operator can be used to do a quick division by power of 2 (unsigned types only). The operators >> and <<, dont change the operand at all. However, the operators >>= and <=< also change the operand after doing the shift operations.





x < x <<= y - Shifts variable x left y bits (Bits positions vacated by shift are filled with zeros).

A left shift of n bits multiplies by 2 raise to n.

x >> y  - Gives value x shifted right y bits.
x >>= y - Shifts variable x right y bits.

For the right shift, All bits of operand participate in the shift. For unsigned data type, 
bits positions vacated by shift are filled with zeros. For signed data type, bits positions 
vacated by shift are filled with the original highest bit (sign bit). Right shifting n bits 
divides by 2 raise to n. Shifting signed values may fail because for negative values the result never 
gets past -1:

-5 >> 3 is -1 and not 0 like -5/8.






Good interview question

A simple C command line utility takes a series of command line options. The options are given to the utility like this : options=[no]option1,[no]options2,[no]option3?... Write C code using bitwise operators to use these flags in the code.



//Each option will have a bit reserved in the global_options_bits integer. The global_options_bits
// integer will have a bit set or not set depending on how the option was specified by the user.
// For example, if the user said nooption1, the bit for OPTION1 in global_options_bits
// will be 0. Likewise, if the user specified option3, the bit for OPTION3 in global_options_bits
// will be set to 1.

#define OPTION1 "option1" // For strcmp() with the passed arguments.
#define OPTION1_BITPOS (0x00000001) // Bit reserved for this option.
#define OPTION2 "option2"
#define OPTION2_BITPOS (0x00000002)
#define OPTION3 "option3"
#define OPTION3_BITPOS (0x00000004)

//Required to do the bit operations.
#define ALL_BITPOS (0x0001ffff)

// Assume you have already parsed the command line option and that
// parsed_argument_without_no has option1 or option2 or option3 (depending on what has
// been provided at the command line) and the variable negate_argument says if the
// option was negated or not (i.e, if it was option1 or nooption1)

if (strcmp((char *) parsed_argument_without_no, (char *) OPTION1) == 0)
{
    // Copy the global_options_bits to a temporary variable.
    tmp_action= global_options_bits;

    if (negate_argument)
    {
        // Setting the bit for this particular option to 0 as the option has
        // been negated.
        action_mask= ~(OPTION1_BITPOS) & ALL_BITPOS;
        tmp_action= tmp_action & action_mask;
    } 
    else
    {
        //Setting the bit for this particular option to 1.
        action_mask= (OPTION1_BITPOS);
        tmp_action= tmp_action | action_mask;
    }

    // Copy back the final bits to the global_options_bits variable
    global_options_bits= tmp_action;
}
else if (strcmp((char *) parsed_argument_without_no, (char *) OPTION2) == 0)
{
    //Similar code for OPTION2
}
else if (strcmp((char *) parsed_argument_without_no, (char *) OPTION3) == 0)
{
    //Similar code for OPTION3
}


//Now someone who wishes to check if a particular option was set or not can use the
// following type of code anywhere else in the code.
if(((global_options_bits & OPTION1_BITPOS) == OPTION1_BITPOS)

    //Do processing for the case where OPTION1 was active. 
}
else
{
    //Do processing for the case where OPTION1 was NOT active.
}



Question 3

How to reverse the bits in an interger?
 


Here are some ways to reverse the bits in an integer.

Method1


unsigned int num;            // Reverse the bits in this number.
unsigned int temp = num;     // temp will have the reversed bits of num.

int i;

for (i = (sizeof(num)*8-1); i; i--)
{  
 temp = temp | (num & 1);
 temp <<= 1;  
 num  >>= 1;
}

temp = temp | (num & 1);



Method2

In this method, we use a lookup table.


const unsigned char ReverseLookupTable[] = 
{
     0x00, 0x80, 0x40, 0xC0, 0x20, 0xA0, 0x60, 0xE0, 0x10, 0x90, 0x50, 0xD0, 0x30, 0xB0, 0x70, 0xF0, 
     0x08, 0x88, 0x48, 0xC8, 0x28, 0xA8, 0x68, 0xE8, 0x18, 0x98, 0x58, 0xD8, 0x38, 0xB8, 0x78, 0xF8, 
     0x04, 0x84, 0x44, 0xC4, 0x24, 0xA4, 0x64, 0xE4, 0x14, 0x94, 0x54, 0xD4, 0x34, 0xB4, 0x74, 0xF4, 
     0x0C, 0x8C, 0x4C, 0xCC, 0x2C, 0xAC, 0x6C, 0xEC, 0x1C, 0x9C, 0x5C, 0xDC, 0x3C, 0xBC, 0x7C, 0xFC, 
     0x02, 0x82, 0x42, 0xC2, 0x22, 0xA2, 0x62, 0xE2, 0x12, 0x92, 0x52, 0xD2, 0x32, 0xB2, 0x72, 0xF2, 
     0x0A, 0x8A, 0x4A, 0xCA, 0x2A, 0xAA, 0x6A, 0xEA, 0x1A, 0x9A, 0x5A, 0xDA, 0x3A, 0xBA, 0x7A, 0xFA,
     0x06, 0x86, 0x46, 0xC6, 0x26, 0xA6, 0x66, 0xE6, 0x16, 0x96, 0x56, 0xD6, 0x36, 0xB6, 0x76, 0xF6, 
     0x0E, 0x8E, 0x4E, 0xCE, 0x2E, 0xAE, 0x6E, 0xEE, 0x1E, 0x9E, 0x5E, 0xDE, 0x3E, 0xBE, 0x7E, 0xFE,
     0x01, 0x81, 0x41, 0xC1, 0x21, 0xA1, 0x61, 0xE1, 0x11, 0x91, 0x51, 0xD1, 0x31, 0xB1, 0x71, 0xF1,
     0x09, 0x89, 0x49, 0xC9, 0x29, 0xA9, 0x69, 0xE9, 0x19, 0x99, 0x59, 0xD9, 0x39, 0xB9, 0x79, 0xF9, 
     0x05, 0x85, 0x45, 0xC5, 0x25, 0xA5, 0x65, 0xE5, 0x15, 0x95, 0x55, 0xD5, 0x35, 0xB5, 0x75, 0xF5,
     0x0D, 0x8D, 0x4D, 0xCD, 0x2D, 0xAD, 0x6D, 0xED, 0x1D, 0x9D, 0x5D, 0xDD, 0x3D, 0xBD, 0x7D, 0xFD,
     0x03, 0x83, 0x43, 0xC3, 0x23, 0xA3, 0x63, 0xE3, 0x13, 0x93, 0x53, 0xD3, 0x33, 0xB3, 0x73, 0xF3, 
     0x0B, 0x8B, 0x4B, 0xCB, 0x2B, 0xAB, 0x6B, 0xEB, 0x1B, 0x9B, 0x5B, 0xDB, 0x3B, 0xBB, 0x7B, 0xFB,
     0x07, 0x87, 0x47, 0xC7, 0x27, 0xA7, 0x67, 0xE7, 0x17, 0x97, 0x57, 0xD7, 0x37, 0xB7, 0x77, 0xF7, 
     0x0F, 0x8F, 0x4F, 0xCF, 0x2F, 0xAF, 0x6F, 0xEF, 0x1F, 0x9F, 0x5F, 0xDF, 0x3F, 0xBF, 0x7F, 0xFF
};

unsigned int num; // Reverse the bits in this number.
unsigned int temp; // Store the reversed result in this.

temp = (ReverseLookupTable[num & 0xff] <        (ReverseLookupTable[(num >> 8) & 0xff] <        (ReverseLookupTable[(num >> 16) & 0xff] <        (ReverseLookupTable[(num >> 24) & 0xff]);



Question 4

Check if the 20th bit of a 32 bit integer is on or off?
 


AND it with x00001000 and check if its equal to x00001000


if((num & x00001000)==x00001000)



Note that the digits represented here are in hex.


     0      0      0      0      1      0      0      0
                                 ^                     
                                 |

 x0000   0000   0000   0000   0001   0000   0000   0000 = 32 bits

  ^                              ^                    ^
  |                              |                    |

  0th bit                        20th bit             32nd bit



Question 5

How to reverse the odd bits of an integer?
 


XOR each of its 4 hex parts with 0101.

Question 6

How would you count the number of bits set in a floating point number?
 




Try this question your self :)

 




Test Your Skills Now!
Take a Quiz now
Reviewer Name