Working with negative numbers

[Frederick Gotham]

pete posted:

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.

Yeah, that kind of gets a handle on it.

There's an exotic way of eating a banana (e.g. like Kevin Spacey in K-Pax
who didn't remove its skin first), and there's the domestic way of eating
a banana (i.e. removing the skin and eating the stuff inside).

 

[Eric Sosman]

Eric Sosman posted:






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.

Two's complement has one glaring disadvantage not shared
by the other allowed representations: it has an asymmetrical
range, with more negative values than positives.

Can you spot the error in this silly little number-printer?

#include <stdio.h>
void outnum(int num) {
if (num < 0) {
putchar ('-');
num = -num;
}
if (num > 10)
outnum(num / 10);
putchar ('0' + num % 10);
}

 

[Eric Sosman]

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?

Think of the sign bit in two's complement as representing
twice the value of the highest-order value bit, but with a
negative sign. In sixteen-bit two's complement, the bits
are "worth"

bit 0: 1
bit 1: 2
bit 2: 4
...
bit 13: 8192
bit 14: 16384
sign bit: -32768

The value of the integer is the sum of the values corresponding
to all its one-bits.

 

[Dik T. Winter]

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

And it made multipliers for signed integers much easier. Almost all early
computers were either 1's complement or sign-magnitude.

 

[Dik T. Winter]

> There's an exotic way of eating a banana (e.g. like Kevin Spacey in K-Pax
> who didn't remove its skin first), and there's the domestic way of eating
> a banana (i.e. removing the skin and eating the stuff inside).

Merriam-Webster:
domestic, adjective:
1. Living near or about human habitations (tame, domesticated)
2. Of, relating to, or originating with a country and especially
one's own country
3. of or relating to the household or the family
4. devoted to home duties and pleasures
5. indigenous

indigenous, adjective
1. having originated in and being produced, growing, living or
occurring naturally in a particular region or environment

 

[Frederick Gotham]

Eric Sosman posted:

Can you spot the error in this silly little number-printer?

#include <stdio.h>
void outnum(int num) {
if (num < 0) {
putchar ('-');
num = -num;

^^^^

I presume this is the error?

If the range were -128 through 127, and it the value of num were -128,
then we can't represent its positive counterpart.

What does the Standard have to say about doing that? Implementation-
defined behaviour, or undefined behaviour?

 

[Dik T. Winter]

> Bill Pursell wrote: ....
>
> Think of the sign bit in two's complement as representing
> twice the value of the highest-order value bit, but with a
> negative sign. In sixteen-bit two's complement, the bits
> are "worth"
>
> bit 0: 1
> bit 1: 2
> bit 2: 4
> ...
> bit 13: 8192
> bit 14: 16384
> sign bit: -32768

And for 1's complement make it -32767 (i.e. one more than the value for
2's complement).

 

[Roberto Waltman]

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

Domestic bliss vs. imported bliss?

(English my native is not language either.)

 

[Richard Tobin]

...

Merriam-Webster:
domestic, adjective:

Obviously the OP's use of "domestic" is an extension of the original
use. In Britain the phrase "common or garden" (originally, I assume,
applied to plant varieties) is used in this way, so that I wouldn't be
very surprised to hear someone refer to, say, a "common or garden sort
algorithm". But I doubt that "domestic" will pass into common usage
for this.

-- Richard

 

[Richard Tobin]

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".

As far as I can tell, that's predominantly a U.S. usage. It seems to
be creeping into use in Britain through airports ("domestic flights",
formerly "internal").

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

We just made them up to confuse Americans.

Incidentally, the material "rubber" is so called because rubbing-out
(=erasing) was the first use of it, rather than the rubbers (=erasers)
being so-called because they were made of rubber.

-- Richard

 

[Richard Bos]

pete posted:


Yeah, that kind of gets a handle on it.

There's an exotic way of eating a banana (e.g. like Kevin Spacey in K-Pax
who didn't remove its skin first), and there's the domestic way of eating
a banana (i.e. removing the skin and eating the stuff inside).

Oh. That's not the canonical way, that's the vanilla way. In this case
they happen to be the same, but that's not always the case.

Richard

 

[Frederick Gotham]

Dik T. Winter posted:

Merriam-Webster:
domestic, adjective:
1. Living near or about human habitations (tame, domesticated)
2. Of, relating to, or originating with a country and especially
one's own country
3. of or relating to the household or the family
4. devoted to home duties and pleasures
5. indigenous

indigenous, adjective
1. having originated in and being produced, growing, living or
occurring naturally in a particular region or environment

Is that suppose to prove a point?

I'm a native speaker of English, and I know how to speak.

Where I'm from, "domestic" can mean something along the lines of
"ordinary".

Throw five thousand dictionaries at me that say otherwise and it won't
make a blind bit of difference.

 

[Michael Mair]

Eric Sosman posted:


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.

You did not really read my reply <[email protected]>
before replying to "domestic", did you?

-Michael

 

[Frederick Gotham]

pete posted:

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.

Here's a post I read on comp.lang.c++ today:


http://groups.google.ie/group/comp.lang.c++/msg/e71c844f680661ba?hl=en&


Note its use of "exotic". In Ireland, we make similar arbitrary use of the
word "domestic".

 

[Bill Pursell]

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

By "top half of the unsigned integers", I mean those
values with the MSB set. I'm picturing the values stacked
up with 00..00 on the bottom and 11..11 on the top and
the number line to the right of the stack, with the number
line aligned in such a way that each bit collection is next
to it's usual interpretation. So negative values and those
above UINT_MAX have nothing to the left of them. Now
grab the top half of the stack and move it down so that
11..11 is to the left of -1. It's a graphic that I can see clearly
in my head, but I don't think I've ever described it accurately
enough to explain it to anyone that didn't already grok. Maybe
it's just a bad description....

 

[Keith Thompson]

Dik T. Winter posted:

Is that suppose to prove a point?

I'm a native speaker of English, and I know how to speak.

Where I'm from, "domestic" can mean something along the lines of
"ordinary".

Throw five thousand dictionaries at me that say otherwise and it won't
make a blind bit of difference.

I don't disagree with any of that.

But if you use "domestic" to mean "ordinary", few people who haven't
read this thread will understand what you mean. If you want to be
understood (which I presume is a goal when you post to Usenet), I
respectfully suggest that you avoid that particular usage -- not
because there's anything wrong with it, but because the vast majority
of us are too ignorant of your particular dialect to understand it.

 

[Mark McIntyre]

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?

Curious. I have /never/ heard this usage of domestic before, except
in highly specialised expressions such as "domestic science "
(cookery). If I wanted to say "normal" I'd say normal.

Hope that helps! : )

Not really !
--
Mark McIntyre

"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it."
--Brian Kernighan

 

[Keith Thompson]

Curious. I have /never/ heard this usage of domestic before, except
in highly specialised expressions such as "domestic science "
(cookery). If I wanted to say "normal" I'd say normal.

In "domestic science", I think "domestic" means "in the home", so it's
not an example of Frederick's usage of "domestic" to mean "ordinary".

 

[Dave Thompson]

Much as 2sC allows the exact same hardware for addition (and
subtraction) of both signed and unsigned, 1sC uses the same hardware
with only addition of end-around-carry (as already noted) which for
ripple carry (which AFAIK all early machines were; lookahead carry
networks are too costly in discrete logic) is just 3 more gates.
Right, because each bit is independent. Basically 1sC gives you _much_
of the advantage of 2sC with less added delay. Today this tradeoff is
different because even several gate delays are like one zillionth of
off-chip (especially memory) times.

And it made multipliers for signed integers much easier. Almost all early
computers were either 1's complement or sign-magnitude.

S&M makes multiply easier. AIR 1sC does not; it requires correction
terms as bad (or slightly worse) than 2sC.

- David.Thompson1 at worldnet.att.net

 

[websnarf]

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?

I'm a math person, so I just think of it as 2sC(x) -> x (mod 256); the
positive residue of x modulo 256. A set of residues generally forms a
ring, so the operations, +, -, * and << work as you would expect in the
ring, which is intuitively mapped to the generally integers within
small ranges.

2s complement addition also supports the following relation:

A+B+C = 2*((A and B) or (A and C) or (B and C)) + (A xor B xor C)

Notice how there are two additions on the left side and one on the
right side. So, assuming that you can make hardware for ands and ors
that is way faster than addition (which is the case in the real world,
since ands and ors are completely bit parallel, while addition
generally is not) you can actually compute two serial adds in nearly
the same speed as a single addition. This can be used for improving
hardware speed by quite a bit.

Another interesting formula worth considering is the following:

average = (a + b) / 2

This came up in some digg story a few weeks ago (in which it was
reported that nearly every binary search implementation fails.) The
problem is that if (a+b) overflows, it will inevitably create a
negative number which, after division by two, will result in a
completely erroneous answer. In twos complement we have this:

a + b = 2*(a & b) + (a ^ b)

(set c = 0 in the formula given above.) So we can compute the average
easily by:

average = (a & b) + ((a ^ b) / 2)

which we can easily see has no overflow problems.

Multiplication only needs "fixing" for double-wide multipliers. (But
this is beyond the people in in c.l.c; At least there seems to be
nobody in this n.g. who have any idea what that is or why it is so
important.) You can think about the fix by imagining that the original
operands were as wide as the indended result by sign extending them
appropriately, then the truncated result will be correct.

Division is obviously not an analogy to modulo inversion, but is rather
just a truncating division. I haven't looked deeply at it, but the way
I would do division would be by iterating a division estimator, which
can be done via table look-ups, which can take negative numbers into
account.

Anyhow, this is why 2s complement is so clearly superior to alternative
methods which don't have useful properties anywhere near as useful.
Fortunately, this has been recognized right from the creation of the
very first microprocessor.