Counting no. of 1's in a given number without using loop.
Counting number of set of unset bits in a given 32 bit number is really a basic thing that may be used in number of lower level programming including kernel's memory management. I have used this in TAJ's memory manager routine to keep track of used and unused block of memory in my heap and page management. So this can be viewed as a simple bitmap that can be used to keep track of no. of resources.Now this is really a mindblowing stuff I have ever came accrose. It is not that easy to count number of 1's (bit that are set) in a given number using loop. There are number of solution to this problem. For example:
1. int count=0;//x is input
while(x)
{
x&=x-1;
++count;
}
return count;
2. int count=0;
while(n)
{
if(n & 1)
count++;
n >>= 1;
}
etc etc etc.......
But what if you are not allowed to use loops in counting the number of ON bits? Well this is really mind boggling.. What to see the solution? Then please check it:
unsigned int v; // count the number of bits set in v
unsigned int c; // c accumulates the total bits set in v
1. Counting no. of ON bits in a 12-bit number.
c = (v * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;
2. Counting no. of ON bits in a 24-bit number.
c = (v & 0xfff) * 0x1001001001001ULL & 0x84210842108421ULL;
c += ((v & 0xfff000) >> 12) * 0x1001001001001ULL & 0x84210842108421ULL;
c %= 0x1f;
3. Counting no. of ON bits in a 32-bit number.
c = (((v & 0xfff) *
0x1001001001001ULL & 0x84210842108421ULL) +
((v & 0xfff000) >> 12) *
0x1001001001001ULL & 0x84210842108421ULL)) % 0x1f;
c += ((v >> 24) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;
Isnt it mind blowing? But friends this things really works. Want to check the explaination why how it works? check this : http://www.thinkingms.com/pensieve/homepage/articles/tech/bitcounter64/bitcounter_64bit.htm
posted by Viral Patel @ 3:43 PM
1 comments
