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 (i=0; i<256; i++) {
        ms1bTable[i] = (
            (i>127) ? 7 :
            (i> 63) ? 6 :
            (i> 31) ? 5 :
            (i> 15) ? 4 :
            (i>  7) ? 3 :
            (i>  3) ? 2 :
            (i>  1) ? 1 :
                      0
        );
    }

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).