Author: Walter Faxon
Date: 15:49:27 11/17/02
Go up one level in this thread
Hi, Joel.
Here's my hack to find, remove and report the low-order bit in a bitboard.
I find it a little faster than Gerd's generic solution, but you should
experiment. Also, strangely, coding either method as a macro rather than
as an inline function can sometimes improve speed, depending on the compiler.
-- Walter
Code follows:
// ---------------------------------------------------------------------------
typedef unsigned long long u64; // nonstandard
typedef unsigned long u32;
typedef unsigned char u8;
extern const u8 LSB_64_table[154]; // bit number table
#define LSB_64_adj -51 // offset to table base
#define LSB_64_magic ( (u32)0x01C5FC81 ) // magic constant
// ---------------------------------------------------------------------------
// LSB_64() -- find, remove, report least-significant bit of 64.
// Argument 'bb' must be non-null. Method: fold then table lookup.
// Written by Walter Faxon, June 2002. No copyright. No warranty.
//
inline // inline declaration may differ by compiler
u8 LSB_64( u64* bb )
{
u64 t64;
u32 t32;
t64 = *bb - 1;
*bb &= t64; // omit this line to retain current LSB
t64 ^= *bb;
t32 = (u32)t64 ^ (u32)(t64 >> 32);
t32 ^= LSB_64_magic;
t32 += t32 >> 16;
t32 -= t32 >> 8;
return LSB_64_table [LSB_64_adj + (u8)t32];
}
// ---------------------------------------------------------------------------
// Table reports number of low-order bit as 0, high-order as 63.
// (Numbering can be reversed by changing this table.)
// Important: arrange storage so that this table is kept in the cache.
const u8 LSB_64_table[154] =
{
#define __ 0
23,__,__,__,31,__,__,39,19,__, 17,16,18,__,47,10,20, 9, 8,11,
1, 0, 2,57,56,58, 3,12,__,59, __,__,21,__, 4,__,__,60,__,__,
__,__,__,13,__,__,__,__,__,__, 5,__,__,61,__,__,__,__,__,__,
__,__,__,__,22,__,__,__,30,__, __,38,__,__,__,14,__,__,46,__,
__,__, 6,__,__,62,__,__,__,54, __,__,__,__,__,__,__,__,__,__,
29,__,__,37,__,__,__,__,__,__, 45,__,__,__,__,__,28,__,__,36,
__,53,__,__,27,__,44,35,26,24, 25,34,32,33,43,40,41,52,42,15,
__,50,48,49,__,51, 7,__,__,63, __,__,__,55
#undef __
};
//eof
===============================================================================
On November 17, 2002 at 16:00:35, Gerd Isenberg wrote:
>Hi Anthony,
>
>i havn't compared it in an simple loop running n times and mesured the time.
>The effect in my chess program is rather significant, a few percent if i
>remember well. To traverse bitboards, i use this version, which resets the found
>bit as well:
>
>__forceinline UINT BitSearchAndReset(BitBoard &bb)
>{
>#ifdef _M_IX86
>#ifdef FASTEST_AND_SAFEST
> __asm
> {
> xor edx, edx
> mov ebx, [bb]
> mov eax, edx
> inc edx
> bsf ecx, [ebx]
> jnz found
> bsf ecx, [ebx + 4]
> lea ebx, [ebx + 4]
> xor eax, 32
> found:
> shl edx, cl
> xor eax, ecx
> xor [ebx], edx
> }
>#else
> __asm
> {
> mov edx, [bb]
> bsf eax, [edx+4]
> xor eax, 32
> bsf eax, [edx]
> btr [edx],eax
> }
>#endif
>
>#else // _M_IX86
> BitBoard lsbb = bb & (-(__int64)bb);
> bb ^= lsbb;
> UINT32 lsb = LOWBOARD(lsbb) | HIGHBOARD(lsbb);
> return ((((((((((HIGHBOARD(lsbb)!=0) <<1)
> ^((lsb & 0xffff0000)!=0))<<1)
> ^((lsb & 0xff00ff00)!=0))<<1)
> ^((lsb & 0xf0f0f0f0)!=0))<<1)
> ^((lsb & 0xcccccccc)!=0))<<1)
> ^((lsb & 0xaaaaaaaa)!=0);
>#endif
>}
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.