Author: Gerd Isenberg
Date: 02:58:09 09/21/05
Go up one level in this thread
On September 21, 2005 at 04:35:02, Andrew Shapira wrote:
>Hi - does anyone know of a way to find a mask of the highest bit in a word in
>O(1) time using only standard C operators = + - ^ ~ >> << (and no control flow
>statements like 'if')? The * and / operators might also be ok. In other words,
>I want to compute 1 << h(x), given x, where h is the highbit function that gives
>the index of the most significant bit set in x. I have a suspicion that this
>may be possible but I haven't yet read or devised a way to do it. It's possible
>to find the mask of the lowest 1 bit in O(1) time: return ((x^(x-1))+1) >> 1.
>This is nice in a chess program because it's almost as fast as using a hardware
>lowbit instruction, and it doesn't introduce hardware dependency. I want the
>same thing for the high bit. It's possible to find the mask of the highest bit
>in O(lg N) time, where N is the word size: x |= x >> 1; x |= x >> 2; x |= x >>
>4; x |= x >> 8; ...; return (x+1) >> 1. Can it be done in O(1) time (or proved
>not to be possible with those operators)?
Hi Andrew,
first, for masking the least significant one bit, you can use x & -x instead of
((x^(x-1))+1) >> 1.
For masking the most significant one bit, there is the O(ld N) parallel prefix
approach to set all lower bits, eg. for N = 64:
x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
x |= x >> 8;
x |= x >> 16;
x |= x >> 32;
ms1bmask = (x>>1) + 1;
Another way is to find the index of the MS1B via int/double conversion and to
interprete the exponent, here is a routine i recently posted in Winboard Forum:
typedef unsigned __int64 BitBoard;
union BB
{
BB(BitBoard b) {bb=b;}
double getSignedDouble() {return (double)(__int64)bb;}
BitBoard bb;
struct {
unsigned int lo;
unsigned int hi;
};
};
unsigned int bitScanReverse(BB bb)
{
union {
double d;
struct {
unsigned int mantissal : 32;
unsigned int mantissah : 20;
unsigned int exponent : 11;
unsigned int sign : 1;
};
} ud;
bb.lo &= ~bb.hi; // avoids rounding issues
ud.d = bb.getSignedDouble();
unsigned int idx = (ud.exponent - 1023) | (63*ud.sign);
return idx;
}
... and then to do 1L << bitScanReverse(bb)
Gerd
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.