TalkChess.com

Code: Select all

                    High bit                                                 Low bit

        input:  N = 0001000000001000100000000000000000000100000000000100000000010000 (64-bit binary integer)
                                    ^     ^              ^
                                    k1    k              k2
                k =                       41
        output: R = 0000000000000000111111111111111111111100000000000000000000000000 (64-bit binary integer)

Code: Select all

        input:  N = 0001000000001000100000000000000000000100000000000100000000010000 (64-bit binary integer)
                       ^  ^     ^
                       k1 k     k2
                k =       57
        output: R = 0001111111111000000000000000000000000000000000000000000000000000 (64-bit binary integer)

Code: Select all

while ( copyOfN )
{
    int sq = msb_nr( copyOfN ); // most significant bit
    ...
    copyOfN &= ~&#40;1 << sq&#41;;
&#125;

Code: Select all

// Most significant bit number.
// Get the position of the most significant bit (0-63). 
// \return 0-63 and NoSquare for an empty bitboard.
// (== log2)
// (Version with big table)
SquareType msb_nr_big_table( BB bb )
{
    static const byte log2table[256] =
    {
       64, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 
        4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 
        5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 
        5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 
        6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 
        6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 
        6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 
        6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 
        7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 
        7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 
        7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 
        7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 
        7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 
        7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 
        7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 
        7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7
    };
    if ( bb & C(0xffffffff00000000) )
    {
        if ( bb & C(0xffff000000000000) )
        {
            if ( bb & C(0xff00000000000000) )
                return log2table[bb >> 56] + 56;
            return log2table[bb >> 48] + 48;
        }
        else
        {
            if ( bb & C(0x0000ff0000000000) )
                return log2table[bb >> 40] + 40;
            return log2table[bb >> 32] + 32;
        }
    }
    else
    {
        if ( bb & 0xffff0000 )
        {
            if ( bb & 0xff000000 )
                return log2table[bb >> 24] + 24;
            return log2table[bb >> 16] + 16;
        }
        else
        {
            if ( bb & 0x0000ff00 )
                return log2table[bb >> 8] + 8;
            else if ( bb & 0x000000ff )
                return log2table[bb];
            else
                return NoSquare;
        }
    }
}


#ifdef _MSC_VER
// Most significant bit number.
// Get the position of the most significant bit (0-63). 
// \return 0-63 and NoSquare for an empty bitboard.
// (== log2)
// (Version with bsr = bit scan reverse )
SquareType msb_nr_bsr( BB bb )
{
    static const unsigned long zero_value = NoSquare;
    __asm
    {
        mov eax, [DWORD PTR bb + 4]
        bsr eax, eax
        jne Upper
        mov eax, [DWORD PTR bb + 0]
        bsr eax, eax
        cmove eax, [zero_value]
        jmp Done
      Upper:
        add eax, 32
      Done:
    };
}
#endif


// Most significant bit number.
// Get the position of the most significant bit (0-63). 
// \return 0-63 and NoSquare for an empty bitboard.
// (best version)
SquareType msb_nr( BB bb )
{
#ifdef _MSC_VER
    return msb_nr_bsr(bb);
#else
    return msb_nr_big_table(bb);
#endif
}

Code: Select all

/*
 * left[k] has bits 0..k-1 set, others null
 * right[k] has bits k+1..63 set, others null
 * obviously if k-1<0 or k+1>63, then these are null bitboards
 * I let you write the code to precompute these
*/
uint64_t left&#91;64&#93;, right&#91;64&#93;;

/*
 * bit_segment&#91;k1&#93;&#91;k2&#93; has bits k1..k2 set others null
 * you can assume k1 < k2, and zero fill the rest
*/
uint64_t bit_segment&#91;64&#93;&#91;64&#93;;

uint64_t your_function&#40;uint64_t x, unsigned k&#41;
&#123;
  unsigned k1 = msb&#40;x & left&#91;k&#93;);
  unsigned k2 = lsb&#40;x & right&#91;k&#93;);
  /* you need to decide what you do if x & left&#91;k&#93; == 0, or x & right&#91;k&#93; == 0, not described in your spec. what if x = 0 for example ? */
  return bit_segment&#91;k1&#93;&#91;k2&#93;;
&#125;