Fastest way to parse a bitboard

Question

I am making a chess engine, and for now I’m working on the move generation. I’m using bitboards, and so for example my magic bit boards file for a knight on d4 is

00000000
00000000
00101000
01000100
000N0000
01000100
00101000
00000000

Which is represented by some unsigned long long integer.

I need this in a format where I can store the moves in a move list, and also make the move. E.g. {10,12,17,21,33,37,42,44}

What would be the fastest way to get the indices of the “1” bits in the bitboard during runtime? Currently I isolate the least significant 1 bit with x &= -x, and then XOR the position until I get 0. But is there a faster way to do this?

Answer 1

I found some well hidden pages in the Chess Programming Wiki.

The first one basically introduces your solution:

https://www.chessprogramming.org/Bitboard_Serialization#Single_Bits

However, the next chapter states that most applications are interested in the index of the square rather than its bitboard representation:

https://www.chessprogramming.org/Bitboard_Serialization#Square_Index_Serialization

This is done using a bitscan routine. There is another page dedicated to them:

https://www.chessprogramming.org/BitScan

It shouldn't be a surprise that the fastest method is to use processor specific instructions:

https://www.chessprogramming.org/BitScan#bsfbsr

If this is not possible, there are many other algorithms described there, which you can choose from.

There is also a Java dedicated version of this page, which describes API methods, which may be intrinsified by the VM:

https://www.chessprogramming.org/Java-Bitscan