Author: Tom Kerrigan
Date: 20:12:32 04/18/00
Go up one level in this thread
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. > >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 >Flemming There are x86 instructions to solve problem 1. So you can do some inline assembly trickery. I can't remember what the instructions are called off the top of my head, though. For problem 2, there is a way to use masks and addition to essentially count the bits in parallel (no branches necessary). This is a pretty well known algorithm and easy to find on the Web if you search for "bit counting" or somesuch. Sorry I can't help you with more specific details, but at least now you know there are other ways. :) -Tom
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.