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

Discussion in 'C Programming' started by Lax, Apr 9, 2008.

  1. Lax

    Lax Guest

    Why is the "x&(x-1)" trick for removing the least significant set bit
    from an integer only valid on 2's complement systems?
    Lax, Apr 9, 2008
    #1
    1. Advertising

  2. In article <>,
    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?


    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
    Walter Roberson, Apr 9, 2008
    #2
    1. Advertising

  3. 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
    Falcon Kirtaran, Apr 9, 2008
    #3
  4. Lax

    Lax Guest

    On Apr 9, 5:09 pm, 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?


    Thank you all (for suggesting and showing counterexamples).

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

    (signed)( x & ( (unsigned)x-1 ) )
    Lax, Apr 9, 2008
    #4
  5. Lax 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?

    >
    > 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
    Peter Nilsson, Apr 10, 2008
    #5
  6. 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
    Falcon Kirtaran, Apr 10, 2008
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Mantorok Redgormor

    sign magnitude, ones complement, two's complement

    Mantorok Redgormor, Oct 5, 2003, in forum: C Programming
    Replies:
    8
    Views:
    8,573
    Glen Herrmannsfeldt
    Oct 8, 2003
  2. Mr. SweatyFinger
    Replies:
    2
    Views:
    1,762
    Smokey Grindel
    Dec 2, 2006
  3. sarathy

    1's complement and 2's complement

    sarathy, Aug 1, 2006, in forum: C Programming
    Replies:
    20
    Views:
    2,172
    Bo Persson
    Aug 2, 2006
  4. sarathy
    Replies:
    22
    Views:
    2,319
    Bo Persson
    Aug 2, 2006
  5. Roberto Waltman

    2's complement vs. 1's complement vs. ...

    Roberto Waltman, Jun 9, 2011, in forum: C Programming
    Replies:
    4
    Views:
    1,340
    Michael Press
    Jun 14, 2011
Loading...

Share This Page