Re: is there a fast way to get every bit in a uint64_t
On 27 Aug., 15:06, Greg Herlihy wrote:
If the target architecture has an instruction to count the set bits in
a register (such as Intel's i7 POPCNT instruction), then an assembly
language routine would be the fastest solution.
I'm not sure if that's really what the OP asked for
Otherwise, counting the bits via a table look-up would almost
certainly be faster than testing each bit individually. For example:
inline
int GetPopulationCount( uint64_t n)
{
static const int kNumBits[] = {
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 };
int count = 0;
count += kNumBits[n & 0xFF];
count += kNumBits[(n >>= 8) & 0xFF];
count += kNumBits[(n >>= 8) & 0xFF];
count += kNumBits[(n >>= 8) & 0xFF];
count += kNumBits[(n >>= 8) & 0xFF];
count += kNumBits[(n >>= 8) & 0xFF];
count += kNumBits[(n >>= 8) & 0xFF];
count += kNumBits[n >> 8];
return count;
}
There's another nice solution for counting bits (I can't take credit
for):
int getPopulationCount(uint64_t n)
{
// 64 1-bit numbers
n = ((n & 0xAAAAAAAAAAAAAAAAu)>>1) + (n & 0x5555555555555555u);
// 32 2-bit numbers
n = ((n & 0xCCCCCCCCCCCCCCCCu)>>2) + (n & 0x3333333333333333u);
// 16 4-bit numbers
n = ((n & 0xF0F0F0F0F0F0F0F0u)>>4) + (n & 0x0F0F0F0F0F0F0F0Fu);
// 8 8-bit numbers
n += n >> 32;
// 4 8-bit numbers
n += n >> 16;
// 2 8-bit numbers
n += n >> 8;
// 1 8-bit number
return n & 0xFF;
}
(not tested)
The idea is "addition of small numbers in parallel".
There's also the "Bit Twiddling Hacks"-Site:
http://graphics.stanford.edu/~seander/bithacks.html
Cheers!
SG
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]