Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > x&(x-1) ... why only 2's complement system?

Reply
Thread Tools

x&(x-1) ... why only 2's complement system?

 
 
Lax
Guest
Posts: n/a
 
      04-09-2008

Why is the "x&(x-1)" trick for removing the least significant set bit
from an integer only valid on 2's complement systems?

 
Reply With Quote
 
 
 
 
Walter Roberson
Guest
Posts: n/a
 
      04-09-2008
In article <(E-Mail Removed)>,
Lax <(E-Mail Removed)> wrote:

>Why is the "x&(x-1)" trick for removing the least significant set bit
>from an integer only valid on 2's complement systems?


Orders of Rear Admiral Grace Hopper.


Consider signed-magnitude and the number -2. 1 for the sign, a bunch
of binary 0s, then binary 10 at the end. x-1 is -3, which is
1 for the sign, a bunch of binary 0s, then binary 11 at the end.
Bitwise and the two together and you get 1 for the sign, a bunch of
binary 0s, then binary 10 at the end. Which is the representation of -2
which is the number you started with, so the technique does not work
for signed-magnitude.


With this example in mind, you should easily be able to determine
whether the technique works for 1's complement systems.
--
"After all, what problems has intellectualism ever solved?"
-- Robert Gilman
 
Reply With Quote
 
 
 
 
Falcon Kirtaran
Guest
Posts: n/a
 
      04-09-2008
Lax wrote:
> Why is the "x&(x-1)" trick for removing the least significant set bit
> from an integer only valid on 2's complement systems?
>


Because on a 2's compliment system (let's assume 8-bit for simplicity's
sake) x-1 is the same as x+(0b11111111) or x+0xFF. Let's say, for
example's sake, that x is 0b00101000 or positive 40. In that case,

0b00101000
+ 0b11111111
= 0b00100111 = 39

0b00101000
& 0b00100111
= 0b00100000 which is the correct answer.

However, this obviously relies on -1 being represented as the 2's
compliment of one (invert all bits and add one). If the system uses
some other method, it will be different and the bitmask will not be
equal to x-1. For instance, in a one's compliment system, x-1 is
represented as x+0b11111110.

--
--Falcon Kirtaran
 
Reply With Quote
 
Lax
Guest
Posts: n/a
 
      04-09-2008
On Apr 9, 5:09*pm, Lax <(E-Mail Removed)> wrote:
> Why is the "x&(x-1)" trick for removing the least significant set bit
> from an integer only valid on 2's complement systems?


Thank you all (for suggesting and showing counterexamples).

So is this a good implementation-independent way of doing it?

(signed)( x & ( (unsigned)x-1 ) )

 
Reply With Quote
 
Peter Nilsson
Guest
Posts: n/a
 
      04-10-2008
Lax wrote:
> Lax <(E-Mail Removed)> wrote:
> > Why is the "x&(x-1)" trick for removing the least
> > significant set bit from an integer only valid on 2's
> > complement systems?

>
> Thank you all (for suggesting and showing
> counterexamples).
>
> So is this a good implementation-independent way of doing it?
>
> (signed)( x & ( (unsigned)x-1 ) )


No, the right way is to make x unsigned to begin with, and
to forget about testing bits in negative integers.

--
Peter
 
Reply With Quote
 
Falcon Kirtaran
Guest
Posts: n/a
 
      04-10-2008
Eric Sosman wrote:
> Lax wrote:
>> Why is the "x&(x-1)" trick for removing the least significant set bit
>> from an integer only valid on 2's complement systems?

>
> It is valid on all systems if `x' is non-negative.
> That means, as a particularly useful special case, that
> it is always valid if `x' is unsigned.
>
> For negative values of `x', I suggest you take pencil
> and paper and work through a few examples, using all three
> of the representations C allows: two's complement, ones'
> complement, and signed magnitude. To save some writing,
> pretend your computer uses a narrow int of maybe six or
> eight bits. Try a few different `x' values like -1, -2,
> -10, and see what happens.
>


Hmm. I stand corrected.

--
--Falcon Kirtaran
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
2's complement vs. 1's complement vs. ... Roberto Waltman C Programming 4 06-13-2011 11:26 PM
findcontrol("PlaceHolderPrice") why why why why why why why why why why why Mr. SweatyFinger ASP .Net 2 12-02-2006 03:46 PM
1's complement and 2's complement sarathy C++ 22 08-02-2006 05:53 PM
1's complement and 2's complement sarathy C Programming 20 08-02-2006 05:53 PM
sign magnitude, ones complement, two's complement Mantorok Redgormor C Programming 8 10-07-2003 11:52 PM



Advertisments