Bit Manipulation (extract 5th bit from X and return number of 1 bits in X)

Question

Assume X is an unsigned integer how will I be able to extract the 5th bit from X and return the number of 1 bits in X. Note: these two operations don't depend on each other.

For extracting the 5th bit from X I was thinking to use the & operation to do something like this: XXXX1X & 000010

I am not really sure how to do the return the number of 1 bits in X.

Thanks!

Answer 1

Counting the number of 1-bits is relatively straightforward; you iterate over all of the bits of your number and add to some accumulator the number of bits that are set:

unsigned int X;     
unsigned int count; 

for (count = 0; X; X >>= 1) {
   count += X & 1;
}

How it works:

1. Initialize count to 0
2. Start from the MSB (most significant bit) [this is the current bit]
3. Add to count the result of the current bit & 1
   • 1 if the bit is set
   • 0 if the bit is not set
4. Shift X to the right 1 bit, so the current bit is now the next MSB
5. Repeat step 3

Extracting the 5th bit is also straightforward, simply right shift your number X by 5 and compute the logical AND with 1:

unsigned int fifthBit (unsigned int X) {
   return (X >> 5) & 1;
}

Answer 2

A shorter and simpler way to find number of set bits in an int is following:

int num_1_bits(unsigned int x)  // or unsigned long x; or unsigned short x;
{
   int bitcount = 0;
   while(x)
   { 
      x &= (x - 1);
      ++bitcount;
   }
   return bitcount;
}

How does this work?

For an unsigned number x, the sequence of bits in x - 1 will be the complement of x till the first set bit of x counted from LSB.

i.e. for x = 20 [0b11100];     x - 1 = 19 [0b11011]
Here Bit sequence of 19 is complement of 20 till first set bit in 20 (first set bit at position 3 from LSB).

Therefore,
if you do x & (x - 1), this operation will consume one set bit from x.

Hence,
if you want to continue doing this until x becomes 0, you will need to do it as many times as there are set bits in x, which in turn will give you the count of set bits in x.

This method is better because the loop will run only as many times as there are 1 bits in x and hence doesn't depend on datatype of x.

Answer 3

As a complement, I precise that if you are looking for efficiency there are some built-in hardware instructions to perform computations on bits (counting zeros: you can deduce how many 1-bit you have then) see this article as an example.