Velocity Reviews > bitwise absolute value

# bitwise absolute value

Christopher Benson-Manica
Guest
Posts: n/a

 09-07-2003
I'm trying to compute the absolute value of an integer using only bitwise
operators...

int x;
sscanf( "%d", &x );
printf( "%d\n", (x^((~((x>>31)&1))+1)) + ((x>>31)&1) );

That works, but it assumes 32 bit integers. Is there a portable/standard way
to do this? Or are ANSI integers always 32 bits? If not, is using
sizeof(int) * 8 - 1 as the shift value an acceptable alternative?

--
Christopher Benson-Manica | Jumonji giri, for honour.
ataru(at)cyberspace.org |

Malcolm
Guest
Posts: n/a

 09-07-2003

"Christopher Benson-Manica" <(E-Mail Removed)> wrote in message
>
> are ANSI integers always 32 bits? If not, is using
> sizeof(int) * 8 - 1 as the shift value an acceptable alternative?
>

Integers can be 16, 32 or very rarely another number of bits. chars are
usually 8 bits but 9 or 32 has occasionally been reported.

using ( sizeof(int) * CHAR_BIT ) will be reasonably portable, but vulnerable
to padding bits. INT_MAX will give you the maximum value of an integer.
There is also no guarantee that your system uses two's complement
representation of negative numbers.

So it is quite easy to make your construct portable to any architecture you
are likely to encounter in practise, but very difficult to do so in a
perfectly compliant manner. Since your problem looks like a brainteaser
rather than a real programming construct, it is probably worth pinting out
the pitfalls to whoever set it.

Josh Sebastian
Guest
Posts: n/a

 09-07-2003
On Sun, 07 Sep 2003 20:06:20 +0000, Christopher Benson-Manica wrote:

> I'm trying to compute the absolute value of an integer using only bitwise
> operators...
>
> int x;
> sscanf( "%d", &x );
> printf( "%d\n", (x^((~((x>>31)&1))+1)) + ((x>>31)&1) );
>
> That works, but it assumes 32 bit integers.

That can be easily fixed. The more insidious assumption is that it assumes
twos-complement representation of integers.

Josh

Carsten Hansen
Guest
Posts: n/a

 09-07-2003

"Christopher Benson-Manica" <(E-Mail Removed)> wrote in message
news:bjg33s\$b10\$(E-Mail Removed)...
> I'm trying to compute the absolute value of an integer using only bitwise
> operators...
>
> int x;
> sscanf( "%d", &x );
> printf( "%d\n", (x^((~((x>>31)&1))+1)) + ((x>>31)&1) );
>
> That works, but it assumes 32 bit integers. Is there a portable/standard

way
> to do this? Or are ANSI integers always 32 bits? If not, is using
> sizeof(int) * 8 - 1 as the shift value an acceptable alternative?
>
> --
> Christopher Benson-Manica | Jumonji giri, for honour.
> ataru(at)cyberspace.org

Why not just (x ^ (x>>31)) - (x>>31)?
Good compilers will actually generate this code. It avoids a branch which is
important on today's processors.
Be aware that Sun has a patent on this method.

Carsten Hansen

Christopher Benson-Manica
Guest
Posts: n/a

 09-07-2003
Carsten Hansen <(E-Mail Removed)> spoke thus:

>> (x^((~((x>>31)&1))+1)) + ((x>>31)&1)

> Why not just (x ^ (x>>31)) - (x>>31)?
> Good compilers will actually generate this code. It avoids a branch which is
> important on today's processors.
> Be aware that Sun has a patent on this method.

Whoops... What's the rationale behind that though? I'm trying to wrap my
brain around the logic... And how does it avoid a branch?

--
Christopher Benson-Manica | Jumonji giri, for honour.
ataru(at)cyberspace.org |

Carsten Hansen
Guest
Posts: n/a

 09-08-2003

"Christopher Benson-Manica" <(E-Mail Removed)> wrote in message
news:bjgg1f\$c0o\$(E-Mail Removed)...
> Carsten Hansen <(E-Mail Removed)> spoke thus:
>
> >> (x^((~((x>>31)&1))+1)) + ((x>>31)&1)

>
> > Why not just (x ^ (x>>31)) - (x>>31)?
> > Good compilers will actually generate this code. It avoids a branch

which is
> > important on today's processors.
> > Be aware that Sun has a patent on this method.

>
> Whoops... What's the rationale behind that though? I'm trying to wrap my
> brain around the logic... And how does it avoid a branch?
>
> --
> Christopher Benson-Manica | Jumonji giri, for honour.
> ataru(at)cyberspace.org |

Traditionally you take the absolute value by doing something like

if (x < 0)
y = -x;
else
y = x;

Or maybe

y = (x < 0) ? -x : x;

But this involves a comparison and a branch. If the sign of x is random, the
branch prediction is of no value. Hence the processor will stall in 50% of
In compression code this is common case. You remove all redundancy, and the
rest is white noise that you have to encode.
Today it is in general better to do a few extra instructions if that will
avoid a branch. "Keep the processor busy".
Intel's compiler will do this optimization.

Carsten Hansen

Peter Nilsson
Guest
Posts: n/a

 09-08-2003
Christopher Benson-Manica <(E-Mail Removed)> wrote in message news:<bjg33s\$b10\$(E-Mail Removed)>...
> I'm trying to compute the absolute value of an integer using only bitwise
> operators...

Why?

> int x;
> sscanf( "%d", &x );
> printf( "%d\n", (x^((~((x>>31)&1))+1)) + ((x>>31)&1) );
>
> That works, but it assumes 32 bit integers.

And two's complement representation, and sign bit propogating right
shifts, and possibly an absence of trap representations.

In a clc sense, it doesn't work at all.

> Is there a portable/standard way to do this?

(x < 0 ? -x : x)

Note that it does assume that INT_MIN is negatable, which isn't the
case in 2c.

> Or are ANSI integers always 32 bits?

Definitely not. An int must have at least 16 (value+sign) bits, a long
must have at least 32.

> If not, is using sizeof(int) * 8 - 1 as the shift value an acceptable
> alternative?

No, since CHAR_BIT need not be 8 and the integer can be padded.

--
Peter

Christopher Benson-Manica
Guest
Posts: n/a

 09-08-2003
Peter Nilsson <(E-Mail Removed)> spoke thus:

> Why?

It was an assignment for the intro-to-C class at school and I was trying to
help a friend... and it was a macho thing to prove I could do it

> In a clc sense, it doesn't work at all.

By "works," of course, I meant "produces correct results on my implementation."

> (x < 0 ? -x : x)

Certainly would have been my first choice, but all conditional operators were
explicitly forbidden by the assignment. The 32-bit integer assumption was
explicitly permitted, and two's complement represenation was implied. Since
the code was only required to work on a specific implementation (an i386 Linux
box, I believe), these assumptions were acceptable in the context of the
assignment.

Is this question impossible to answer in a strictly ANSI-compliant way, then?

--
Christopher Benson-Manica | Jumonji giri, for honour.
ataru(at)cyberspace.org |

Christopher Benson-Manica
Guest
Posts: n/a

 09-08-2003
Carsten Hansen <(E-Mail Removed)> spoke thus:

>> Whoops... What's the rationale behind that though? I'm trying to wrap my
>> brain around the logic... And how does it avoid a branch?

I probably should have been clear earlier - this was an assignment a friend of
mine had, and conditional operations were explictly forbidden.

--
Christopher Benson-Manica | Jumonji giri, for honour.
ataru(at)cyberspace.org |

Arthur J. O'Dwyer
Guest
Posts: n/a

 09-08-2003

On Mon, 8 Sep 2003, Christopher Benson-Manica wrote:
>
> Peter Nilsson <(E-Mail Removed)> spoke thus:
>
> > Why?

>
> It was an assignment for the intro-to-C class at school and I was trying to
> help a friend... and it was a macho thing to prove I could do it

(BTW, I'm in a course this year whose first lab consists entirely of
about a dozen of these "brain-teasers," assuming the same things that
the OP's code assumed (sign-propagation, two's-complement, 32-bit, no
trap on overflow...). But we didn't have to do absolute value for our
lab.)

> > In a clc sense, it doesn't work at all.

>
> By "works," of course, I meant "produces correct results on my
> implementation."

Well, that's not the clc sense of "works."

> > (x < 0 ? -x : x)

>
> Certainly would have been my first choice, but all conditional operators
> were explicitly forbidden by the assignment. The 32-bit integer assumption
> was explicitly permitted, and two's complement representation was
> implied. Since the code was only required to work on a specific
> implementation (an i386 Linux box, I believe), these assumptions were
> acceptable in the context of the assignment.
>
> Is this question impossible to answer in a strictly ANSI-compliant way,
> then?

y = (x < 0)? -x: x;

This *is* the ISO-compliant way to compute absolute value. Bitwise
operators in C operate on bits, not values, so you can't use them to
compute [much of] anything related to value. C makes a distinction
between the *value* of an 'int' and the *representation* thereof.
<OT> I bet your code works [in the clc sense] in Java. </OT>

HTH,
-Arthur