The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as
well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct. Donald E. Knuth

Bit Manipulation

Problem :-
Count the number of set bits in an integer.

Solution :-
We use a combination of bitwise AND operation & left shift operation to count the number of set bits in an integer. See the implementation below.

#include<iostream>
using namespace std;

// count the no. of set bits in a positive integer
int countSetBits(unsigned int num) {
   unsigned int count = 0;
   while (num) {
      // bitwise AND operation to check if the
      // leftmost bit is set or not
      // if set, increment the count
      count += num & 1;
      // left shift the nm by one position
      num >>= 1;
   }
   return count;
}

//main
int main() {
   unsigned int num = 6;
   unsigned int no_set_bits = countSetBits(num);
   cout<<"\nNo. of set bits :: "<<no_set_bits;
   cout<<endl;
   return 0;
}

Back | Next

All problems on Bit Manipulation
* Count the number of set bits in an integer
* Find out whether a bit in a particular position in the binary representation of an unsigned integer is set or not
* Check if a number is a power of 2 using bit operation.
* Add two numbers without using any arithmetic operator
* Find the number of bits which are to be flipped to convert one integer to another
* Reverse the bits of an unsigned integer