Anukool Lakhina wrote:
> Given two 32-bit numbers, I want to decide which number has more bits set.
> And what the difference in the number of bits set is. So for example, if
> Num1=1110000...011 and Num2= 0000011...001, I'm trying to write an efficient
> function numBitsSet() that returns 2 if Num1 has 2 more bits set than Num2
> and -2 if Num2 has 2 more bits set than Num1. In this case, it'll return 2.
>
> Yes, I can do this easily by looping through the two numbers and storing a
> counter etc etc. But I need an efficient way to do this - I'm trying to do
> this by using a combination of xors or something. Please email me if you
> have any suggestions.
static const unsigned char count[0x100] = {
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,
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, 8, 8,
};
static int numBits8(unsigned int x)
{
return count[x & 0xff];
}
static int numBits(unsigned int x)
{
return numBits8(x >> 24) +
numBits8(x >> 16) +
numBits8(x >> 8) +
numBits8(x);
}
int diffBits(unsigned int a, unsigned int b)
{
return numBits(a) - numBits(b);
}
--
Glynn Clements <[EMAIL PROTECTED]>