Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Two's complement – You beauty

everyogi.in

Post reply on HN
Print view View original

61–70 of 92 posts

Re: Two's complement – You beauty

#61

Post by white-flame »

Elrac wrote: post #9

I program a UNISYS 2200 mainframe at work. It uses 1's complement. Yes, there are two zeros. Not a problem in practice because all arithmetic operations normalize -0 to +0 at no extra cost in execution time, so -0 practially doesn't happen. IIRC from Assembler class, addition is implemented as subtraction of the negative operand. Just in case anyone ever needs it, e.g. for bitmaps, the SZ (store zero) assembler instr…

> When reading dumps, not having to perform an extra addition (subtraction?) when changing a number's sign is pretty sweet!

So I've not worked with 1's complement machines, but how do you add a negative number to a positive number?

For instance, 5 + -3 in one's complement would naively be:

    000101
  + 111100
  --------
    000001 instead of 2
Doesn't the machine have to perform some fixup for negative numbers in this more common case, instead of a fixup during the arguably less common negation?

Re: Two's complement – You beauty

#63

Post by misterrobot »

vog wrote: post #6

This all is suddenly less surprising for people who learned some modulo arithmetics in school (or university). That is, calculating with the remainders of division. For example: - Calculating "modulo 60" means calculating time with a round clock in mind, considering only minutes and ignoring hours (and seconds). - Calculating with angles (in degrees) means just calculating "modulo 360". - "modulo 1000" means calculat…

"Division" i.e. multiplying by the multiplicative inverse doesn't require the modulus be prime; it just requires that the number you are finding the inverse of and the modulus are relatively prime.

Re: Two's complement – You beauty

#64

Post by white-flame »

Looking at limited-digit odometer style devices gives the best example of why 2's complement is saner.

  ...    or  ...
  9998       1110
  9999       1111
  0000       0000
  0001       0001
  0002       0010
  ...
What number is before 0 in binary? 1111. So that's where -1 is. The number before that? 1110, so that's -2. The whole XOR + 1 thing can be derived from this shape.

That, and simple addition of both signed and unsigned numbers actually works. :)

The only question is where you draw the line between underflowing negatives and overflowing positives, and going halfsies on the top bit seems to make sense. For an 8-bit number, there are 128 numbers on each of the negative/non-negative split, but zero mucks it up by being not mathematically positive. 1's complement evens it out by having 127 numbers on each side plus two zeros, but messes up signed math.

Re: Two's complement – You beauty

#65

Post by SamBam »

kybernetikos wrote: post #10
0xcde4c3db wrote: post #4

> There would be two ways to represent 0, as +0 and -0. IEEE 754 floating point actually has this (due to having a dedicated sign bit). I think most code doesn't care (IIRC they are defined as equal for comparison purposes even though the bits are different in memory), but apparently it's sometimes handy to have for some functions that have a discontinuity at zero or otherwise need to preserve the sign through a mult…

Because of this, javascript has a +0 and a -0. They make a fun trivia question because there are very few ways to distinguish them since most of the ways of checking equality (even ===) will report that they are equal. In fact, I only know two ways to distinguish them: divide something by them, and you get positive infinity for +0 and negative infinity for -0, or you can use Object.is(-0, 0) which will return false.

Weird. I just tried it out. So in Javascript you can have two variables, `a` and `b`, such that `a === b` and `1/a !== 1/b`.

Re: Two's complement – You beauty

#66

Post by TillE »

eps wrote: post #14

It's an elegant construct, but this used to be a part of an entry-level course in every computer school I know of. Have things changed now?

I suspect lots of people here have little or no higher education. Mine was 10+ years ago, so an occasional refresher can be nice; I remember the general concepts, but not necessarily the details.

Re: Two's complement – You beauty

#69

Post by paulddraper »

If you're looking for true beauty, look no further than negabinary. (http://mathworld.wolfram.com/Negabinary.html)

E.g.

     3 = (-2)^2 + (-2)^1 + (-2)^0 = 0110_-2
    -3 = (-2)^3 + (-2)^2 + (-2)^0 = 1101_-2
There is no signed bit, you don't have to worry about sign; everything just works like "normal" numbers because that in fact is what it is.

A pity it was never used except a few times in early computing. I'm never sure why 2's-complement won.

Re: Two's complement – You beauty

#70

Post by ashark »

TillE wrote: post #66
eps wrote: post #14

It's an elegant construct, but this used to be a part of an entry-level course in every computer school I know of. Have things changed now?

I suspect lots of people here have little or no higher education. Mine was 10+ years ago, so an occasional refresher can be nice; I remember the general concepts, but not necessarily the details.

The category of Things I Once Knew but Have Since Forgotten because I Don't Them Often Enough probably includes 95+% of everything I've ever learned about both mathematics and computers/programming.

The people on here who rattle off the names of various mathematical theorems like it's nothing and act like it's weird not to remember how intro-level algorithms work without thinking really hard and doing some trial-and-error for a while or consulting a reference must have much more interesting jobs than I ever have. :-/

Post reply on HN