Author: Gerd Isenberg
Date: 05:03:09 12/05/03
Go up one level in this thread
On December 04, 2003 at 16:27:53, scott farrell wrote: >Gerd (I think) recently gave me a link to a high tech djinni (really deBrujin or >soething) for LSB - which works great .. thanx :). > >It got me thinking, this seems to run very fast for my java chompster: > >(x& (x-1)) ^x > >which works out the lsb, but it is 64 bit, a straight cast to (int) doesnt work >(as the cast just grabs the first/last 32 bits or something). > >Is this why we need all the high tech maths to get the right 32 bits out? > >Maybe someone can help with how to process the above into a 32 bit int. Scott i don't get your question at all, i fear. Is it about isolating the LSB, or about 32-bit? Isolating LSB is about the "miracles" of two's complement. Building the two's complement (*(-1)) is one's complement + one: E.g one byte, lets take 88 or 0x58 or binary: x 0101 1000 ~x 1010 0111 ~x+1 1010 1000 ==> -x Another algorithm for building the two's complement is: copy all bits from lsb in msb direction, until the first "one" is copied after first one is copied, copy remaining higher bits inverted. This makes it obvoius, that "x & -x" leaves the least significant "one"-bit. The other trick is minus one: x 0101 1000 x-1 0101 0111 Obviously only the ls1b changed from 1 to 0 due the substraction and all lower bits changed from 0 to 1. You may xor the results, to get a set of changed bits, or you may and them to get a set with reset ls1b. With some algebra you can deduce both tricks, so it's only about an overflow of a digit addition works from low to high ;-) And it works for all integer sizes. Gerd > >Thanx >Scott
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.