Author: Shane Hudson
Date: 16:20:28 04/25/01
Go up one level in this thread
On April 25, 2001 at 16:53:56, Bas Hamstra wrote:
>On April 25, 2001 at 14:53:00, Dann Corbit wrote:
>>On April 25, 2001 at 14:38:48, Bas Hamstra wrote:
>>>On April 25, 2001 at 14:31:27, Bas Hamstra wrote:
[stuff snipped]
>>This works fairly well (which is {I suspect}) what is in your table:
>>
>>static int inbits[256] = {
>> 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
....
>> 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
>>};
>>
>>int Count(const BITBOARD B)
>>{
>> return inbits[(unsigned char) B] +
>> inbits[(unsigned char) (B >> 8)] +
>> inbits[(unsigned char) (B >> 16)] +
>> inbits[(unsigned char) (B >> 24)] +
>> inbits[(unsigned char) (B >> 32)] +
>> inbits[(unsigned char) (B >> 40)] +
>> inbits[(unsigned char) (B >> 48)] +
>> inbits[(unsigned char) (B >> 56)];
>>}
>
>Yes, that's how my code works as well.
>
>>You might want to time this in comparison to your routine. For that matter, I
>>have a collection of bit counting routines found here:
>>ftp://cap.connx.com/pub/bitcount/BITC.ZIP
>>
>>That might prove useful. A benchmark routine is included. They are for 32
>>bits, but the techniques easily generalize to larger integers.
>
>Thanks, I will certainly take a look because I use it all the time and I am not
>quite satisfied with the current performance.
>
>Best regards,
>Bas.
Some time ago I profiled a number of bit-counting routines (on 32-bit
numbers, and for file system bitmap lookup code instead of chess, but
the techniques are similar for 64 bits) and found that for random inputs,
the "folding" method (it may have a real name, I don't know) with no
array lookups or branches was clearly the fastest, even beating lookups
of 256-element tables (like you have) or 65536-element tables. Here is
the folding method for 32 bits (it assumes unsigned longs are 32 bits):
int
bitcount (unsigned long x)
{
x = ((x & 0xAAAAAAAAUL) >> 1) + (x & 0x55555555UL);
x = ((x & 0xCCCCCCCCUL) >> 2) + (x & 0x33333333UL);
x = ((x & 0xF0F0F0F0UL) >> 4) + (x & 0x0F0F0F0FUL);
x = ((x & 0xFF00FF00UL) >> 8) + (x & 0x00FF00FFUL);
x = ((x & 0xFFFF0000UL) >> 16) + (x & 0x0000FFFFUL);
return (int) x;
}
The 64-bit equivalent has only one more "x = ...." expression, so it
scales logarithmically. I have it in a file somewhere...
However, when got curious and I modified crafty's PopCnt() to use this
method, I found no improvement -- which was surprising until I checked
the inputs and found the input value was almost always below 3, and
was 0 about 70% of the time. So the best method depends highly on
the distribution of input values.
Cheers,
Shane
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.