Author: Gerd Isenberg
Date: 13:22:59 01/10/04
Go up one level in this thread
On January 10, 2004 at 15:58:09, Jaime Benito de Valle Ruiz wrote:
>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
X86 bsr-instruction or probably lookup methods like Eugene's, with a furher
1<<idx:
int EugeneBitscan (Bitboard arg) {
int result = 0;
if (arg > 0xFFFFFFFF) {
arg >>= 32;
result = 32;
}
if (arg > 0xFFFF) {
arg >>= 16;
result += 16;
}
if (arg > 0xFF) {
arg >>= 8;
result += 8;
}
return result + tableMSB[arg];
}
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.