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

71–80 of 92 posts

Re: Two's complement – You beauty

#71

Post by kps »

gizmo686 wrote: post #22
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…

I didn't downvote you. However, I am a math person and your post feels wrong for some reason. It isn't wrong, but it feels like it should be; and I am not entirely sure why. CPUs use modular arithmetic for both signed (two's complement) and unsigned values, so that cannot be the defining feature of twos complement. The insight with two's complement is that we can interperet the "upper" half of numbers as negative. As…

  > However, the result of the multiplication of two n-bit numbers
  > could be as big as 2n-bits.
For unsigned multiplication. For signed two's complement multiplication, it's at most 2n−1 bits, and that is only when multiplying the two most negative numbers; otherwise it's at most 2n−2 bits.

~~~ wavy line flashback ~~~

A few years ago, I did a C code generator for a 2's complement 16-bit processor that had mostly adopted the convention that 0x8000 was an invalid sentinel value, so that integers would have a symmetric range around zero, ±0x7FFF. This was mostly a software convention (i.e. the ALU didn't trap or anything like that) except that, given that 0x8000 was 'unused', the multiplier only produced a 30 bit result. This made C 'long' multiplication interesting.

Re: Two's complement – You beauty

#72

Post by kps »

Turing_Machine wrote: post #46
gumby wrote: post #19

Earlier quoted context omitted.

> What _is_ annoying about the UNISYS boxes is the 36 bit word format, though. Characters are stored in 9 bit quarterwords that map pretty awkwardly to bytes containing 8-bit ASCII. Binary data formats are essentially incompatible with anything. This is why the FTP protocol has a byte size command. If all you have is 8-bit bytes then that seems strange. But at the time FTP was designed the most common machines on the…

> 7-bit ascii was common (5 characters would fit in a word, like my username GUMBY), as were six bit bytes (pack six characters into a word) There were a bunch of different six bit character encodings, often (though not always strictly correctly) called "BCD". The horror show of IBM's EBCDIC was an eight bit extension of one of these. Then there was 5 bit Baudot code, and... The last time I checked, many *nix systems…

  > … *nix systems will still assume that you're on a 5 bit Baudot (uppercase only) teletype …
Akshully the original 1963 version of ASCII¹, which was a 7 bit code but did not include lower case. The Model 33 teletype² (one of the terminals used by UNIX developers³, and probably a contributing factor to two-character command names) was a 1963-ASCII device. Even after 1967 ASCII added lower case, popular low end video terminals⁴ did not include it so that they could get away with 6 bits worth of printable character ROM.

¹ http://worldpowersystems.com/archives/codes/X3.4-1963/index....

² https://en.wikipedia.org/wiki/Teletype_Model_33

³ https://commons.wikimedia.org/wiki/File:Ken_Thompson_(sittin...

⁴ https://en.wikipedia.org/wiki/ADM-3A

Re: Two's complement – You beauty

#73

Post by gumby »

ramshorns wrote: post #25
gumby wrote: post #19

Earlier quoted context omitted.

> What _is_ annoying about the UNISYS boxes is the 36 bit word format, though. Characters are stored in 9 bit quarterwords that map pretty awkwardly to bytes containing 8-bit ASCII. Binary data formats are essentially incompatible with anything. This is why the FTP protocol has a byte size command. If all you have is 8-bit bytes then that seems strange. But at the time FTP was designed the most common machines on the…

The example C function in the article uses 8 instead of CHAR_BIT, which today seems not worth complaining about. I never knew there used to be so many machines with non-8-bit bytes.

> I never knew there used to be so many machines with non-8-bit bytes.

It's not like the 8 bit byte was the initial default and others were experiments.

FWIW I believe the 8-bit byte was an IBMism, and for whatever reason I don't remember IBM machines being particularly popular on the ARPANET, which was a research network.

Although its arrival well predated me I do remember a conversation with someone in which we were surprised by how it was becoming common to see people assume that a byte was a fixed 8 bits. I think that was entirely due to the spread of the Vax.

Re: Two's complement – You beauty

#74

Post by ramshorns »

chii wrote: post #18

the https://en.wikipedia.org/wiki/Method_of_complements article explains a more fundamental piece of information about this operation - i often see articles explaining two's complement, but doesn't say anything about this general 'complement' method (which works for all bases, not just binary).

> In the decimal numbering system, the radix complement is called the ten's complement and the diminished radix complement the nines' complement. In binary, the radix complement is called the two's complement and the diminished radix complement the ones' complement. The naming of complements in other bases is similar. Some people, notably Donald Knuth, recommend using the placement of the apostrophe to distinguish between the radix complement and the diminished radix complement. In this usage, the four's complement refers to the radix complement of a number in base four while fours' complement is the diminished radix complement of a number in base 5.

That makes sense. The names one's complement and two's complement are kind of confusing otherwise, since they actually refer to totally different things, and it's not clear how they would generalize to higher bases.

Re: Two's complement – You beauty

#75

Post by phkahler »

gizmo686 wrote: post #22
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…

I didn't downvote you. However, I am a math person and your post feels wrong for some reason. It isn't wrong, but it feels like it should be; and I am not entirely sure why. CPUs use modular arithmetic for both signed (two's complement) and unsigned values, so that cannot be the defining feature of twos complement. The insight with two's complement is that we can interperet the "upper" half of numbers as negative. As…

Another way to do signed comparisons (I think) is to simply invert the top bit and do an unsigned comparison. For the 3-bit example this is equivalent to adding 4 to both numbers which will shift the range from (-4,3) to (0,7).

So in hardware this amounts to routing one bit of the instruction to be XORed with the sign bits of the operands. You then get signed and unsigned comparison. It's these trivial hardware implementations that made 2's complement the standard way of doing things. using 2 gates to implement a variation on an instruction is awesome.

edit: it would not surprise me if there is an even simpler way to do it.

Re: Two's complement – You beauty

#76

Post by jonsen »

paulddraper wrote: post #69

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.

Maybee conversion to/from character code is easier. Notice the conversion code in the linked article.

Re: Two's complement – You beauty

#77

Post by kps »

gumby wrote: post #73
ramshorns wrote: post #25

Earlier quoted context omitted.

The example C function in the article uses 8 instead of CHAR_BIT, which today seems not worth complaining about. I never knew there used to be so many machines with non-8-bit bytes.

> I never knew there used to be so many machines with non-8-bit bytes. It's not like the 8 bit byte was the initial default and others were experiments. FWIW I believe the 8-bit byte was an IBMism, and for whatever reason I don't remember IBM machines being particularly popular on the ARPANET, which was a research network. Although its arrival well predated me I do remember a conversation with someone in which we wer…

Yes. The early situation was very different; see e.g. http://www.ed-thelen.org/comp-hist/BRL-III-B.html from 1955.

The IBM 360 (1964–) was the killer 8-bit-byte machine.

Re: Two's complement – You beauty

#78

Post by wahern »

1010111 wrote: post #17

Shitty C code: the binary printing function is needlessly complicated. void print_bin(int x){ for(unsigned m=~(~0u>>1); m ; m>>=1) putchar(x&m?'1':'0'); putchar('\n'); }

This code (`x & m`) promotes x to unsigned, which means you're not actually printing the bit representation of a signed integer. You'd get the wrong bit pattern for a negative number on ones' complement machines, as signed-to-unsigned conversions are well defined in C and obey modulo semantics. So, for example, `-1` would print as `1 ... 111` instead of `1 ... 110`.

Re: Two's complement – You beauty

#79

Post by brandonbloom »

AstralStorm wrote: post #50
ema wrote: post #47

Earlier quoted context omitted.

same as the infinite number of zeros in front of a positive number.

Just trimming 1s would be ambiguous. Is b11 3 or -2? You would have to add a 0 prefix to all positive numbers or some other to negative.

Just prefix a + or - just like you do for base 10.

Re: Two's complement – You beauty

#80

Post by dahart »

vog wrote: post #60
dahart wrote: post #57

Earlier quoted context omitted.

I didn't downvote, but the article was comparing one's complement to two's complement. One's complement also requires arithmetic modulo 2^n, so nothing you've said is unique to two's complement or helps to explain why it works. With two's complement, you flip all the bits, and then add 1 to the result . The surprise is that you can shift the negative half of the circle by 1 and everything still works. And not only do…

> The surprise is that you can shift the negative half of the circle by 1 and everything still works But this, again, has has nothing to do with binary but all with modulo arithmetics. If you think in modulo arithmetics, this is still no "surprise". For example, if you calculate modulo 1000 you don't distinguish between 777 and (777 + 1000x) for any integer x. That is, the following numbers are treated the same: 777,…

You're still talking about the modulo circle, and not two's complement relative to 1's complement. Everything you just said having to do with the modulo circle applies to 1's complement. Do you know the difference between 1's complement and 2's complement, and can you explain that difference? Your comments make me suspect you might not understand what 2's complement is. I don't mean that to be insulting, I was only trying to be helpful and explain what my perception of your first comment was, and guess at why people might have downvoted it, since you asked. I realize that suggesting you might be misunderstanding, even if you do understand it, can feel very irritating, and I apologize for that in advance.

Everybody knows about the modulo part, everyone reading this understands that you have a set number of bits, and that positive numbers wrap around to negative ones. That is not what's interesting here, and it is not the key differentiating factor to understanding two's complement, when comparing it to one's complement.

> The only binary-specific thing here is how the tie is resolved in the signed case.

This doesn't feel accurate to me. I'm not exactly sure what you mean by a "tie". But for 1's complement, you have two representations for 0. With 2's complement, you have one representation for 0. The representation for all negative numbers in 2's complement are offset by 1 from the same negative number in 1's complement. Yet both systems allow you to add together two numbers, mixing positive & negative, and get a result that is valid for the system. Why? Why are there two different ways? What happens when I overflow in each system? How does multiplying and dividing work in each system? Those are the interesting questions with complements.

Post reply on HN