C/C++, Codes

The number of set bits

Language implementation : C++.
A set bit ‘s value is 1; otherwise 0.
The idea is simple : AND the integer with so that preceding bits are clear/ If == 1, setbit increment, then shift bit by 1 position.
TRUTH table for AND.

A   B   A AND B
0   0         0
0   1         0
1   0         0
1   1         1

Only when corresponding bits are 1, the result can be confirmed to be 1.

/**
 * Duc Ho.
 * Count the number of set bits - Hamming Weight.
 * Date : 02/07/2012.
 */
#include <iostream>
using namespace std;

//count the number of set bits
int popCount(int num)
{
	int sBit = 0;
	//shift 32 bits
	for (int i = 0; i < 32; ++i){
        //AND with 1
        if ((num & 1) == 1)
          sBit++;
        //shift 1 pos more.
        num = num >> 1;
	}
	return sBit;
}
int main()
{
	int n;
	cout << "Enter a number: "; 	         cin  >> n;
	cout << "The number of set bits in " << n
	     << ": " << popCount(n);

	return 0;
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s