Author: Heiner Marxen
Date: 02:50:57 03/31/03
Go up one level in this thread
On March 28, 2003 at 06:32:37, Tony Werten wrote:
>On March 27, 2003 at 11:50:10, Russell Reagan wrote:
>
>>On March 27, 2003 at 05:35:10, Uri Blass wrote:
>>
>>>If I want to get rid of the least significant 1 of a BitBoard
>>>I do for a bitboard a
>>>a&=a-1
>>>
>>>What is the fastest way to get rid of the most significant 1 of
>>>a bitboard?
>>>
>>>Is it slower than a&=a-1 and how much slower?
>>>(it cannot be faster otherwise popcount of crafty could use it).
>>
>>There is no way to reset the most significant bit of a value using bitwise
>>operations. This has been proven. The following text is from the book "Hacker's
>>Delight" by Henry S. Warren Jr.
>
>Wich obviously is wrong.
>
>BB = BITBOARD
>
>BB|=((BB & even int32) shr 32) | ((BB & odd int32) shl 32)
>BB|=((BB & even int16) shr 16) | ((BB & odd int16) shl 16)
>BB|=((BB & even byte) shr 8) | ((BB & odd byte) shl 8)
>BB|=((BB & even nibble) shr 4) | ((BB & odd nibble) shl 4)
>BB|=((BB & even 2bit) shr 2) | ((BB & odd 2bit) shl 2)
>BB|=((BB & even bit) shr 1) | ((BB & odd bit) shl 1)
>
>BITBOARD=BITBOARD XOR (1 shl(63-lsb(BB)))
>
>
>( I'm not claiming it's efficient )
>
>Tony
>
>
>>
>>"There is a simple test to determine whether or not a given function can be
>>implemented with a squence of add's, subtract's, and's, or's, and not's. We may,
>>of course expand the list with other instructions that can be composed from the
>>basic list, such as shift left by a fixed amount (which is equivalent to a
>>sequence of add's), or multiply. However, we can exclude instructions that
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
>>cannot be composed from this list. The test is contained in the following
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
>>theorem.
By that, "shr" is excluded.
This theorem requires very careful reading :-)
Cheers,
Heiner
>>THEOREM. A function mapping words to words can be implemented with word-parallel
>>add, subtract, and or, and not instructions if and only if each bit of the
>>result depends only on bits at and to the right of each input operand.
>>
>>That is, imagine trying to compute the rightmost bit of the result by looking
>>only at the rightmost bit of each input operand. Then try to compute the next
>>bit to the left by looking only at the rightmost two bits of each input operand,
>>and so forth. If you are successful in this, then the function can be computed
>>with a sequence of add's, and's and so on. If the function cannot be computed in
>>this right-to-left manner, then it cannot be implemented with a sequence of such
>>instructions."
>>
>>Since finding the most significant bit is dependent upon bits to the left of it,
>>it is not possible to implement it using the operations described. So it will
>>probably require some kind of looping or more complex instructions, which means
>>it will be slower than (b & b - 1).
>>
>>The simplest method I can think of to find the most significant bit is to
>>compute a 16-bit lookup table of values and test each 16-bit portion of the
>>64-bit value at a time, or use a table of 8-bit values if that would be faster
>>due to cache friendliness. I'll see if I can write an example later tonight if
>>you'd like.
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.