Computer Chess Club Archives


Search

Terms

Messages

Subject: Bitcount explained

Author: Oliver Roese

Date: 19:04:54 04/19/00

Go up one level in this thread


On April 19, 2000 at 11:02:52, Ernst A. Heinz wrote:

>Hi Flemming,
>
>>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.
>>
>>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));
>>
>>
>>Is there anything faster, ie. such lookuptables or machine code intrutions?
>>
>>What about problem 1?
>>
>>Thanks in advance for any reply
>
>My article about "How DarkThought Plays Chess" in the ICCA
>Journal 20(3), pp. 166-176, Sept. 1997 contains some valuable
>information about your subject of interest.
>
>Please have a look at the WWW pages of "DarkThought" at URL
>http://supertech.lcs.mit.edu/~heinz/dt/ in order to find an
>electronic preprint of this article among others.
>
>=Ernst=

I found the following (on http://supertech.lcs.mit.edu/~heinz/dt/node7.html):

...
Otherwise, DARKTHOUGHT prefers the following non-iterative formulation that
stems from the well-known ``Hacker's Memory''
collection of programming tricks. It performs better than intuitive methods with
lookup tables because the tables get either too large
or need too many lookups.1.3

#define m1 ((unsigned_64) 0x5555555555555555)
#define m2 ((unsigned_64) 0x3333333333333333)

unsigned int non_iterative_popcount(const unsigned_64 b) {
    unsigned_32 n;
    const unsigned_64 a = b - ((b >> 1) & m1);
    const unsigned_64 c = (a & m2) + ((a >> 2) & m2);
    n = ((unsigned_32) c) + ((unsigned_32) (c >> 32));
    n = (n & 0x0F0F0F0F) + ((n >> 4) & 0x0F0F0F0F);
    n = (n & 0xFFFF) + (n >> 16);
    n = (n & 0xFF) + (n >> 8);
    return n;
}
...

(The mentioned 'Hackers Memory' can be found at
http://www.inwap.com/pdp10/hbaker/hakmem/hakmem.html
There are other methods shown to count bits, some of them utilizing
multiplications.
This text is demanding i think. There are seldom explanations and programming is
in PDP-11-assembler.)

I try to shortly explain, how it works:

     const unsigned_64 a = b - ((b >> 1) & m1);

This line adds adjacent bits together, leaving 32 adjacent 2-bitnumbers in a,
each in {0,1,2}. This line could also be written as:

     const unsigned_64 a = (b & m1) + ((b >> 1) & m1);

but the tricky form is more efficient.

     const unsigned_64 c = (a & m2) + ((a >> 2) & m2);

This line adds these adjacent 2-bit numbers together, leaving 16 adjacent
4-bitnumbers from {0,...,4} in c.

    n = ((unsigned_32) c) + ((unsigned_32) (c >> 32));

Adds the 8 tophalf numbers to the corresponding 8 bottomhalfnumbers, leaving
8 adjacent 4-bitnumbers from {0,...,8} in the 32bitword n.
I think the progress is obvious from here:

    n = (n & 0x0F0F0F0F) + ((n >> 4) & 0x0F0F0F0F);

Adds adjacent 4-bitnumbers, leaving 4 adjacent 8-bitnumbers from {0,...,16}.

    n = (n & 0xFFFF) + (n >> 16);

Adds the 4 tophalf numbers to the corresponding 4 bottomhalf numbers, leaving
2 8-bitnumbers from {0,...,32} in the bottom half of n.

    n = (n & 0xFF) + (n >> 8);

Add the chars together.

Using MMX-Instructions, the implementation could be vastly improved.
I hope it helps.


Oliver Roese



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.