Working with negative numbers

[Frederick Gotham]

I have a general idea about how negative number systems work, but I'd
appreciate some clarification if anyone would be willing to help me.

Let's assume we're working with an 8-Bit signed integer, and that it
contains no padding.

Firstly, I realise that the MSB is known as the sign-bit, and that it
indicates whether the number is positive or negative (irrespective of
which negative number system is used).

The next seven bits tell us the value. If the number is positive, then
the seven bits represent the number in the same domestic way in which an
unsigned integer would represent the number.

But if the number is negative, then there's separate methods to correlate
the negative bit-pattern with its corresponding positive value:

(1) Sign-magnitude: The bit-pattern is exactly the same.
(2) One's complement: Toggle each bit.
(3) Two's complement: Toggle each bit, then add 1.


It seems we get the following ranges for each format: (Are they right?)

(1) Sign-magnitude: -127 through +127
(2) One's complement: -128 through +127
(3) Two's complement: -128 through +127


It would seem that each number system has the following advantages:

(1) Sign-magnitude:

Efficient conversion from negative to positive.

(2) One's complement:

There's only one bit-pattern for zero.
One extra unit in the negative range.

(3) Two's complement:

There's only one bit-pattern for zero.
One extra unit in the negative range.
Addition with negative numbers can be performed exactly as if
they were positive.


Are there any other advantage/disadvantages to be aware of?

The next thing I want to discuss is the whole idea of having more than
one bit-pattern for a specific value... zero in particular!.

If we have a machine that uses sign-magnitude, and we have two separate
variables that hold the value zero, is it possible for them to have
different bit patterns? i.e.:

var1 == 0000 0000
var2 == 1000 0000


How does the machine handle comparison of these two variables? Would it
interpret:

if ( var1 == var2 )

as:

if ( !(var1 & 127 || var2 & 127) )



I'd ask more question as people reply...

 

[pete]

Frederick Gotham wrote:

It seems we get the following ranges for each format:
(Are they right?)

(1) Sign-magnitude: -127 through +127
(2) One's complement: -128 through +127
(3) Two's complement: -128 through +127

Yes, except that implementations
are allowed to have SCHAR_MIN equal to -127,
regardless of representation.

The next thing I want to discuss is the whole idea of having more than
one bit-pattern for a specific value... zero in particular!.

If we have a machine that uses sign-magnitude,
and we have two separate
variables that hold the value zero, is it possible for them to have
different bit patterns? i.e.:

var1 == 0000 0000
var2 == 1000 0000

How does the machine handle comparison of these two variables?

A machine has two choices,
an integer object with the representation for negative zero,
either compares equal to zero
or has a trap representation.

 

[Frederick Gotham]

pete posted:

A machine has two choices,
an integer object with the representation for negative zero,
either compares equal to zero
or has a trap representation.

Nicely put.

Does that mean that you MUST have padding within a signed integer in order
for "negative zero" to be a trap representation? The reason I ask is as
follows: I recall reading something recently along the lines of "The value
representation bits of an integer type shall not be involved in trapping".
This makes me think that, if you're going to have a trap representation,
then you must have at least one padding bit.

 

[Michael Mair]

I have a general idea about how negative number systems work, but I'd
appreciate some clarification if anyone would be willing to help me.

Let's assume we're working with an 8-Bit signed integer, and that it
contains no padding.

Firstly, I realise that the MSB is known as the sign-bit, and that it
indicates whether the number is positive or negative (irrespective of
which negative number system is used).

The next seven bits tell us the value. If the number is positive, then
the seven bits represent the number in the same domestic way in which an
domestic?

unsigned integer would represent the number.

But if the number is negative, then there's separate methods to correlate
the negative bit-pattern with its corresponding positive value:

(1) Sign-magnitude: The bit-pattern is exactly the same.
(2) One's complement: Toggle each bit.
(3) Two's complement: Toggle each bit, then add 1.

Note that the last rule does not cover
10000000
whereas the rule "pretend that unsigned representations of values
in the range 1<<7 to (1<<8)-1 are treated as 'unsigned value -
(1<<8)'" does.

Note that C90 does not prescribe one of these three, so you could
come up with "sign magnitude - 1" or "sign plus inverted order
value bits" or ...
C99 restricts your choice to 1s complement, 2s complement, and
sign-magnitude.

It seems we get the following ranges for each format: (Are they right?)

(1) Sign-magnitude: -127 through +127
(2) One's complement: -128 through +127

Wrong. Reread your rule above. Ones complement covers
-127 to 127

(3) Two's complement: -128 through +127


It would seem that each number system has the following advantages:

(1) Sign-magnitude:

Efficient conversion from negative to positive.

Easy multiplication/division of negative and positive numbers.
Symmetric range.

(2) One's complement:

There's only one bit-pattern for zero.

Wrong. 11111111 fits your definition.

One extra unit in the negative range.

Wrong.
Advantages: ~ means the same as unary minus.
Symmetric range.

(3) Two's complement:

There's only one bit-pattern for zero.
One extra unit in the negative range.
Addition with negative numbers can be performed exactly as if
they were positive.

Often "compute through overflow" possible to extend range.

Disadvantages:
- >> for arithmetic shift means "round down
division" instead of real division.
- asymmetric range: You pay simply too much for the "one extra
unit". Having to write -32767-1 in order to make sure that you
arrive at the right value with the right type simply is a
little bit too much. This can incur many ugly checks and can be
for many things as annoying as "value preserving instead of
unsigned preserving".[*]

Are there any other advantage/disadvantages to be aware of?

Sure -- depending on your application. See above for a few of
them.

The next thing I want to discuss is the whole idea of having more than
one bit-pattern for a specific value... zero in particular!.

If we have a machine that uses sign-magnitude, and we have two separate
variables that hold the value zero, is it possible for them to have
different bit patterns? i.e.:

var1 == 0000 0000
var2 == 1000 0000

Yes. The implementation can treat 10000000 (or, for 1sC, 11111111)
as "trap representation" or "negative zero".
The C99 standard specifically deals with "negative zero" (I am too
lazy to look it up, have a look at N1124.pdf; I am also too lazy
to find out what you can find in C90).

How does the machine handle comparison of these two variables? Would it
interpret:

if ( var1 == var2 )

as:

if ( !(var1 & 127 || var2 & 127) )

This is the implementation's problem, not yours, so you are going
toward off-topic.


Cheers
Michael

 

[Eric Sosman]

Frederick Gotham wrote On 06/27/06 17:42,:

I have a general idea about how negative number systems work, but I'd
appreciate some clarification if anyone would be willing to help me.

Let's assume we're working with an 8-Bit signed integer, and that it
contains no padding.

Firstly, I realise that the MSB is known as the sign-bit, and that it
indicates whether the number is positive or negative (irrespective of
which negative number system is used).

You're on shaky ground when you designate the sign bit
as the "most significant." It'd be clearer just to say that
the eight-bit number has one sign bit and seven value bits.

The next seven bits tell us the value. If the number is positive, then
the seven bits represent the number in the same domestic way in which an
unsigned integer would represent the number.

Again, "next" is an iffy proposition best left alone.
(And there's that peculiar use of "domestic" again; it's
not a usage I've ever encountered except in your writing.)

But if the number is negative, then there's separate methods to correlate
the negative bit-pattern with its corresponding positive value:

(1) Sign-magnitude: The bit-pattern is exactly the same.
(2) One's complement: Toggle each bit.
(3) Two's complement: Toggle each bit, then add 1.

Instead of thinking about shuffling the bits, think about
the seven value bits encoding a non-negative value V and the sign
bit specifying a transformation of that value. If the sign bit
is zero there is no transformation and the value of the eight-bit
integer is V. If the sign bit is one

(1) Signed magnitude: The value is -V
(2) Ones' complement: The value is V-127
(3) Two's complement: The value is V-128

It seems we get the following ranges for each format: (Are they right?)

(1) Sign-magnitude: -127 through +127
(2) One's complement: -128 through +127
(3) Two's complement: -128 through +127

(1) and (3) are right, but the range for (2) is -127
through 127. The bit patterns all-zero and all-one both
represent zero (all-one is informally called "minus zero").

In theory, the ranges supported by C can be "smaller"
than these. The "minus zero" patterns for (1) and (2) and
the -128 pattern for (3) could be trap representations rather
than actual attainable values. I'm not personally familiar
with any C implementations that do such a thing, but that
doesn't prove there aren't any.

It would seem that each number system has the following advantages:

(1) Sign-magnitude:

Efficient conversion from negative to positive.

This won't be a consideration for small integers.
The circuitry to negate a value that can fit in a machine's
accumulator will do the job quite quickly; getting the value
to and from the accumulator will probably dominate.

(2) One's complement:

There's only one bit-pattern for zero.
One extra unit in the negative range.

There are two bit patterns for zero, and no extra unit.
Ones' complement has a (possibly insignificant) disadvantage
in that some operations require an "end-around carry" where
a carry out of the most significant bit must be added back
in at the least significant position. Since that position
can also be an input to determining the carry, a little more
delay may be required -- but if the whole thing completes in
less than a clock cycle, it doesn't matter how much or how
little "spare time" remains.

(3) Two's complement:

There's only one bit-pattern for zero.
One extra unit in the negative range.
Addition with negative numbers can be performed exactly as if
they were positive.

That last seems to be the big attraction, big enough to
outweigh the inconvenience of the asymmetrical range.

Are there any other advantage/disadvantages to be aware of?

The next thing I want to discuss is the whole idea of having more than
one bit-pattern for a specific value... zero in particular!.

If we have a machine that uses sign-magnitude, and we have two separate
variables that hold the value zero, is it possible for them to have
different bit patterns? i.e.:

var1 == 0000 0000
var2 == 1000 0000

Yes, these would both represent the value zero.

How does the machine handle comparison of these two variables? Would it
interpret:

if ( var1 == var2 )

as:

if ( !(var1 & 127 || var2 & 127) )

How the machine handles the comparison is a matter for
the circuit designers and the compiler writers. What C
requires is that any two zero values generated by "proper"
means must compare equal to each other, less than all positive
integers, and greater than all negative integers.

This may just fall out of the way the machine's comparator
works. If it doesn't, C will need to take steps to "normalize"
the values before comparing them, transforming "minus zero"
to "canonical zero." There's a possible surprise here, in
that a C implementation might avoid the problem by operating
the arithmetic unit in a mode that never produces "minus
zero" as a result: that way, all zeroes are already canonical,
and the compiler need not generate normalization code. But
if you use type-punning shenanigans to generate a "minus
zero" representation by devious means, that zero might or
might not behave the way a pedigreed C zero must. (At least,
I don't see any guarantee; others might be able to find one.)

 

[pete]

pete posted:


Nicely put.

Does that mean that you MUST have padding within
a signed integer in order
for "negative zero" to be a trap representation?

No.
A signed magnitude representation
with the sign bit is set,
can either be equal to zero or not represent any number.
All bits set in one's complement, is the same way.

The reason I ask is as follows:
I recall reading something recently along the lines of "The value
representation bits of an integer type shall
not be involved in trapping".

How about:
no arithmetic operation on valid
values can generate a trap representation other than as
part of an exception such as an overflow
?

 

[pete]

A signed magnitude representation
with the sign bit is set,

with only the sign bit set,

 

[pete]

"negative zero"

ISO/IEC 9899

6.2.6.2 Integer types

2

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).
Which of these applies is implementation-defined,
as is whether the value with sign bit 1 and all value bits zero
(for the first two), or with sign bit and all value bits 1
(for one’s complement),
is a trap representation or a normal value.
In the case of sign and magnitude and one’s complement,
if this representation is a normal value it is called a
negative zero.

3 If the implementation supports negative zeros,
they shall be generated only by:
— the &, |, ^, ~, <<, and >> operators with arguments
that produce such a value;
— the +, -, *, /, and % operators where one argument
is a negative zero and the result is zero;
— compound assignment operators based on the above cases.

It is unspecified whether these cases actually generate a
negative zero or a normal zero, and whether a negative zero
becomes a normal zero when stored in an object.

4 If the implementation does not support negative zeros,
the behavior of the &, |, ^, ~, <<, and >> operators with
arguments that would produce such a value is undefined.

 

[Frederick Gotham]

Michael Mair posted:

domestic?

Eric Sosman posted:

(And there's that peculiar use of "domestic" again; it's
not a usage I've ever encountered except in your writing.)

Must be a dialectal thing (I'm Irish, but a native speaker of English).

If I say something like:

What's the domestic way of eating a banana?

Then I mean something along the lines of:

What's the commonplace and prevalent method of eating a banana which
has widespread acceptance and is well-known?

Hope that helps! : )


Another thing: up until a week or two ago, I used to always say:

-127 to 127 inclusive

But now (in my posts at least), I say:

-127 through 127

I like the ring to it, plus it's very precise. If I wanted to be equally
precise using "to", I'd have to say something like:

-127 inclusive to 127 inclusive


"through" doesn't get such usage in Ireland.


[More off-topic stuff...]

I was in the US last year, Masachusets (sorry about the spelling!),
Colarado and New York; I heard a lot of "I work Monday through Friday"
over there. In Ireland, we say "I work Monday to Friday", even though
it's ambiguous as to whether me mean inclusive, exclusive, or a
combination of both.

But by FAR the hardest things to come to grips with when travelling is
the use of slang, and also vocabulary which is mutually unknown to each
other -- things like "sweater" instead of "jumper", "trainers" instead of
"runners", "band-aids" instead of "plasters".

 

[Richard Heathfield]

Frederick Gotham said:

If I say something like:

What's the domestic way of eating a banana?

Then I mean something along the lines of:

What's the commonplace and prevalent method of eating a banana which
has widespread acceptance and is well-known?

Aha! All is now clear.

The canonical term for that is "canonical".

 

[Keith Thompson]

Michael Mair posted:



Eric Sosman posted:



Must be a dialectal thing (I'm Irish, but a native speaker of English).

If I say something like:

What's the domestic way of eating a banana?

Then I mean something along the lines of:

What's the commonplace and prevalent method of eating a banana which
has widespread acceptance and is well-known?

Hope that helps! : )

Interesting. In my version of English (and I suspect in most other
people's as well), "domestic" means roughly "from this country", as
opposed to "imported". I've never heard your usage before you
mentioned it here a few days ago.

[...]

But by FAR the hardest things to come to grips with when travelling is
the use of slang, and also vocabulary which is mutually unknown to each
other -- things like "sweater" instead of "jumper", "trainers" instead of
"runners", "band-aids" instead of "plasters".

The British slang terms for what we call "erasers" and "cigarettes"
can also cause some frivolity.

 

[Bill Pursell]

(1) Sign-magnitude: The bit-pattern is exactly the same.
(2) One's complement: Toggle each bit.
(3) Two's complement: Toggle each bit, then add 1.

This has always sort of bugged me. The description of
2's complement above is a nice way to describe the
technique for comprehending the bit pattern used to
represent an integer, but it's not a good way to describe
the system. I think a better description is: take the top
half of the unsigned integers and move them to the bottom.
Unfortunately, I can't find the right wording to explain
that description completely. Any thoughts on expanding
it sufficiently to describe it, without making it too verbose?

signed magnitude is taking the top half
of the integers, flipping them over and moving them to the
bottom, with the zeros overlapping. (From this description,
it's far more obvious why 2's complement is simpler.)

One's complement is derived by moving the top half
to the bottom and shifting up by one to make the zeros
overlap.

It feels like those descriptions are not clear to the clueless
newbie, however. I'm not sure they're even clear to anyone
unless they already understand the number system...

 

[Giorgio Pastore]

Here, my 2 cents. It is not short but I think, from my experience
with students, it allows to understand the rationale behind the definition:

signed magnitude is taking the top half of the integers, and it is
reassigning them a new meaning as negative values, with the constraint
that each (but one) of these negative numbers has a corresponding
positive partner, uniquely identified by the fact that, when they are
added, with the usual rules for sums, the result gets all bits equal to
zero.

This way, one has an operative definition and, starting from -1, a few
examples allow to fully understand how it works. Of course, one has to
stress that the choice of considering 1000...00 as the minimum negative
number (the only negative number without positive partner) is somewhat
arbitrary, although convenient to make the whole system uniform (
sequences starting with 1 should be considered as representing negative
numbers ), thus simplifying the implementation of comparison between
numbers.

Then, one can easily derive the simple algorithm (toggle each bit,
then add 1) as an effective way of finding the corresponding
sign-partner of any integer.

Giorgio

 

[Keith Thompson]

Here, my 2 cents. It is not short but I think, from my experience
with students, it allows to understand the rationale behind the
definition:

signed magnitude is taking the top half of the integers, and it is
reassigning them a new meaning as negative values, with the constraint
that each (but one) of these negative numbers has a corresponding
positive partner, uniquely identified by the fact that, when they are
added, with the usual rules for sums, the result gets all bits equal
to zero.

Your describing two's-complement, not signed magnitude.

[snip]

 

[Frederick Gotham]

Richard Heathfield posted:

Frederick Gotham said:



Aha! All is now clear.

The canonical term for that is "canonical".

Hmm... I'll have to stick that one in my vocabulary!

So what's the canonical way of eating a banana? : )

 

[Frederick Gotham]

Eric Sosman posted:

There are two bit patterns for zero, and no extra unit.

So what use is One's complement at all? If it still has two values for
zero, and has no extra unit in the negative range, then what possible good
can it do? It seems that Two's complement would be superior to it in every
way.

 

[pete]

This has always sort of bugged me. The description of
2's complement above is a nice way to describe the
technique for comprehending the bit pattern used to
represent an integer, but it's not a good way to describe
the system. I think a better description is: take the top
half of the unsigned integers and move them to the bottom.
Unfortunately, I can't find the right wording to explain
that description completely. Any thoughts on expanding
it sufficiently to describe it, without making it too verbose?

signed magnitude is taking the top half
of the integers, flipping them over and moving them to the
bottom, with the zeros overlapping. (From this description,
it's far more obvious why 2's complement is simpler.)

One's complement is derived by moving the top half
to the bottom and shifting up by one to make the zeros
overlap.

It feels like those descriptions are not clear to the clueless
newbie, however. I'm not sure they're even clear to anyone
unless they already understand the number system...

I already understand the number system.
I don't understand the following terms:
"top half of the integers"
"moving them to the bottom"

 

[pete]

Michael Mair posted:



Eric Sosman posted:



Must be a dialectal thing (I'm Irish, but a native speaker of English).

If I say something like:

What's the domestic way of eating a banana?

Then I mean something along the lines of:

What's the commonplace and prevalent method of eating a banana which
has widespread acceptance and is well-known?

Hope that helps! : )

Interesting. In my version of English (and I suspect in most other
people's as well), "domestic" means roughly "from this country", as
opposed to "imported". I've never heard your usage before you
mentioned it here a few days ago.

[...]

I had teachers that talked like that.

"Domestic" is the opposite of the of "exotic".

The primary and secondary meanings of exotic are
"foreign" and "unusual".

"Domestic" being used as the opposite
of the secondary meaning of "exotic", is exotic.

 

[pete]

Eric Sosman posted:


So what use is One's complement at all?

My guess is that the ~ (bitwise complement operator)
was a comparitively fast operation on early cpu's.

If it still has two values for
zero, and has no extra unit in the negative range,
then what possible good can it do?
It seems that Two's complement would be superior to it in every
way.

I think you sentiment is reflected in the number
of systems using two's complement versus one's complement.

 

[Flash Gordon]

Richard Heathfield posted:


Hmm... I'll have to stick that one in my vocabulary!

So what's the canonical way of eating a banana? : )

You fire it out of a cannon in to your mouth ;-)

For what it's worth, I've not come across your usage of the word
domestic either.