Author: Peter Klausler
Date: 06:12:20 09/14/99
Go up one level in this thread
I assume that you are given a 64-bit value with exactly one bit set in it,
and that you want to find out which bit it is.
You can do this portably, or you can do this fast, but not both.
There are two useful integer functions available in most processor
instruction set architectures that are *not* accessible through
standard C or C++: leading zero count (LZC, also known as find first
one), and population count (POP). Either one can be used to find
a single set bit. Most architectures implement at least one of these.
LZC returns the bit position of the highest-order set bit in a word;
the sign bit is 0, the low-order bit is 63 (on real computers), and
if no bit is set it'll return -1 or 64 or be undefined.
POP counts the number of bits that are set in a word. You can
use POP to implement a "trailing zero count" function that works
for nonzero arguments: TZC(x) = POP(x ^ (x-1)) - 1. If you don't
see why that works, try it on a few values with paper and pencil
and you'll get it.
Some compilers provide access to LZC and/or POP via non-standard
extensions, possible with other names (consult your manual). Other
compilers, usually non-optimizing ones, allow you to insert inline
assembly code into C/C++ programs, and if your machine supports one
or the other you can get at it this way. Otherwise, you can write a
little assembly language subroutine that performs LZC or POP and just
call it, with some loss of performance from subroutine call overhead
and optimization restrictions.
Now if performance of these functions isn't critical to your program,
you can write a subroutine to find that set bit via a 6-level binary
search, or you can implement POP in C as follows and call it as
described above. It depends on your machine which would be faster,
so measure it, but on modern processors this POP function is likely
to be better due to its lack of jumps. (But if speed is really
all that important, use an extension, asm, or assembly language!)
unsigned char
POP (unsigned long x /* assumed 64 bits */) {
x = (x & 0x5555555555555555) +
((x >> 1) & 0x5555555555555555);
x = (x & 0x3333333333333333) +
((x >> 2) & 0x3333333333333333);
x = (x & 0x0f0f0f0f0f0f0f0f) +
((x >> 4) & 0x0f0f0f0f0f0f0f0f);
x += x >> 8;
x += x >> 16;
x += x >> 32;
return (unsigned char) x;
}
/* Warning: the above code is from memory, be sure to test it, and
don't use it if you don't understand the trick I'm using here. */
Peter Klausler (pmk@cray.com), an architecture/compiler/simulator guy
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.