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.