## Looking for an CPU Instruction or a Function Which Can ...

Discussion of chess software programming and technical issues.

Moderators: hgm, Dann Corbit, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
nkg114mc
Posts: 68
Joined: Sat Dec 18, 2010 4:19 pm
Location: Tianjin, China

### Looking for an CPU Instruction or a Function Which Can ...

Hi all,

I come cross a problem on operating the bitboard. I am looking a CPU instruction or a function implemented by asm language or C language. The input of this function is a 64-bit unsigned integer N and a bit number k (0 <= k <= 64). The return value is also a 64-bit unsigned integer R. Suppose the first non-zero bit on left side of bit k is bit k1, and the first non-zero bit on the right side of k is bit k2. Then R is such a 64-bit unsigned integer that all bits from k1 to k2 (including k1 and k2) are 1, but all other bits are 0.

For example:

Code: Select all

``````                    High bit                                                 Low bit

input&#58;  N = 0001000000001000100000000000000000000100000000000100000000010000 &#40;64-bit binary integer&#41;
^     ^              ^
k1    k              k2
k =                       41
output&#58; R = 0000000000000000111111111111111111111100000000000000000000000000 &#40;64-bit binary integer&#41;
``````
Another example:

Code: Select all

``````        input&#58;  N = 0001000000001000100000000000000000000100000000000100000000010000 &#40;64-bit binary integer&#41;
^  ^     ^
k1 k     k2
k =       57
output&#58; R = 0001111111111000000000000000000000000000000000000000000000000000 &#40;64-bit binary integer&#41;
``````
Is there any CPU instruction which can finish such a task, or a good implementation of function which can generate such a 64-bit unsigned integer effciently (do not need to go through each bit one by one from bit k1 to bit k2)?

Thanks a lot!

mar
Posts: 2262
Joined: Fri Nov 26, 2010 1:00 pm
Location: Czech Republic
Full name: Martin Sedlak

### Re: Looking for an CPU Instruction or a Function Which Can .

Hi,

What do you want then? R? Then you can try this:
((1 << (k1+1))-1) ^ ((1<<(k2+1))-1)

(I hope it's not total BS however)

You can also use a lookup table for that.

If you want a bb mask for squares between two endsquares then you probably want something else than what you described.

Martin

Harald
Posts: 288
Joined: Thu Mar 09, 2006 12:07 am

### Re: Looking for an CPU Instruction or a Function Which Can .

Hi

If you already know k1 and k2 you could use Martin's formula (slightly changed):
((1 << (k1+1))-1) ^ ((1<<(k2))-1)

If your bits k1, k and k2 are on one rank of a chess board and you know the
rank (0..7) then you can shift it down first, (N >> rank) and look up the
result in a table indexed by the lowest 8 bit of the shifted N.
That would to a degree also work with more bits for the range. But the
lookup index must be very big when you don't know where k is inside that
range. The index would have twice the number of bits than the maxium range.

If you don't know the position of k1 and k2 you could use something like this:

Code: Select all

``````while ( copyOfN )
&#123;
int sq = msb_nr&#40; copyOfN ); // most significant bit
...
copyOfN &= ~&#40;1 << sq&#41;;
&#125;
``````
You can find k2 as the biggest sq below k and k1 as the smalles sq over k.

with:

Code: Select all

``````// Most significant bit number.
// Get the position of the most significant bit &#40;0-63&#41;.
// \return 0-63 and NoSquare for an empty bitboard.
// (== log2&#41;
// &#40;Version with big table&#41;
SquareType msb_nr_big_table&#40; BB bb )
&#123;
static const byte log2table&#91;256&#93; =
&#123;
64, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,
4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7
&#125;;
if ( bb & C&#40;0xffffffff00000000&#41; )
&#123;
if ( bb & C&#40;0xffff000000000000&#41; )
&#123;
if ( bb & C&#40;0xff00000000000000&#41; )
return log2table&#91;bb >> 56&#93; + 56;
return log2table&#91;bb >> 48&#93; + 48;
&#125;
else
&#123;
if ( bb & C&#40;0x0000ff0000000000&#41; )
return log2table&#91;bb >> 40&#93; + 40;
return log2table&#91;bb >> 32&#93; + 32;
&#125;
&#125;
else
&#123;
if ( bb & 0xffff0000 )
&#123;
if ( bb & 0xff000000 )
return log2table&#91;bb >> 24&#93; + 24;
return log2table&#91;bb >> 16&#93; + 16;
&#125;
else
&#123;
if ( bb & 0x0000ff00 )
return log2table&#91;bb >> 8&#93; + 8;
else if ( bb & 0x000000ff )
return log2table&#91;bb&#93;;
else
return NoSquare;
&#125;
&#125;
&#125;

#ifdef _MSC_VER
// Most significant bit number.
// Get the position of the most significant bit &#40;0-63&#41;.
// \return 0-63 and NoSquare for an empty bitboard.
// (== log2&#41;
// &#40;Version with bsr = bit scan reverse )
SquareType msb_nr_bsr&#40; BB bb )
&#123;
static const unsigned long zero_value = NoSquare;
__asm
&#123;
mov eax, &#91;DWORD PTR bb + 4&#93;
bsr eax, eax
jne Upper
mov eax, &#91;DWORD PTR bb + 0&#93;
bsr eax, eax
cmove eax, &#91;zero_value&#93;
jmp Done
Upper&#58;
Done&#58;
&#125;;
&#125;
#endif

// Most significant bit number.
// Get the position of the most significant bit &#40;0-63&#41;.
// \return 0-63 and NoSquare for an empty bitboard.
// &#40;best version&#41;
SquareType msb_nr&#40; BB bb )
&#123;
#ifdef _MSC_VER
return msb_nr_bsr&#40;bb&#41;;
#else
return msb_nr_big_table&#40;bb&#41;;
#endif
&#125;
``````
There are more algorithms for msb numbers or lsb numbers.
See the chessprogramming wiki or the other side of a Google search.

Harald

lucasart
Posts: 3184
Joined: Mon May 31, 2010 11:29 am
Full name: lucasart
Contact:

### Re: Looking for an CPU Instruction or a Function Which Can .

I haven't coded n assembly since the days of the 80386, so I'm really not an expert in modern assembly. But the operation you describe seems far too specific for someone to have designed an operation in assembly for it. Besides, you need to think about portability.

Here's how I would do it, in C:

Code: Select all

``````/*
* left&#91;k&#93; has bits 0..k-1 set, others null
* right&#91;k&#93; has bits k+1..63 set, others null
* obviously if k-1<0 or k+1>63, then these are null bitboards
* I let you write the code to precompute these
*/
uint64_t left&#91;64&#93;, right&#91;64&#93;;

/*
* bit_segment&#91;k1&#93;&#91;k2&#93; has bits k1..k2 set others null
* you can assume k1 < k2, and zero fill the rest
*/
uint64_t bit_segment&#91;64&#93;&#91;64&#93;;

uint64_t your_function&#40;uint64_t x, unsigned k&#41;
&#123;
unsigned k1 = msb&#40;x & left&#91;k&#93;);
unsigned k2 = lsb&#40;x & right&#91;k&#93;);
/* you need to decide what you do if x & left&#91;k&#93; == 0, or x & right&#91;k&#93; == 0, not described in your spec. what if x = 0 for example ? */
return bit_segment&#91;k1&#93;&#91;k2&#93;;
&#125;
``````
For lsb and msb, you can have a look at Stockfish. It has all the state of the art stuff.
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.

lucasart
Posts: 3184
Joined: Mon May 31, 2010 11:29 am
Full name: lucasart
Contact:

### Re: Looking for an CPU Instruction or a Function Which Can .

mar wrote:Hi,

What do you want then? R? Then you can try this:
((1 << (k1+1))-1) ^ ((1<<(k2+1))-1)

(I hope it's not total BS however)

You can also use a lookup table for that.

If you want a bb mask for squares between two endsquares then you probably want something else than what you described.

Martin
I think you missed the point. The only difficult part is to compute k1 and k2.
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.

bob
Posts: 20922
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

### Re: Looking for an CPU Instruction or a Function Which Can .

nkg114mc wrote:Hi all,

I come cross a problem on operating the bitboard. I am looking a CPU instruction or a function implemented by asm language or C language. The input of this function is a 64-bit unsigned integer N and a bit number k (0 <= k <= 64). The return value is also a 64-bit unsigned integer R. Suppose the first non-zero bit on left side of bit k is bit k1, and the first non-zero bit on the right side of k is bit k2. Then R is such a 64-bit unsigned integer that all bits from k1 to k2 (including k1 and k2) are 1, but all other bits are 0.

For example:

Code: Select all

``````                    High bit                                                 Low bit

input&#58;  N = 0001000000001000100000000000000000000100000000000100000000010000 &#40;64-bit binary integer&#41;
^     ^              ^
k1    k              k2
k =                       41
output&#58; R = 0000000000000000111111111111111111111100000000000000000000000000 &#40;64-bit binary integer&#41;
``````
Another example:

Code: Select all

``````        input&#58;  N = 0001000000001000100000000000000000000100000000000100000000010000 &#40;64-bit binary integer&#41;
^  ^     ^
k1 k     k2
k =       57
output&#58; R = 0001111111111000000000000000000000000000000000000000000000000000 &#40;64-bit binary integer&#41;
``````
Is there any CPU instruction which can finish such a task, or a good implementation of function which can generate such a 64-bit unsigned integer effciently (do not need to go through each bit one by one from bit k1 to bit k2)?

Thanks a lot!
On the Cray, you can do this. On X86, no. Will take a few programming tricks...

One simple approach is to locate the two 1 bits in question, say k1 and k2.

Create an array that has one bits set from each bit in the word all the way through the end. set[0] has ones everywhere, set[1] has bits from bit 1 thru 63 set, etc.

create another array that has 1 bits everywhere, except on the "other side" of a bit. For example, unset[8] would have 1 bits on bits 0-8, and 0 bits on 9-63.

given the two bits you have, k1 and k2, you use

Used to do this kind of thing in bitboards before moving on to rotated and then magics.

mar
Posts: 2262
Joined: Fri Nov 26, 2010 1:00 pm
Location: Czech Republic
Full name: Martin Sedlak

### Re: Looking for an CPU Instruction or a Function Which Can .

lucasart wrote:I think you missed the point. The only difficult part is to compute k1 and k2.
C'est parce que j'approuve Windaube et je n'y connaisse rien

JuLieN
Posts: 2948
Joined: Mon May 05, 2008 10:16 am
Location: Nantes (France)
Contact:

### Re: Looking for an CPU Instruction or a Function Which Can .

mar wrote:
lucasart wrote:I think you missed the point. The only difficult part is to compute k1 and k2.
C'est parce que j'approuve Windaube et je n'y connaisse rien
"The only good bug is a dead bug." (Don Dailey)
[Blog: http://tinyurl.com/predateur ] [Facebook: http://tinyurl.com/fbpredateur ] [MacEngines: http://tinyurl.com/macengines ]

bob
Posts: 20922
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

### Re: Looking for an CPU Instruction or a Function Which Can .

lucasart wrote:
mar wrote:Hi,

What do you want then? R? Then you can try this:
((1 << (k1+1))-1) ^ ((1<<(k2+1))-1)

(I hope it's not total BS however)

You can also use a lookup table for that.

If you want a bb mask for squares between two endsquares then you probably want something else than what you described.

Martin
I think you missed the point. The only difficult part is to compute k1 and k2.
I don't think that part is hard. To find the first 1 to the right of bit k, you simply clear all bits to the left of K and bit K itself, then use a BSR. To find the first 1 to the left, clear all bits to the right of K and K itself, and use a BSF.

clearing the bits is an AND with a simple table lookup into 64 values...