bitwise absolute value

[Christopher Benson-Manica]

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?

 

[Malcolm]

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]

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]

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?

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]

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?

 

[Carsten Hansen]

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?

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
the cases. Very bad.
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]

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.

 

[Christopher Benson-Manica]

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]

(reply snipped)

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

 

[Arthur J. O'Dwyer]

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

Yes, it is September already.
(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.)

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

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

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?

See Peter's answer.

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

 

[Ben Pfaff]

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

+ is not a bitwise operator.

 

[Ben Pfaff]

It doesn't answer your question directly, but here's some code
that you might find interesting:

#include <stdio.h>
#include <limits.h>

/* Return X + 1. */
unsigned
uincr (unsigned x)
{
unsigned y;

for (y = 1; y != 0; y <<= 1)
if ((x ^= y) & y)
break;

return x;
}

/* Return X - 1. */
unsigned
udecr (unsigned x)
{
unsigned y;

for (y = 1; y != 0; y <<= 1)
if (!((x ^= y) & y))
break;

return x;
}

/* Returns value of most significant bit in unsigned type. */
unsigned
msb (void)
{
/* There must be a better way... */
unsigned y;
for (y = 1; y << 1; y <<= 1);
return y;
}

/* Negates X, which is in the machine's native int format. */
unsigned
negate (unsigned x)
{
if ((int) UINT_MAX == -1)
return uincr (~x);
else if ((int) UINT_MAX == 0)
return ~x;
else
return x ^ msb ();
}

/* Converts X, in the machine's native int format, to 2's complement
form. */
unsigned
n2twos (unsigned x)
{
if ((x & msb ()) == 0 || (int) UINT_MAX == -1)
return x;
else if ((int) UINT_MAX == 0)
return uincr (x);
else
return uincr (~(x ^ msb ()));
}

/* Converts X, in 2's complement format, to the machine's native int
format. */
int
twos2n (unsigned x)
{
if ((x & msb ()) == 0 || (int) UINT_MAX == -1)
return x;
else if ((int) UINT_MAX == 0)
return udecr (x);
else
return uincr (~x) ^ msb ();
}

/* Returns the bit pattern in X as an int. */
int
u2i (unsigned x)
{
return *(int *) &x;
}

/* Returns the bit pattern in X as an unsigned. */
unsigned
i2u (int x)
{
return *(unsigned *) &x;
}

/* Returns X + 1. */
int
sincr (int x)
{
return u2i (twos2n (uincr (n2twos (i2u (x)))));
}

/* Returns X - 1. */
int
sdecr (int x)
{
return u2i (twos2n (udecr (n2twos (i2u (x)))));
}

int
main (void)
{
int x;

for (x = -10; x <= +10; x = sincr (x))
printf ("% 3d ", x, negate (x));
putchar ('\n');

for (x = +10; x >= -10; x = sdecr (x))
printf ("% 3d ", x);
putchar ('\n');

return 0;
}

 

[Arthur J. O'Dwyer]

Yes, it is September already.
(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.)

Funny story... right after I wrote that, I headed to recitation for
the systems class (15-213, for anyone who cares). And what should
we be doing in recitation but going over an example trick for the
lab -- namely, the "absolute value" one!

So I got to "show off" by putting the (x ^ x>>31) +1+~ (x>>31)
solution on the chalkboard off the top of my head. ;-)

-Arthur

 

[Paul Hsieh]

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. [...]

It also assumes twos complement arithmetic. I.e., -x = 1+~x is true
for twos complement, but not for example, in ones complement.
Unfortunately, the ANSI C standard does not specify whether or not you
can assume twos complement representations, so this whole idea is not
really useful in C.

Of course, it is highly unlikely you will ever encounter a non-twos
complement machine ever in your life (and ones complement has been
aggressively phased out pretty much everywhere), however the ANSI C
standard does not take this into account.

[...] Is there a portable/standard way to do this?

Syntactically or semantically? I mean, to be truly semantically
portable you have to build up your own twos complement model from
scratch. I suppose that's doable, but its also pure nonsense.

[...] Or are ANSI integers always 32 bits?

Not ANSI C, however Java integers are always 32 bits, and the
operators are always twos complement. So if you really really
need/want to perform this trick and you actually need to be portable,
you probably should switch to Java. ANSI C really doesn't have
anything to offer you.

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

Apparently bytes can be something other than 8 bits. I've seen people
post things like "CHAR_BITS" in this newsgroup, however, I don't know
whether that's part of any standard.

 

[Glen Herrmannsfeldt]

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.

I would think that preprocessor expressions could separate twos complement,
ones complement, and sign magnitude.

#if ~0==-1
printf("twos complement\n");
#elif ~0==-0
printf("ones complement\n");
#else
printf("sign magnitude\n");
#endif

Then the three different bitwise absolute value expressions could be
conditionally generated

How about x&((~0>>1)) for sign magnitude?

-- glen

 

[Glen Herrmannsfeldt]

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.

Are you sure that works? It seems close but not right to me.

Conditional load is designed to avoid branch. Don't most machines have an
absolute value instruction?

-- glen

 

[pete]

Glen Herrmannsfeldt wrote:

#if ~0==-1
printf("twos complement\n");
#elif ~0==-0
printf("ones complement\n");
#else
printf("sign magnitude\n");
#endif

Then the three different bitwise absolute value expressions could be
conditionally generated

How about x&((~0>>1)) for sign magnitude?

(~0) is not a portable expression.
Representations which would equate to (-0), may be traps.

 

[Morris Dovey]

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?

Hmm. If you're going to allow arithmetic operators, then how about:

int my_abs(int x)
{ return x * ((x > 0) - (x < 0))
}

 

[Carsten Hansen]

which

Are you sure that works? It seems close but not right to me.

Either it works or it doesn't. Give an example where it fails.
Be aware that both Microsoft's and Intel's compiler generate the equivalent
code

value in eax
cdq
xor eax,edx
sub eax,edx

Also, the trick is mentioned in IBM's guide for compiler writers for the
PowerPC.

Conditional load is designed to avoid branch. Don't most machines have an
absolute value instruction?

-- glen

They may have an instruction for taking the absolute value of a
floating-point number. But neither the x86 nor the PowerPC have an
instruction for taking the absolute value of a fixed-point number.

Carsten Hansen

 

[pete]

Hmm. If you're going to allow arithmetic operators, then how about:

int my_abs(int x)
{ return x * ((x > 0) - (x < 0))
}

You also inserted relational operators.