Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: fast bit counting

Author: Heiner Marxen

Date: 12:01:10 04/19/00

Go up one level in this thread


On April 19, 2000 at 14:32:33, Dan Newman wrote:

>On April 18, 2000 at 23:39:31, Dann Corbit wrote:
>
>>On April 18, 2000 at 22:44:25, Flemming Rodler wrote:
>>
>>>Hi,
>>>
>>>I am trying to implement a bitboard based chess program on a Pentium or AMD
>>>computer. I need to be able to find the following information fast:
>>>
>>>1) The position of the first and/or last bit in a sequence of 64 bits.
>>>2) Count the number of bits that are 1 in a sequence of 64 bits.
>>
>>#2:
>>
>>static char     nbits[256] =
>>{
>>    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             CountBits(BitBoard d)
>>{
>>    unsigned long  *n = (unsigned long *) &d;
>>    return
>>        nbits[(unsigned char) n[0]] +
>>        nbits[(unsigned char) (n[0] >> 8)] +
>>        nbits[(unsigned char) (n[0] >> 16)] +
>>        nbits[(unsigned char) (n[0] >> 24)] +
>>        nbits[(unsigned char) n[1]] +
>>        nbits[(unsigned char) (n[1] >> 8)] +
>>        nbits[(unsigned char) (n[1] >> 16)] +
>>        nbits[(unsigned char) (n[1] >> 24)];
>>}
>>
>
>
>Interesting.  I hadn't thought about using a cast to clip off the higher
>order bits--I use a mask (& 0xff).  I wonder which is faster, or if there
>is any difference...  Also, assuming unsigned long is 32 bits, you don't
>need the last cast since there are no higher bits to be clipped--not much
>of an optimization of course...

Since the table has size 256, the mask is correct.  That an unsigned char
contains no more than 8 bits is not guaranteed.  The cast is a portability
problem.

>I also use a loop style bit counter for bitboards that I know are going
>to be very sparse:
>
>class bitboard_t {
>  private:
>    unsigned long lower;
>    unsigned long upper;
>  public:
>    ...
>    int sparse_count() const {
>        int count = 0;
>        long b = lower;
>        while( b ) {
>            b &= ~(-b);
>            count++;
>        }
>        b = upper;
>        while( b ) {
>            b &= ~(-b);
>            count++;
>        }
>        return count;
>    }
>    ...
>};

Note please, that the above is not completely portable: on a 1-complement
machine it would break, since -b == ~b.  Better to stick to unsigned types
when manipulating bits:
         unsigned long b = lower;
         while( b ) {
             b &= b - 1;
             count++;
         }

AFAIK, that is as portable as it can be.

>-Dan.
>
>
>>For different machines/compilers, various methods may work better than others.
>>Here is a list of bit counting techniques:
>>ftp://38.168.214.175/pub/bitcount/BITC.ZIP
>>
>>>I know there is a method that works linear in the number of on-bits for
>>>problem 2:
>>>
>>>    for(count = 0; bitboard; count++, bitboard &= (bitboard -1));

Sic!
[snip]

Heiner



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.