count no. of setbits in any given no.

#include <stdio.h>
#include<iostream>
using namespace std;

//1st method
int coutsetbits(int Num)
{
int count=0;
for( ; Num; Num>>=1)
{
if (Num & 1)
count++;
}
return count;
}

The operators >> and <<, dont change the operand at all. However, the operators >>= and <=< also change the operand after doing the shift operations.
//2nd method
int coutsetbits(int Num)
{
int count;
for( count =0; Num; count++)
{
Num = Num & Num -1;
}
return count;
}

//simplify it

{

while(num!=0)

{ count++;

num=num &(num-1) //clears last significant setbit

}

return count;

}

int main ()
{
int num;
cout<<“\n enter the num :”;
cin>>num;
int a;
a=coutsetbits(num);
cout<<a;
system(“pause”);
return 0;
}

//3rd method

write the num in binary form by dividing 2 each time till then it becam 0 n store it in any string/char-string..now count how many setbit r ?

int main ()
{
int num,i=0,a[50],count=0,count1=0;
cout<<“\n enter the num :”;
cin>>num;

while(num!=0)
{ a[i]=num%2; count++; i++; num=num/2; }

for(int j=count-1;j>=0;j–)
cout<<a[j];
for(int j=count-1;j>=0;j–)
{ if(a[j]==1)
count1++; }
cout<<“\n no. of set bit is :”<<count1;
cout<<endl<<endl;
system(“pause”);
return 0;
}

//4th method

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};

//table is taken from a site

unsigned int num;
unsigned int ctr; // Number of bits set.
//0xff==(11111111)(in binary form)

//it'll check 1 byte(8 bit) at a time of any int so we extract 1 byte at a time by rightshift operator n find the corresponding value from lookuptable..

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

Advertisements

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


%d bloggers like this: