Bit Twiddling Fundamentals - Finding the least significant bit in a BitBoard

As explained in the post about board representation BitBoards are very efficient for applying certain conditions onto the board. The result is a BitBoard where those bits are set for which all applied conditions are true.

In the example for the move generation of white pawns we advanced all pawns one rank and filtered out those pawns reaching the 8th rank and those hitting another piece. The result was a BitBoard with valid target squares for simple pawn moves.

In order to make use of that result we must now translate the set bit positions back into squares. The naive way is just looping through the bitboard and looking at each single bit whether it is 1.

Something like

bb : BitBoard;

i : integer;

pos:=0;

while (pos<=63) and ((bb AND (2^pos))<>0) do inc(pos);

if pos<64 then ...

This finds the least significant bit in bb. You can now do something with this information. Then you delete this bit in bb via  bb := bb and NOT (2^pos) and start over again to find the next bit until bb is 0. Then all bits are processed.

This works but is slow. As finding a bit in a BitBoard is called millions of times during search for a best move you want that operation to be very fast. So this is not a reasonable approach.

There are better ways to do that. They might involve a look up tables or magic constants (search for DeBruijn).

The approach I took finally was relying on a processor instruction to do that. That makes the code less portable but it is most likely the fastest way to do that. Free Pascal supports in line assembler and my function looks like this


  function getLSB(const Input: Int64): Byte;  Assembler;
  // Returns the least significant bit of a 64 bits number
  // or ERROR if no bit is set
  asm
      bsf eax, dword ptr Input
      jz @@0
      jnz @@2
    @@0:
      bsf eax, dword ptr Input + 04h
      jz @@1
      add eax, 32
      jnz @@2
    @@1:
      mov eax, ERROR
    @@2:
  end;       


You must process the input in 2 steps as bsf (bit scan forward) works on 32 bit arguments.

I have similar functions for finding the most significant bit or counting the number of set bits in a BitBoard.