Author: Gerd Isenberg
Date: 10:27:31 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).
>
>Uri
Hi Uri,
In assembler performance doesn't matter much using bsf or bsr to extract the
LS1B or MS1B. Resetting by btr or appropriate masking should be the same.
In C you have to use lookup-tables like Russell mentioned or something like this
one to extract the MS1B from:
http://aggregate.org/MAGIC/
Gerd
Most Significant 1 Bit
Given a binary integer value x, the most significant 1 bit (highest numbered
element of a bit set) can be computed using a SWAR algorithm that recursively
"folds" the upper bits into the lower bits. This process yields a bit vector
with the same most significant 1 as x, but all 1's below it. Bitwise AND of the
original value with the complement of the "folded" value shifted down by one
yields the most significant bit. For a 32-bit value:
unsigned int
msb32(register unsigned int x)
{
x |= (x >> 1);
x |= (x >> 2);
x |= (x >> 4);
x |= (x >> 8);
x |= (x >> 16);
return(x & ~(x >> 1));
}
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.