Author: Peter Klausler
Date: 07:38:13 06/05/98
Go up one level in this thread
On June 05, 1998 at 07:19:35, Guido Schimmels wrote:
>I've heard, the latest Alpha chip has an enhanced instruction set
>including a new FindBit()-instruction that can find the LSB of a word.
>The new chip is so fast already, but this new instruction should
>make crafty fly :-)
>Bob, some nps figures available for the new machines, I hope soon ?
>
>- Guido
I argued strongly for the EV6 to support these operations,
and it'll be interesting to see whether they're in the
final 21264 product.
Leading zero count (LZC) and bit population count (POP) are
two functions that are caught in a bind between languages and
architectures: neither C nor Fortran supports them in their
standard definitions, so architectures don't feel compelled
to support them, so there's no incentive to incorporate them
into the languages. Some microprocessors support one and not
the other. And yet they aren't all that hard to implement;
indeed, processors have LZC logic in their floating-point
result normalization stages.
Every Seymour machine since the CDC6600 has had them, and
I wonder how strong the Atkins/Slate CHESS program would
have been without them.
POP is somewhat more powerful because you can also use it to
implement a very cheap trailing zero count (TZC) function and
store your bit masks backwards. The method is left as an easy
exercise for the reader.
I use LZC and POP a lot in my own code; even when they don't
have hardware support, it's possible to implement them fairly
cheaply in software. LZC is invaluable for traversing bit
sets, such as in a graph coloring register assigner, and is
also a cheap "base-2 logarithm" estimator. POP is also good
for bit sets.
The cutest way that I know to implement POP without using lookup
tables in software is:
short
POP (unsigned long long x) {
x = (x & 0x5555555555555555LL) + ((x>> 1) & 0x5555555555555555LL);
x = (x & 0x3333333333333333LL) + ((x>> 2) & 0x3333333333333333LL);
x = (x & 0x0f0f0f0f0f0f0f0fLL) + ((x>> 4) & 0x0f0f0f0f0f0f0f0fLL);
x = (x & 0x00ff00ff00ff00ffLL) + ((x>> 8) & 0x00ff00ff00ff00ffLL);
x = (x & 0x0000ffff0000ffffLL) + ((x>>16) & 0x0000ffff0000ffffLL);
x = (x & 0x00000000ffffffffLL) + (x>>32);
return x;
}
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.