Solution 1:
algorithm (Kernighan's?)
The "slow and obvious" solution:
UINT32 Count(UINT32 n)
{
UINT32 c = 0;
for( ; n != 0; n >>= 1 )
{
c += n & 1;
}
return c;
}
Sol 2: --o(n)
int num_bits_set(int num)
{
int count = 0;
while(num)
{
num = num & (num - 1);
count++;
}
return count;
}
{
int count = 0;
while(num)
{
num = num & (num - 1);
count++;
}
return count;
}
Sol 3:
--------
har arr[256] = {0, 1, 1, 2, 1, 2, 2, 3, 1, ...........};
int
count_set_bits (int num)
{
char byte0, byte1, byte2, byte3;
byte0 = num & 0xff;
byte1 = (num & 0xff00) >> 8;
byte2 = (num & 0xff0000) >> 16;
byte3 = (num & 0xff000000) >> 24;
return (arr[byte0] + arr[byte1] + arr[byte2] + arr[byte3]);
}
AND
The one true method of counting bits comes from MIT Hakmem 169 (assuming 32-bit int):
inline UINT32 Count(UINT32 n)
{
UINT32 c = n;
c -= (n>>1) & 033333333333;
c -= (n>>2) & 011111111111;
c = (c + c>>3) & 030707070707;
return c % 63;
}
http://discuss.techinterview.org/default.asp?interview.11.578648.14
--
Siva
There are a number of ways to count the number of bits set in an integer. Here are some C programs to do the same.
ReplyDeleteMethod1
This is the most basic way of doing it.
#include
int main()
{
unsinged int num=10;
int ctr=0;
for(;num!=0;num>>=1)
{
if(num&1)
{
ctr++;
}
}
printf("\n Number of bits set in [%d] = [%d]\n", num, ctr);
return(0);
}
Method2
This is a faster way of doing the same thing. Here the control goes into the while loop only as many times as the number of bits set to 1 in the integer!.
#include
int main()
{
int num=10;
int ctr=0;
while(num)
{
ctr++;
num = num & (num - 1); // This clears the least significant bit set.
}
printf("\n Number of bits set in [%d] = [%d]\n", num, ctr);
return(0);
}
Method3
This method is very popular because it uses a lookup table. 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};
unsigned int num;
unsigned int ctr; // Number of bits set.
ctr = LookupTable[num & 0xff] +
LookupTable[(num >> 8) & 0xff] +
LookupTable[(num >> 16) & 0xff] +
LoopupTable[num >> 24];
nice article..
ReplyDelete