Write code to count number of set bits in a int/byte in BEST time complexity?
{ unsigned int ctr;
for(ctr=0;num;num >>= 1)
{
ctr += num & 1;
}
return ctr;
}
This approach requires one iteration per bit, until no more bits are set. So on a 32-bit word with only the high set, it will go through 32 iterations.
int CountSetBits(unsigned int num)
{ unsigned int ctr;
for (ctr = 0; num; ctr++)
{
num&= num - 1; // clear the least significant bit set
}
return ctr;
}
Brian Kernighan's method goes through as many iterations as there are set bits. So if we have a 32-bit word with only the high bit set, then it will only go once through the loop.
Method 1:Checking each bit
int CountSetBits(unsigned int num){ unsigned int ctr;
for(ctr=0;num;num >>= 1)
{
ctr += num & 1;
}
return ctr;
}
This approach requires one iteration per bit, until no more bits are set. So on a 32-bit word with only the high set, it will go through 32 iterations.
Method 2: Checking only set bit : Brian Kernighan's way
int CountSetBits(unsigned int num)
{ unsigned int ctr;
for (ctr = 0; num; ctr++)
{
num&= num - 1; // clear the least significant bit set
}
return ctr;
}
Brian Kernighan's method goes through as many iterations as there are set bits. So if we have a 32-bit word with only the high bit set, then it will only go once through the loop.
int CountSetBits(int num)
ReplyDelete{ int ctr=0;
for(;num!=0;num >>= 1)
{
if(num&1)
ctr++;
}
return ctr;
}
/*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
ReplyDelete1 in the integer!.*/
int CountSetBits_Better(int num)
{ int ctr=0;
while(num)
{
ctr++;
num = num & (num - 1); // This clears the least significant bit set.
}
return ctr;
}
3rd Approcah--------Using Lookup Table
ReplyDeleteThis 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.
EXAMPLE:
0 - 0 Bit(s) set.
1 - 1 Bit(s) set.
2 - 1 Bit(s) set.
3 - 2 Bit(s) set.
...
http://www.geeksforgeeks.org/archives/1176
ReplyDeleteWithout branching & More clearer way--------
ReplyDeleteunsigned int v; // count the number of bits set in v;
unsigned int c; // c accumulates the total bits set in v
for (c = 0; v; v >>= 1)
{
c += v & 1;
}
This approach requires one iteration per bit, until no more bits are set. So on a 32-bit word with only the high set, it will go through 32 iterations.
Brian Kernighan's way ------------
unsigned int v; // count the number of bits set in v;
unsigned int c; // c accumulates the total bits set in v
for (c = 0; v; c++)
{
v &= v - 1; // clear the least significant bit set
}
Brian Kernighan's method goes through as many iterations as there are set bits. So if we have a 32-bit word with only the high bit set, then it will only go once through the loop.