Author: Gerd Isenberg
Date: 12:42:26 01/10/04
Go up one level in this thread
On January 10, 2004 at 14:28:58, Chris Hull wrote: >I am trying to find a fast algorithm that will return the closest bit to a given >bit. I searched google but found nothing. > >Here is an example problem stated as concisely as I can. > >Given: > > 111111 > 5432109876543210 // bit positions > >X = 0101000100000101 // binary >Postion = 8 > >/** Here is the problem we are trying to solve > Find nearest bit higher than bit number 8 and > find nearest bit lower than bit number 8 **/ > >X' = 0101000*00000101 > >so if > >Y = int FindNearestHigherBit( int X, int Position ); >Z = int FindNearestLowerBit( int X, int Position ); > >then > >Y = 0001000000000000 >Z = 0000000000000100 > >So I am looking for the function/algorithm for FindNearestHigherBit and >FindNearestLowerBit. I would like one that runs fast (ie one clock cycle) >and not a loop that looks at every bit. > >Ok, all you who were CS major in college help me out. Thanks in advance. > > >Chris http://aggregate.org/MAGIC/ http://graphics.stanford.edu/~seander/bithacks.html One possible solution on the fly: 1. Build two masks from position: M = 1<<pos; M1 = M-1; M2 = ~(M1|M); M = 0000000100000000 M1 = 0000000011111111 M2 = 1111111000000000 2. And x with both masks X1 = X & M1; X2 = X & M2; X = 0101000100000101 X1 = 0000000000000101 X2 = 0101000000000000 3. Perform lsb bit isolation with X2 Y = X2 & -X2; X2 = 0101000000000000 -X2= 1011000000000000 Y = 0001000000000000 4. Perform msb bit isolation with X1 A bit more complicated to isolate the msb. Set all lower bits with ld(n) or/shifts depending on the word size: X1 |= X1 >> 1; X1 |= X1 >> 2; X1 |= X1 >> 4; X1 |= X1 >> 8; // for 16 bit X1 |= X1 >> 16; // for 32 bit X1 |= X1 >> 32; // for 64 bit Z = (X+1)>>1; // x+1 can't overflow! X1 = 0000000000000111 X1+1= 0000000000001000 Z = 0000000000000100
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.