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.01 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.