Computer Chess Club Archives


Search

Terms

Messages

Subject: mask of highest bit

Author: Andrew Shapira

Date: 01:35:02 09/21/05


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)?



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.