Count the Number of Bits Set in an Integer [Shift Operator]

Shift operators shift the bits in an integer variable by a specified number of positions. The << operator shifts bits to the left, and the >> operator shifts bits to the right. The syntax for these binary operators is x << n and x >> n Each operator shifts the bits in x by n positions in the specified direction. For a right shift, zeros are placed in the n high-order bits of the variable; for a left shift, zeros are placed in the n low-order bits of the variable.

Here are a few examples:

Binary 00001000 (decimal 8) right-shifted by 2 gives 00000010 (decimal 2).
Binary 00001000 (decimal 8) left-shifted by 3 gives 01000000 (decimal 64).

One of the application of shift operation is to count the number of bits set in an unsigned integer.
For example: f(0) = 0, f(1) = 1, f(2) = 1, f(3) = 2.

More information @ Wikipedia

Option 1: In a while loop, increment a counter if the last bit in the unsigned integer is 1 all the while right shifting the integer in each iteration of the while loop.

// C program to count the number of bits set in an integer

#include<stdio.h>

int main()
{
  unsigned int i, b[32] = {0};
  int j = 31, count = 0;
  printf("\nEnter the unsigned integer:");
  scanf("%d", &i);

  while(i != 0)
  {
    // Bitwise AND operation b/w i & 0x00000001 is 1
    // if the last bit of i is 1 and 0 if the last
    // last bit is 0
    b[j] = i & 0x00000001; 
    // Increment count whenever the bit is 1    
    if(b[j] == 1)
      count++;
    j--;
    // Right shifting i by 1 to get the next bit
    i = i >> 1;
  }

  printf("\nThe number of bits set in %d is %d", i, count);

  // The array b gives the binary representation of i
  printf("\nThe binary representation of %d is ", i);
  for(i = j + 1; j < 32; j++)
    printf("%d", b[j]); 

  return 0;
}

Brian Kernighan's method: Published in 1988, the C Programming Language 2nd Ed. (by Brian W. Kernighan and Dennis M. Ritchie) mentions this in exercise 2-9. On April 19, 2006 Don Knuth pointed out to him that this method "was first published by Peter Wegner in CACM 3 (1960), 322. (Also discovered independently by Derrick Lehmer and published in 1964 in a book edited by Beckenbach.)".

long count_bits(long n) {     
  unsigned int c; // c accumulates the total bits set in v
  for (c = 0; n; c++) 
    n &= n - 1; // clear the least significant bit set
  return c;
}

Use built-in functions in compilers: GCC has the following built-in function to count the number of bits. The compiler can generate a single POPCNT instruction in the best case or generate a call to a function to count the number of bits in the worst case.

int __builtin_popcount (unsigned int x);

SWAR Algorithm: This uses a divide & conquer algorithm where the problem of summing the number of bits set in a 32 bit unsigned integer is divided into two problems of summing the number of bits set in a 16 bit integer. This strategy is applied recursively resulting in log₂(32) = 5 steps. - From Hacker's Delight, p. 66, Figure 5-2

int pop(unsigned x)
{
    x = x - ((x >> 1) & 0x55555555);
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
    x = (x + (x >> 4)) & 0x0F0F0F0F;
    x = x + (x >> 8);
    x = x + (x >> 16);
    return x & 0x0000003F;
}

These are some of the ways to tackle this problem.

References:

• Bit Twiddling Hacks
• Hamming Weight
• Fast Bit Counting Routines
• Population Count (Ones count)

Written by Munia Balayil