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

[Lax]

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

[Eric Sosman]

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.

--
Er*********@sun.com

[Lax]

On Apr 9, 5:09*pm, Lax <[e-mail]:

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 ) )

[Peter Nilsson]

Lax wrote:

Lax <[e-mail]:

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

[CBFalconer]

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 works fine on unsigned integers also. Just write down the bit
patterns involved.

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.
** Posted from http://www.teranews.com **

[CBFalconer]

Lax wrote:

Lax <[e-mail]:

>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. It is a good way of getting undefined behaviour.

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.

** Posted from http://www.teranews.com **

[Falcon Kirtaran]

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