Computer Chess Club Archives




Subject: Countbits() Function

Author: Roberto Waldteufel

Date: 05:29:23 01/03/99

Hi all,

I recently did some code timing experiments, and I thought the results might be
useful to some of you here...

I coded two versions of a function to count the number of 1-bits in a bitboard.
One method is to use a loop with the bitscan instructions, repeated on the low
and high order 32-bit chunks. The other uses only logical instructions, with no
loops. See Ernst Heinz's DarkThought site for a detailed account of these
methods. I was interested to compare the methods on Pentium 32-bit architecture:
the loop is best when only a few bits are set (it terminates quickly) with time
proportional to the number of bits set, and the second method is faster if many
bits are set, since it does not depend on how many bits are set.

It turned out for me that the loop is preferable if at most 6 bits are set, and
for 7 or more bits the logical instructions perform best. With exactly 7 bits,
the difference is less than 1%. That was on a PII 333MHz box. The break-even
point would be much higher on any Intel without fast bit-scans, ie bit scans are
*much* faster on PII and PPro than on earlier Intel CPU's, whereas the logical
instructon method would take about the same time for any bitboard, dependant
only on clock speed.

Hope this is useful for someone....:-)


This page took 0.06 seconds to execute

Last modified: Thu, 07 Jul 11 08:48:38 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.