Author: Chris Hull
Date: 17:47:49 01/10/04
Go up one level in this thread
On January 10, 2004 at 16:22:59, Gerd Isenberg wrote:
>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];
>}
Hmmm, this is interesting I will look at it closer. I like the idea.
Thanks.
Chris
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.