Author: Scott Gasch
Date: 23:51:29 01/06/03
Go up one level in this thread
On January 06, 2003 at 23:25:57, Nathan Thom wrote:
>Hi all,
>
>Does anyone have a super duper algorithm to count the number of set bits in a
>64-bit number? In C, i have:
>
>int CountBits(BitBoard *b) {
> int count=0;
>
> while (*b) {
> if (*b & (BitBoard)1) count++;
> *b >>= 1;
> }
>
> return count;
>}
>
>But im sure it could be much faster in assembler, i just dont know how.
I think what's fastest depends a lot on the typical characteristics of the
bitboard and the machine you run it on.
1. Shifting and/or masking is ok but you will always need 64 loop tests, 64
ands, 64 shifts, potentially 64 adds, etc.
2. Someone already said this one... and the number with itself minus one. If
you subtract one from 0y0010001000 you will get 0y0010000111. When you and them
together you get 0y0010000000 -- every time through you lose the lowest order
set bit so the loop runs exactly the number of set bits in the bitboard. Really
good for sparse data... better than shifting and/or masking almost always.
3. If you can get a reasonable lookup table in a cache line maybe try looking up
every byte (nibble, etc) in a table. The first one hit memory and the rest
comes from cache. Cache lines on K7's are 64 bytes large, I think.
4. Again someone has already posted the magic solution using 0y101010101... then
0y1100110011... and then 0y1111000011110000....
Good luck,
Scott
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.