Re: is there a fast way to get every bit in a uint64_t
On Aug 26, 6:26 pm, "lfeiman...@gmail.com" <lfeiman...@gmail.com>
wrote:
hi,everybody,given a uint64_t ,if I want to know which bits are set in
it.
The number of bits set in an integer is often called its "population
count".
i will do a iterator with it,such as
uint64_t iSrc = 8394324;
uint64_t iTmp = 0;
for(int i = 0 ;i<64;i++)
{
iTmp = pow(2,i);
if(iTmp & iSrc)
{
printf("bit %d is set!!!!!!!!!!",i);
}
}
i 'm wandering ,is there a faster way to do this??? thank you !
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.
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;
}
Greg
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]