Author: Russell Reagan
Date: 21:03:13 02/02/04
Go up one level in this thread
On February 02, 2004 at 23:19:45, Omid David Tabibi wrote:
>Have you compared various C/C++ codes for findFirstBitTrue on 32-bit data?
I'm not exactly sure what the definition of findFirstBitTrue means, but I'll
give it a guess. I assume you don't want what I posted, or you wouldn't still be
asking :) From your other post, I assume this is basically the same thing as the
64-bit bitscanning routines, but you want a 32-bit version since your program
uses 32-bit values in the attack tables. Am I right?
The concepts used in all of the bitscanning routines that I posted should be
applicable to any size variable (64-bit, 32-bit, whatever). I don't have 32-bit
versions of these, but they shouldn't be difficult to write.
There are three basic ideas working in these bitscans. The first is 'divide and
conquer' in the form of a binary search. This is what Eugene's bitscan does. As
you notice in this code, each section eliminates half of the bits.
int EugeneBitscan (Bitboard arg) {
int result = 0;
if (arg > 0xFFFFFFFF) { // Find out if the LSB is in the lower
arg >>= 32; // or upper 32-bits
result = 32;
}
if (arg > 0xFFFF) { // Find out if the LSB is in the lower or upper
arg >>= 16; // 16-bits, of the remaining 32-bits (we ruled out
result += 16; // the other 32-bits)
}
if (arg > 0xFF) { // Find out if the LSB is in the lower or upper
arg >>= 8; // 8-bits of the remaining 16-bits
result += 8;
}
return result + table8[arg]; // lookup the remaining
// 8-bits in a lookup table
}
For a 32-bit version, you could probably just cut out the first if-statement. So
it would look something like this (untested).
int EugeneBitscan (Bitboard arg) {
int result = 0;
if (arg > 0xFFFF) { // Find out if the LSB is in the lower or upper
arg >>= 16; // 16-bits
result += 16;
}
if (arg > 0xFF) { // Find out if the LSB is in the lower or upper
arg >>= 8; // 8-bits of the remaining 16-bits
result += 8;
}
return result + table8[arg]; // lookup the remaining
// 8-bits in a lookup table
}
That's pretty good. Only two if-statements and an 8-bit table lookup which is
likely to be in the cache. Eugene said that this would actually translate into
branchless code, so if that happens, even better. One alternative is to use
bitwise ANDs instead of >'s in the if-statements. i.e. if (arg & 0xFFFF0000)
instead of if (arg > 0xFFFF). I don't know that it matters.
The second approach is to use a 'magic' number. I'll save you from listening to
me try to explain this approach. You'd better just read this paper instead.
"Using de Bruijn Sequences to Index a 1 in a Computer Word" by Charles E.
Leiserson, Harald Prokop, Keith H. Randall
http://citeseer.nj.nec.com/leiserson98using.html
It basically involves a multiplication and a table lookup. It didn't score so
well for a 64-bit bitscan on 32-bit hardware, because a 64-bit multiply on
32-bit hardware is slow. A 32-bit multiply isn't the fastest thing in the world,
but it might do well.
int MagicBitscan (const Bitboard b) {
const Bitboard lsb = b & -b; // Isolate the LSB bit
return table[(lsb * magic) >> 58]; // Do the magic...
}
The last method was basically a brute force approach, looking at each 16-bit
portion of the value and finding the first bit via a 16-bit lookup table. For a
32-bit value, that is only two lookups, or you could use an 8-bit table for
cache friendliness and do potentially 4 lookups. The 64-bit one looks like this.
int TableBitscan16 (Bitboard b) {
static const Bitboard TwoFullRanks = 65535;
static const Bitboard FPMask1 = (Bitboard) TwoFullRanks << 16;
static const Bitboard FPMask2 = (Bitboard) TwoFullRanks << 32;
if (b & TwoFullRanks)
return table16[b & TwoFullRanks];
if (b & FPMask1)
return table16[(b >> 16) & TwoFullRanks] + 16;
if (b & FPMask2)
return table16[(b >> 32) & TwoFullRanks] + 32;
return table16[b >> 48] + 48;
}
You can fiddle with those to turn them into 32-bit versions if you want, or I
can do it later in the week if you're willing to wait. I'm just busy with work
and school for the next few days. Hope this helps, for now.
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.