Author: Ricardo Gibert
Date: 10:31:11 03/27/03
Go up one level in this thread
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. > >"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. > >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." I think the instruction "a = 0;" will reset the msb of "a" to zero ;) > >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.