Author: Gerd Isenberg
Date: 08:25:27 12/05/02
Go up one level in this thread
On December 05, 2002 at 08:27:54, Dan Newman wrote: >On December 05, 2002 at 08:10:42, Sune Fischer wrote: > >>On December 05, 2002 at 07:34:37, Matt Taylor wrote: >> >>><snip> >>>>> I went on and did some testing with the b & -b >>>> >>>>Okay, I'm going to ask now. Can someone explain to me the meaning of b& -b? My >>>>compiler generates a warning that changing a sign on an unsigned accomplishes >>>>nothing, so the expression reduces to b & b which is b? >>><snip> >>> >>>You may have to cast if your compiler is too "smart" for you. The b & -b gives a >>>mask such that the only bit set in the mask is the first bit set in b. (e.g. >>>1111b -> mask of 0001b, 1000b -> mask of 1000b, 1010b -> mask of 0010b) >>> >>>-Matt >> >> >>I still don't understand how it works, "unary minus operator applied to unsigned >>type", how is that even defined, what is -b? >> >>But basicly the result is the same as b^(b&(b-1)) ? >> >>-S. > >The b & -b trick relies on having twos-complement representation for >negative numbers. But it only works if b is signed (or perhaps with >a cast to make it so). It can be done on unsigned b with an extra >operation: b & (~b + 1). > >Here's an example of how it works (on 8-bit numbers): > >Let b = 11100100 > >then ~b = 00011011 > >and ~b + 1 = 00011100 (same as -b if b is signed) > >and finally b & (~b + 1) = 00000100 > >which has only the first one-bit of b turned on. > >-Dan. Hi Dan, Most (All?) C-compilers have no problem with unary minus and constants: unsigned int A = -CONST; Because -CONST is a kind synonym for the compiler which means implicitly (2**wordLengthInBits) - CONST ==> 0 - CONST But with variables this implicite assumption is not true, so a signed cast or using binary minus is necessary. unsigned int b; ... unsigned int lsb = b & (0-b); unsigned int lsb = b & -(signed int)b; Building the Two's complement is even possible by One's Complement plus one... A 00001100 ~A 11110011 +1 11110100 ... or by a sequential algoritm approach: copy all bits from LSB to MSB, but after copying the first "one", inverse the remaining bits. A 00001|100 -A 11110|100 This "algoritm" makes it quite obvious, that b & -b leaves the least significant "one" as lonesome result. Cheers, Gerd
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.