Author: Russell Reagan
Date: 08:50:10 03/27/03
Go up one level in this thread
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." 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.