ms1bTable array in Eugene Nalimovs bitScanReverse

[sluijten]

I guess I could find myself, but choose the lazy way: how does the ms1bTable array look like in Eugene Nalimovs bitScanReverse:

/**
* bitScanReverse
* @author Eugene Nalimov
* @param bb bitboard to scan
* @return index (0..63) of most significant one bit
*/
int bitScanReverse(U64 bb)
{
int result = 0;
if (bb > 0xFFFFFFFF) {
bb >>= 32;
result = 32;
}
if (bb > 0xFFFF) {
bb >>= 16;
result += 16;
}
if (bb > 0xFF) {
bb >>= 8;
result += 8;
}
return result + ms1bTable[bb];
}

[Sven]

Code: Select all

int ms1bTable[256];

void init_ms1bTable() {
    int i;
    for &#40;i=0; i<256; i++) &#123;
        ms1bTable&#91;i&#93; = (
            &#40;i>127&#41; ? 7 &#58;
            &#40;i> 63&#41; ? 6 &#58;
            &#40;i> 31&#41; ? 5 &#58;
            &#40;i> 15&#41; ? 4 &#58;
            &#40;i>  7&#41; ? 3 &#58;
            &#40;i>  3&#41; ? 2 &#58;
            &#40;i>  1&#41; ? 1 &#58;
                      0
        );
    &#125;

would be a possible initialization code.

Sven

[sluijten]

Great, thanks Sven
Stef

[Sven]

Of course, "bb != 0" is a precondition for bitScanReverse(). This implies that ms1bTable[0] is never used (0 has no "most significant one bit"). Before and after each "if (bb > ...)" block the condition "bb != 0" must be valid.

Sven

[sluijten]

If you want to catch the error bb = 0, you could make ms1bTable[0]=127, but I think it's better to make sure bb !=0 before calling the function (and don't test for it in the function).