bitwise absolute value

[Kevin Easton]

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?

Not at all:

x * (2 * (x > 0) - 1)

(Chances are this will result in a branch in the generated machine code
- but that's not what the question asked).

- Kevin.

 

[Glen Herrmannsfeldt]

(snip)

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

Oh, arithmetic shift right. I was considering logical shift right. I would
have to get out my book, but I thought C didn't specify which one you got.

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

Won't that violate the previously mentioned Sun patent? (Maybe only if one
actually uses it?)

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.

The only architecture that I have coded one on, S/370, has it. Alpha, as
far as I can tell, uses a conditional load (between registers) to do it in
two instructions with no branch. I thought VAX did, but I don't see it in
the book, so I guess not.

-- glen

 

[LibraryUser]

... snip ...

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.

From N869:

5.2.4.2.1 Sizes of integer types <limits.h>

[#1] The values given below shall be replaced by constant
expressions suitable for use in #if preprocessing
directives. Moreover, except for CHAR_BIT and MB_LEN_MAX,
the following shall be replaced by expressions that have the
same type as would an expression that is an object of the
corresponding type converted according to the integer
promotions. Their implementation-defined values shall be
equal or greater in magnitude (absolute value) to those
shown, with the same sign.

-- number of bits for smallest object that is not a bit-
field (byte)
CHAR_BIT 8

 

[pete]

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

#if !(1 & -1)
printf("ones complement\n");
#elif -1 & 2
printf("twos complement\n");
#else
printf("sign magnitude\n");
#endif

Is there any wording in the standard which prohibits
negative integer values from being represented by
the sign bit and a gray code representation of the magnitude ?

 

[Glen Herrmannsfeldt]

#if !(1 & -1)
printf("ones complement\n");
#elif -1 & 2
printf("twos complement\n");
#else
printf("sign magnitude\n");
#endif

Is there any wording in the standard which prohibits
negative integer values from being represented by
the sign bit and a gray code representation of the magnitude ?

Positive integers must have the traditional binary representation, but sign
magnitude is allowed for negative integers. I think that any definition of
sign magnitude would disallow a different representation of the magnitude
for positive and negative numbers.

-- glen

 

[Ben Pfaff]

Is there any wording in the standard which prohibits
negative integer values from being represented by
the sign bit and a gray code representation of the magnitude ?

Yes. Positive values have to be the ordinary binary
representation. Here is what C99 says about negative values:

If the sign bit is one, the value shall be
modified in one of the following ways:
- the corresponding value with sign bit 0 is negated (sign
and magnitude);
- the sign bit has the value -(2N) (two's complement);
- the sign bit has the value -(2N - 1) (one's complement).

 

[Ben Pfaff]

Oh, arithmetic shift right. I was considering logical shift right. I would
have to get out my book, but I thought C didn't specify which one you got.

It doesn't:

4 The result of E1 << E2 is E1 left-shifted E2 bit positions;
vacated bits are filled with zeros. If E1 has an unsigned
type, the value of the result is E1 × 2E2, reduced modulo
one more than the maximum value representable in the result
type. If E1 has a signed type and nonnegative value, and E1
× 2E2 is representable in the result type, then that is the
resulting value; otherwise, the behavior is undefined.

5 The result of E1 >> E2 is E1 right-shifted E2 bit positions. If
E1 has an unsigned type or if E1 has a signed type and a
nonnegative value, the value of the result is the integral
part of the quotient of E1 / 2E2. If E1 has a signed type
and a negative value, the resulting value is
implementation-defined.

(Note that some of those values should be superscripted.)

 

[Ben Pfaff]

x * (2 * (x > 0) - 1)

(Chances are this will result in a branch in the generated machine code
- but that's not what the question asked).

It asked for use of only bitwise operators. Not only did you use
non-bitwise operators, you didn't use any bitwise operators at
all.

 

[LibraryUser]

#if !(1 & -1)
printf("ones complement\n");
#elif -1 & 2
printf("twos complement\n");
#else
printf("sign magnitude\n");
#endif

Is there any wording in the standard which prohibits
negative integer values from being represented by
the sign bit and a gray code representation of the magnitude ?

Yes. There is something about binary bit weights somewhere.

 

[Morris Dovey]

You also inserted relational operators.

I did, didn't I?

Good catch. 8^)

 

[pete]

Yes. Positive values have to be the ordinary binary
representation. Here is what C99 says about negative values:

If the sign bit is one, the value shall be
modified in one of the following ways:
- the corresponding value with sign bit 0 is negated (sign
and magnitude);
- the sign bit has the value -(2N) (two's complement);
- the sign bit has the value -(2N - 1) (one's complement).

Thank you.

 

[Kevin Easton]

It asked for use of only bitwise operators. Not only did you use
non-bitwise operators, you didn't use any bitwise operators at
all.

The example given in the original question used addition operators. I
can add a shift operator if you like:

x * (((x > 0) << 1) - 1)

or

x + x * ((x < 0) << 1)

- Kevin.

 

[Dan Pop]

Yes. Positive values have to be the ordinary binary
representation. Here is what C99 says about negative values:

If the sign bit is one, the value shall be
modified in one of the following ways:
- the corresponding value with sign bit 0 is negated (sign
and magnitude);
- the sign bit has the value -(2N) (two's complement);
- the sign bit has the value -(2N - 1) (one's complement).

Nope, this is definitely NOT what C99 says about negative values.
The last two lines are properly rendered in plain text as:

- the sign bit has the value -(2**N) (two's complement);
- the sign bit has the value -(2**N - 1) (one's complement).

Where ** stands for the exponentiation operator. The mechanical
translation from PDF to plain text doesn't work as well as some people
naively believe...

But this text is completely missing from C89, which is the currently
implemented standard, so there is nothing preventing a current
implementation from adopting Pete's model for representing negative
values. In theory, at least ;-)

Dan

 

[Ben Pfaff]

Nope, this is definitely NOT what C99 says about negative values.
The last two lines are properly rendered in plain text as:

- the sign bit has the value -(2**N) (two's complement);
- the sign bit has the value -(2**N - 1) (one's complement).

Of course. That's obvious.

 

[Dan Pop]

Of course. That's obvious.

If you're already familiar with the issue, yes. Otherwise, 2N is supposed
to be read as 2 * N and not as 2 ** N.

Dan