faster than bsf and bsr

[Cardoso]

Hi,
one way to find the least significant bit of the 'path' bitboard would be:
bit=(path&-path);
now bit is a bitboard with only one bit set wich is the LSB of path.
What about the MSB of path?
The reason I ask is that if I knew how to do it for MSB then I could stuff this into a
bit = dir<2 ? (path&-path) : (expression for MSB);
construct in wich a recent compiler would make branchless code.
This way it would be faster going through the 4 diagonals in my checkers engine wich have flying kings (queens) and generating captures for the flying kings is slow.
Can anyone help me with the expression for MSB wich would return a bitboard with only one bit set wich would be the MSB?

Thanks in advance,
Alvaro

[Gerd Isenberg]

Hi,
one way to find the least significant bit of the 'path' bitboard would be:
bit=(path&-path);
now bit is a bitboard with only one bit set wich is the LSB of path.
What about the MSB of path?
The reason I ask is that if I knew how to do it for MSB then I could stuff this into a
bit = dir<2 ? (path&-path) : (expression for MSB);
construct in wich a recent compiler would make branchless code.
This way it would be faster going through the 4 diagonals in my checkers engine wich have flying kings (queens) and generating captures for the flying kings is slow.
Can anyone help me with the expression for MSB wich would return a bitboard with only one bit set wich would be the MSB?

Thanks in advance,
Alvaro

MS1B isolation is quite expensive and most rely on bsr-instrinsics to get the bit-index:

Code: Select all

x |= x >> 32; // for 64-bit words, skip for 32-bit
x |= x >> 16;
x |= x >>  8;
x |= x >>  4;
x |= x >>  2;
x |= x >>  1;
MS1B = (x >> 1) + 1;

With masked diagonals or files, with only max one bit set per byte, one may use two bswaps tp temporary swap the bytes for "reversed" two's complement:

Code: Select all

x = _byteswap_uint64(path);
x = x & -x; // reversed LS1B
bit = _byteswap_uint64(x);

Gerd

[Gerd Isenberg]

The reason I ask is that if I knew how to do it for MSB then I could stuff this into a
bit = dir<2 ? (path&-path) : (expression for MSB);
construct in wich a recent compiler would make branchless code.
This way it would be faster going through the 4 diagonals in my checkers engine wich have flying kings (queens) and generating captures for the flying kings is slow.

I actually added code for a generalized bitscan in the Wiki, which might be what you are looking for:
http://chessprogramming.wikispaces.com/ ... cBitScan15

Code: Select all

int bitIdx = bitScan(path, i >= 2);

Gerd

[Cardoso]

Thanks,
Alvaro

[Cardoso]

If instead of the bit index one want's to return a bitboard with only the bit in question set, how would you code that generalized BitScan?

Thanks,
Alvaro

[Pradu]

You can do b&-b.

[Gerd Isenberg]

If instead of the bit index one want's to return a bitboard with only the bit in question set, how would you code that generalized BitScan?

Thanks,
Alvaro

You may lookup the single bit bitboard (either LS1B or MS1B) by the scanned index. 1 << bitidx is likely slower in 32-bit mode. X86 hat the bit-test family instructions with set, reset and toggle bit, available via intrinsics. See "Bit by Square":
http://chessprogramming.wikispaces.com/ ... erations63

for instance:

Code: Select all

U64 isolateBit (U64 bb, bool mostSignificant) {
   assert (bb != 0);
   U64 one   = 1;
   U64 rMask = -(U64)mostSignificant;
   return one << bitScanReverse&#40;bb & (-bb | rMask&#41;);
&#125;

Gerd

[Gerd Isenberg]

You can do b&-b.

Yes, for least significant bit. Alvaro wants either LS1B or MS1B by boolean parameter. Is it correct to call it generalized bitscan?

[Pradu]

You can do b&-b.

Yes, for least significant bit. Alvaro wants either LS1B or MS1B by boolean parameter. Is it correct to call it generalized bitscan?

Sorry, I didn't follow the thread clearly. I guess it wouldn't be a generalized bitscan.

[mambofish]

I have wasted literally days trying to see if this could be done. Finally it dawned on me that there can be no simple parallel function to get MSB. The reason is that bitwise instructions such as and, or, xor, sub, not complent and so on depend only on the bits at and to the "right" of the input operand (i.e towards LSB). Since turning off the MSB requires looking "left" to find out if that bit in question is the MSB, it can't be done just using bitwise parallel operators.

To obtain the MSB you need to count the number of leading zeros. This can be done branch-free in just a few instructions. You then need to convert the result into the relevant bit number, usually by means of magic number (de bruijn sequence) table lookup.

Whatever you do though, you won't outperform bsf