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

[Desperado]

heres just another idea. I hope i read carefully enough and
its doing what you want...

(2*k2-k1) & (2*k2-k1)

Michael

Well, if you already have k2,k1 i think that will work.
Some people here suggested to use bitscans (bsf,bsr) to
get k1,k2 but that would only work if k1 is lsb and
k2 is msb. if you have noise "outside" from k1,k2 bitscans
wont work.

So if k1 is lsb und k2 is msb, my proposal can be improved
and would look like (so there would be nothing to clear
outside the range k1 to k2):

2*k2 - 1

Michael

hint: of course the multiplication can be replaced by left shift operation
(k2<<1) - 1

[Desperado]

heres just another idea. I hope i read carefully enough and
its doing what you want...

(2*k2-k1) & (2*k2-k1)

Michael

Well, if you already have k2,k1 i think that will work.
Some people here suggested to use bitscans (bsf,bsr) to
get k1,k2 but that would only work if k1 is lsb and
k2 is msb. if you have noise "outside" from k1,k2 bitscans
wont work.

So if k1 is lsb und k2 is msb, my proposal can be improved
and would look like (so there would be nothing to clear
outside the range k1 to k2):

2*k2 - k1

Michael

hint: of course the multiplication can be replaced by left shift operation
(k2<<1) - k1

just corrected, sorry was in hurry... now its what i want

Michael

[Gerd Isenberg]

No x86 instruction for that.

Due to two's complement and ones' decrement, this would be much simpler to calculate with least significant one bits:

Code: Select all

k1andAbove = x | -x;
x          = x & (x-1); // BLSR
k2andBelow = x ^ (x-1); // BLSMSK
result = k2andbelow & k1andabove;

BMI1 has some instructions to support this further. I guess for most significant one bits leading and trailing reversal is too expensive so far
(AMD Bulldozer has XOP VPPERM for bitboard reversal).

Otherwise, leadingZeroCount aka BitScan reverse (bsr) and the usual stuff.

What is the purpose of this calculation?

[nkg114mc]

Hi Gerg,

Thanks for the reply!

Actually, I want to find a way to generate the "controlled squares" bitboard of queen, rook, or bishop. It is easy to do this on the rank and file squares, but for diagonal squares, I did not have any good ideas except the rotated board. But if I have such an efficient function as description in this post, this task would become very easy.

For example, b1 = block_bb & diagonal_mask, where b1 contains all pieces on this diagonal line (the line specified by diagonal_mask ). Then using the function I need in this post, input sq and b1, we can get b2, and (b2 & diagonal_mask) is the bitboard of all controlled squares on this diagonal line.

I did not have much knowledge on bitboard operating. Does some one has some other better idea to this task ("controlled squares" bitboard of q, r, or b) above?

Thanks a lot!

[nkg114mc]

Hi Martin:

Thanks for the reply.

R is what I need. But k1 and k2 are not given. The only input of this function is N and k. k1 and k2 are acutally the critical thing that should be calculated by this function. We can also ask the function to return k1 and k2, and use your formula to get the bitboard immediately.

BTW: what does "endsquares" means?

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

[Gerd Isenberg]

Michael's Obstruction Difference is a similar approach, I guess. Otherwise there are a bunch of other techniques in cpw, Hyperbola Quintessence is another calculation technique. State of the art are Magic Bitboards.

Gerd

[nkg114mc]

Hi Lucas,

Thanks for the advice!

I have understood your idea, and I think it is easy to implement.

If x == 0, the function should return all bits (0xffffffffffffffffffffffffffffffff). If left side of k bit is null, then fill all bits on the left of k with 1. The same to the right side of k bit.

Stockfish is really a great work, although it may be a little difficult for a beginner, like me, to analyze

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[k] has bits 0..k-1 set, others null
 * right[k] 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.

[nkg114mc]

Hi Harald:

Thanks a lot for the sample code!

I did not understand the concept "Most significant bit"clearly. Is that a concept in bitboard domain, or programming domain?

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 )
{
    int sq = msb_nr( 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 (0-63). 
// \return 0-63 and NoSquare for an empty bitboard.
// (== log2)
// (Version with big table)
SquareType msb_nr_big_table( BB bb )
{
    static const byte log2table[256] =
    {
       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
    };
    if ( bb & C(0xffffffff00000000) )
    {
        if ( bb & C(0xffff000000000000) )
        {
            if ( bb & C(0xff00000000000000) )
                return log2table[bb >> 56] + 56;
            return log2table[bb >> 48] + 48;
        }
        else
        {
            if ( bb & C(0x0000ff0000000000) )
                return log2table[bb >> 40] + 40;
            return log2table[bb >> 32] + 32;
        }
    }
    else
    {
        if ( bb & 0xffff0000 )
        {
            if ( bb & 0xff000000 )
                return log2table[bb >> 24] + 24;
            return log2table[bb >> 16] + 16;
        }
        else
        {
            if ( bb & 0x0000ff00 )
                return log2table[bb >> 8] + 8;
            else if ( bb & 0x000000ff )
                return log2table[bb];
            else
                return NoSquare;
        }
    }
}


#ifdef _MSC_VER
// Most significant bit number.
// Get the position of the most significant bit (0-63). 
// \return 0-63 and NoSquare for an empty bitboard.
// (== log2)
// (Version with bsr = bit scan reverse )
SquareType msb_nr_bsr( BB bb )
{
    static const unsigned long zero_value = NoSquare;
    __asm
    {
        mov eax, [DWORD PTR bb + 4]
        bsr eax, eax
        jne Upper
        mov eax, [DWORD PTR bb + 0]
        bsr eax, eax
        cmove eax, [zero_value]
        jmp Done
      Upper:
        add eax, 32
      Done:
    };
}
#endif


// Most significant bit number.
// Get the position of the most significant bit (0-63). 
// \return 0-63 and NoSquare for an empty bitboard.
// (best version)
SquareType msb_nr( BB bb )
{
#ifdef _MSC_VER
    return msb_nr_bsr(bb);
#else
    return msb_nr_big_table(bb);
#endif
}

There are more algorithms for msb numbers or lsb numbers.
See the chessprogramming wiki or the other side of a Google search.

Harald

[nkg114mc]

Hi Dr. Hyatt:

If I understood correctly, your idea the same as Lucas described in his reply, is it?

Thanks a lot for the adivce!

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...

[nkg114mc]

Hi Michael:

I think you may not understand correctly about the BitScan ideas in the above posts. You should clear all bits on one side of k first, and then run the most_left_non-zero_bit or most_right_non-zero_bit.

Your idea about using k1 and k2 is interesting! Thanks for the idea!

heres just another idea. I hope i read carefully enough and
its doing what you want...

(2*k2-k1) & (2*k2-k1)

Michael

Well, if you already have k2,k1 i think that will work.
Some people here suggested to use bitscans (bsf,bsr) to
get k1,k2 but that would only work if k1 is lsb and
k2 is msb. if you have noise "outside" from k1,k2 bitscans
wont work.

So if k1 is lsb und k2 is msb, my proposal can be improved
and would look like (so there would be nothing to clear
outside the range k1 to k2):

2*k2 - 1

Michael

hint: of course the multiplication can be replaced by left shift operation
(k2<<1) - 1