Author: Jaime Benito de Valle Ruiz
Date: 12:58:09 01/10/04
Go up one level in this thread
On January 10, 2004 at 15:42:26, Gerd Isenberg wrote: >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 is the first idea I could come up with, but the msb, as you pointed, is the real problem, because this "folding" is the only one I can remember. Isn't there any easier way to find the msb? Jaime
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.