If you already know k1 and k2 you could use Martin's formula (slightly changed):
result in a table indexed by the lowest 8 bit of the shifted N.
That would to a degree also work with more bits for the range. But the
range. The index would have twice the number of bits than the maxium range.
You can find k2 as the biggest sq below k and k1 as the smalles sq over k.
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
}
There are more algorithms for msb numbers or lsb numbers.
See the chessprogramming wiki or the other side of a Google search.