The two ideas I have:
One other possibility is, if the priorities are all grouped in contiguous 16-bit chunks, then you can do a Nalimov-style bitscan. As an example, here's a normal BSF, but with the priorities of the 4 groups reversed (hope this makes sense):
Code: Select all
if (bb & 0xffff000000000000)
sq = lsb[bb>>48];
else if (bb & 0x0000ffff00000000)
sq = lsb[bb>>32 & 0xffff];
else if (bb & 0x00000000ffff0000)
sq = lsb[bb>>16 & 0xffff];
else if (bb & 0x000000000000ffff)
sq = lsb[bb & 0xffff];
The other is inspired by the second bitscan here (created by Gerd), which does 6 tests, one for each bit of the final result: http://chessprogramming.wikispaces.com/BitScan#toc8
(btw, be sure to check out the FZ video at the bottom, coincidentally right now I am listening to an audience tape of the same song performed about 8 months later )
Simply take the priorities of the squares, and convert them to a "horizontal" array of 6 bitboards. Bitboard 0 will be the set of all squares with bit 0 set in their priority index, and so on. Then we loop through all the bitboards, except we need some special handling. We have to test the 32 highest priority bits first. If there is a bit in there, then we mask out all other bits and continue (I do this below with a simple -1/0 mask). Otherwise we do nothing, and we know that only bits with priorities <= 31 remain.
Code: Select all
bit5 = (bb & mask[5]) != 0;
bb &= mask[5] | (bit5-1); // assuming bit5 is a bitboard, probably a cast is smarter
result |= bit5; result <<= 1;