Looking for intrinsic "least significant bit" on Visual Studio

[Gerd Isenberg]

This shows all the options...

https://en.wikipedia.org/wiki/Find_first_set

This one is most interesting:

Code: Select all

ctz(x) = popcount((x & −x) − 1)

Most useful would be ctz_0, or bsf_0, which returns the bitno and clears it in one instruction, eg

bsf_0 r1, r2 // return bitno in r1, clears the corresponding bit in r2

This eliminates all except the lowest bit:

Code: Select all

x &= -x

This clears the lowest bit in x:

Code: Select all

x &= x - 1

I am not sure if there are such nice tricks with the most significant bit.

Related CPW pages: BitScan, least significant one bit, and most significant one bit. Due to the carry or borrow propagation, most significant one bit isolation requires some more computation. In some cases one may apply reverse arithmetic, see HQ.

[OliverBr]

Msbit is way more problematical. Rule for chess engines is work with lsbit and move upwards.
I didn’t find a reason yet to work the other way round.

Actually I found a good reason and tried to implement it once:

When scanning the 64-bit boards for move generation it would make sense for white to do it with msbit, because more forward pieces would be processed first. This may improve move ordering.

I didn't notice any strength gain, but on the other hand I haven't got the 32-core server yet and couldn't tell anything for sure.

[chrisw]

Msbit is way more problematical. Rule for chess engines is work with lsbit and move upwards.
I didn’t find a reason yet to work the other way round.

Actually I found a good reason and tried to implement it once:

When scanning the 64-bit boards for move generation it would make sense for white to do it with msbit, because more forward pieces would be processed first. This may improve move ordering.

True. Although you could achieve the same (in that movegen scenario) by using bsf and processing the movelist backwards for black.

I didn't notice any strength gain, but on the other hand I haven't got the 32-core server yet and couldn't tell anything for sure.

[Gerd Isenberg]

Msbit is way more problematical. Rule for chess engines is work with lsbit and move upwards.
I didn’t find a reason yet to work the other way round.

Actually I found a good reason and tried to implement it once:

When scanning the 64-bit boards for move generation it would make sense for white to do it with msbit, because more forward pieces would be processed first. This may improve move ordering.

I didn't notice any strength gain, but on the other hand I haven't got the 32-core server yet and couldn't tell anything for sure.

A suggestion for color agnostic bitboard traversal is conditional byteswap.

Code: Select all

if ( x ) {
   U64 m = (U64)color - 1; // e.g. -1 if white, 0 for black
   int o = (int)m & 56;
   x = x ^ ((x ^ flipVertical(x)) & m); // conditional flip
   do {
      int idx = bitScanForward(x) ^ o; // square index from 0..63
      *list++ = foo(idx , ...);
   } while (x &= x-1); // reset LS1B
}

One may color-flip the board in make move to even generate white moves always

[OliverBr]

Hello,
For Windows exes I want to give mingw a chance, but it won't compile because of the "_tzcnt_u64" method. The error messagt does not much sense to me:

Code: Select all

x86_64-w64-mingw32-gcc -Ofast olithink.c -o OliThink.exe
In file included from /usr/lib/gcc/x86_64-w64-mingw32/8.3-win32/include/immintrin.h:93,
                 from /usr/lib/gcc/x86_64-w64-mingw32/8.3-win32/include/x86intrin.h:48,
                 from /usr/share/mingw-w64/include/winnt.h:1554,
                 from /usr/share/mingw-w64/include/minwindef.h:163,
                 from /usr/share/mingw-w64/include/windef.h:8,
                 from /usr/share/mingw-w64/include/windows.h:69,
                 from olithink.c:6:
olithink.c: In function 'pullLsb':
/usr/lib/gcc/x86_64-w64-mingw32/8.3-win32/include/bmiintrin.h:172:1: error: inlining failed in call to always_inline '_tzcnt_u64': target specific option mismatch
 _tzcnt_u64 (unsigned long long __X)
 ^~~~~~~~~~
olithink.c:12:19: note: called from here
 #define getLsb(x) _tzcnt_u64(x)
                   ^~~~~~~~~~~~~
olithink.c:12:19: note: in definition of macro 'getLsb'
 #define getLsb(x) _tzcnt_u64(x)
                   ^~~~~~~~~~

Do you have a tip, how I can solve this? Here is the relevant code snippet from line 5 to 13:, __popcnt64(x) doesn't make problems. Using _tzcnt_u64(x) directly without #define brings the same error.

Code: Select all

#if defined(_WIN32) || defined(_WIN64)
#include <windows.h>
#include <conio.h>
#include <sys/timeb.h>
#include <intrin.h>
struct _timeb tv;
#define _bitcnt(x) __popcnt64(x)
#define getLsb(x) _tzcnt_u64(x)
#else

[mar]

a late reply, you've probably solved this since.

you should be able to use gcc builtins with mingw:
__builtin_clzll and __builtin_ctzll

they compile to lzcnt/tzcnt but you have to specify target arch. -march=native should work just fine on your CPU

(these builtins should work with clang as well)

[OliverBr]

a late reply, you've probably solved this since.

you should be able to use gcc builtins with mingw:
__builtin_clzll and __builtin_ctzll

they compile to lzcnt/tzcnt but you have to specify target arch. -march=native should work just fine on your CPU

(these builtins should work with clang as well)

Thank you. I haven't found it out, because I stashed it. Your tip works well.
Unfortunately the mingw executable is 5% slower than the VisualC executable. This hasn't change since many years ago.