Author: Dan Newman
Date: 16:49:48 08/19/99
Go up one level in this thread
On August 19, 1999 at 18:12:35, Johannes Buchner wrote:
>Hi there !
>
>I just wanted to know if anybody out there knows a different way how to do this
>than using table-lookups like crafty. Is really no other mathematical
>possibility ? By the way, do you know any Internet resources that deal with
>problems like this (I think there is a method to do popcount without
>table-lookups, e.g.) ? In the 'Dark Thought' description they're talking about
>'Hacker's memory', a 'well-known collection of programming tricks'. Ever heard
>of it ? I haven't !
>So if you know anything intersting about that topic, please let me know (and all
>the otherz of course !)
>
> Thanks Johannes
There are a lot of different ways you can do this in C using table lookups
or calculations of course, but the fastest way I've seen so far (on a PC)
is to use the BSF and/or BSR instructions. The mnemonics stand for
bit-scan-forward and bit-scan-reverse, and they find the index of least
(most) significant one bit. These are fairly fast on the P6, PII, etc.,
but not on some of the older processors (486,386, etc.). I used the
following to access BSF and BSR from Watcom C++:
/*
This inline assembly language pragma
gives access to the BSF opcode.
*/
extern int bsf( uint32 bitpat);
#pragma aux bsf = \
"bsf eax, eax" \
parm [eax] \
value [eax] \
modify [eax];
/*
Giving C direct access to the BSR opcode via
inline assembly languge pragma.
*/
extern int bsr( uint32 bitpat);
#pragma aux bsr = \
"bsr eax, eax" \
parm [eax] \
value [eax] \
modify [eax];
I used them to implement a first_one (and last_one) function:
//
// I've measured this one at about one bit index every 9 to 10 clocks
// on the P6/200. The previous best using tables from last year was
// about 16 clocks/index. This one can be inlined at very low cost in size.
//
inline int first_one( uint32 &low, uint32 &high)
{
if( low ) {
int index = bsf( low);
low ^= (1ul << index); // Clear the bit.
return index;
} else if( high) {
int index = bsf( high);
high ^= (1ul << index);
return index+32;
} else {
return 64;
}
}
Each compiler will of course have its own way of accessing these
via inline assembly, and there may be better ways to get at them
using Watcom too...
-Dan.
This page took 0.01 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.