Talk:Two's complement

From Wikipedia, the free encyclopedia

To-do list for Two's complement: edit · history · watch · refresh
  • Describe how to extend precision (using sign extension)
  • Explain multiple precision two's complement arithemetic
  • Describe multiplication and division of two's complement numbers
  • Describe special considerations with left/right shifting
  • Consider adding a short history of the move to two's complement representation in modern computers
  • Describe the connection with the place-value representation of 2-adic integers

Contents

[edit] Requires Cleanup

This page needs to be shortened, and contain a much more consise overview of how twos complement works, on a direct practical application of which. Philcluff (talk) 02:11, 19 February 2008 (UTC)

[edit] Merge with signed number representations

Can we merge this with signed number representations? which is not too long yet and there are some overlap between that and this. -- Taku 23:23, Jul 31, 2004 (UTC)

I disagree; there may be some overlap but the pages have different purposes. Signed number representations compares different representations; this describes one of them in detail. --Rick Sidwell 03:26, 13 Apr 2005 (UTC)

[edit] Overly verbose example

In showing that -95 is congruent to 161 (mod 256), there's an example that shows "−95 + 256 = −95 + 255 + 1 = 255 − 95 + 1 = 160 + 1 = 161". What's with the verbosity? Would "-95 + 256 = 161" not work just as well?

The point of the example is to illustrate the binary subtraction. The one's complement of x
is just (255 - x). So we need the 255. Compare to the binary example immediately following.
Scottcraig 21:25, 15 July 2005 (UTC)

[edit] Re: Why it works

Ooh. All I can say is that two's complement only has to be actually implemented where the resulting numbers are actually used; a simple addition or subtraction module wouldn't care a bit (no pun intended). --Ihope127 01:49, 25 August 2005 (UTC)

[edit] Binary notation

The article uses a strange form of binary notation:

−64 = 1100 00002

The subscript 2 is usually reserved for the binary numeral system, rather than any old binary represenation. As I understand it, the above binary is how to write 192 in (mathematical) binary. Is there another way we could indicate the numbers are just binary, without using the "normal" binary counting system? —Pengo 07:29, 12 September 2005 (UTC)

I agree, though I don't have a better suggestion. --63.85.132.5 13:00, 9 March 2006 (UTC)


I'm not sure I understand what Pengo means by "any old binary represenation" or "indicate that numbers are just binary" but I'm no native English speaker.

However, why not write

−64 = 1100 00002's
−63 = 1100 00001's
192 = 1100 00002

It wouldn't be much extra work. HenkeB 01:31, 7 June 2006 (UTC)

I think the issue, if there is one, is not in the subscript but in the '='; when I talk about this kind of thing, I like to talk about a 'value' of -64 but a 'code' of 11000000, so it just needs a note about the meaning of the equivalence; it means 'coded as'. 76.67.98.29 (talk) 21:43, 6 February 2008 (UTC)

[edit] Intro changes and the concise summary

I made a few changes to the intro to try to make it more clear. The main one is the addition of the concise summary:

In an n-bit binary number, the most significant bit is usually the 2n-1s place. But in the two's complement representation, its place value is negated; it becomes the −2n-1s place and is called the sign bit.

When I discovered this, it instantly clarified everything about two's complement for me. I'm interested to know if it does the same for you, or if there is an easier way to present that idea.

I know of 3 other ways to 'get to' two's complement:

  1. the classic 2^N-b way
  2. define -1 as the bit pattern that gives you 0 when you add it to +1
  3. as a nice specialization of excess notation

Perhaps someday someone can write these up in detail here.

Ken 05:41, 2 February 2006 (UTC)Ken

[edit] calculation trick

One of my teachers mentioned a trick that was pretty useful. In calculating two's compliment, one finds the least significant 1, and flips all the bits more significant that that bit (ie. find the first 1, and flip the bits above it - but don't flip the first 1). This should have a picture to go along with it, and I don't have time now. Fresheneesz 22:47, 24 May 2006 (UTC)

[edit] Carry Bit/OverFlow Bit

I believe this page needs to be revamped. Their are a lot of inconsitentcies regarding the MSB. First of all the (Most Significant Bit (MSB) entry says that it is the highest bit of a binary value. But then it said to be the sign bit.

But more importantly, the carry bit tells you nothing in two's compliment. The overflow bit occurs when the addition of 2 positive numbers yields a negative, or the addition of two negative numbers gets a postive.

Also there is incorrect information regarding the XOR statement, the carry bit and the sign bit to do not determine the overflow bit. I shall prove this by contradiction.

 01 1111
+10 1010
 -------
 00 1001 C=1  S= 0, but V=0

Cleary the XOR argument doesn't work --NMocho 14:49, 23 July 2006 (UTC)

The article is correct regarding the XOR statement. It isn't the carry and sign bits that determine overflow, but the carry into and out of the sign bit. In this case, they are both 1, so there is no overflow. The carry out of the sign bit goes into the carry bit, and NMocho is correct that this tells you nothing in two's complement. The carry bit is useful for multi-precision addition, when the msb is an ordinary bit in the middle of a number, not the sign bit. The carry into the sign bit is not directly accessible in typical computers; it is XOR'ed with the carry out of the sign bit and stored in the overflow bit, which itself is not useful until a multi-precision addition is complete. So after any given addition operation, either the carry bit or the overflow bit is useful depending on whether it was an intermediate or final addition, but not both.
Multi-precision arithmetic isn't covered in the article. Perhaps it should be, although it isn't specific to two's complement. --Rick Sidwell 15:33, 29 July 2006 (UTC)

[edit] Explanation disorganized

It seems that at some point the text was re-arranged carelessly. In the section Explanation, reference is made to "as we did when we counted backwards", apparently referring to some preceding text that has been removed. Also there's a reference to "the aforementioned overflow checks", again apparently referring to text that has been (re)moved. At this point, I stopped reading. Ferdinand Pienaar 09:56, 31 October 2006 (UTC)

[edit] Gosper extending two's complement into infinity

Would a link to the p-adic numbers be appropiate here, considering that while meaningless in normal number space, Gosper's proof actually IS correct for the 2-adic numbers? I know I once indepently got the idea of p-adic numbers from extending two's complement, though I never did much with it. -- Milo

I came here to say something like that. The 2-adic integers in particular are exactly the set of binary expressions of the form …bbb, so it seems perverse to reinterpret such an expression as an ordinary number and then note that it no longer makes sense. I'm sure there are sources that explain …111, but I don't have one ready, so I'll just remove the paragraph in question. Melchoir 17:01, 15 February 2007 (UTC)

Melchoir, I reverted your removal. Gosper's "proof" is given in terms of the natural numbers, not the 2-adic numbers; indeed, it wouldn't be interesting if it stated a tautology about an obscure system, instead of "proving" something cute about an everyday system. Given the number of newbies who are confused by "0.9999... is the same as 1.0", I think it's very important to retain the paragraph pointing out that Gosper's "proof" is a mathematical joke, and should not be taken seriously. (Gosper's point, IMHO, was that two's complement is the best binary number representation, and I agree with that. But his conclusion that "the Universe is run on a two's complement machine" is obviously not meant to be taken literally; it's a hacker joke.) --Quuxplusone 03:06, 16 February 2007 (UTC)

The Universe bit may be a joke, and that's already indicated by the "flight of fancy" language. But the mathematics is not a joke. The manipulation …110 = …111 − 1 is correct, and it is part of a valid proof of the value of …111. It's not that …111 "cannot" be considered a number in ordinary mathematics; it simply isn't considered in ordinary mathematics at all. There is no barrier to doing so, since the natural numbers are faithfully embedded in the 2-adic integers as the set of expressions with either leading 0s or leading 1s. Given all that, do you really think this is comparable to Mathematical jokes like "sex is fun" and Invalid proofs like i^2=1? Melchoir 04:42, 16 February 2007 (UTC)
I agree that Gosper's approach is sensible and somewhat logical. Two's complement numbers are always considered to have as many higher-order sign extensions as you need, out to infinity, conceptually. This is consistent with the value of ...11111 being -1 and nothing else; the value is unchanged with any finite truncation, as long as the MSB is treated as the sign. His logic makes sense for any finte length of the "...". Dicklyon 05:52, 16 February 2007 (UTC)
I do claim that Gosper's "proof" was meant to be taken humorously. For reference, we're talking about this item, which ends "therefore algebra is run on a machine (the universe) which is twos-complement." That's a joke. "Sex = f(un)" might also be considered a "mathematical joke", but it's certainly on a different level, wouldn't you say? Gosper's joke is more akin in spirit to the observation that

The equation na+nb=nc has solutions in positive integers a,b,c, and n only when n=2 (and then there are infinitely many triplets a,b,c which satisfy the equation); but there are no solutions for n>2. I have discovered a truly marvelous proof of this statement, which, unfortunately, is so small that it would be well-nigh invisible if written in the margin.

– Lierre de Fourmi, in the margin of Di of Antus' Arithmetica, p. 333

Anyway, I don't really care one way or the another if you think Gosper was talking about p-adic numbers (he wasn't) or integers (he was). The clarifying paragraph certainly needs to be there in any case, so unless you want to keep trading quotations of other people's jokes, I'll move on. :) --Quuxplusone 09:18, 16 February 2007 (UTC)
I'm not disagreeing that the conclusion is meant to be taken humorously! But the mathematics isn't wrong in any meaningful way, whereas it's right in several meaningful ways. I'll try to fix the description. Melchoir 15:45, 16 February 2007 (UTC)

…Um, I appreciate that compromise is important, but this edit contains a lot of subtle problems that I tried hard to avoid. It's important to differentiate between Gosper's conclusion as a whole and the very end conclusion, since the first, mathematical part isn't a joke. Writing "see also Invalid proof" very strongly suggests that the proof in question is itself invalid, which it isn't. The phrase "can be treated as a number" is unmathematical; it is alway possible to make new definitions if necessary, or in this case to exploit old definitions that not everyone knows about. There's also no distinct "ordinary algebra", at least not in the sense that some subfield of mathematics manages to contain different results from the rest of mathematics. All one can say is that the definitions one learns in elementary school are insufficient to reason with …111. Finally, the three items in the last sentence are distinct, and they don't need to be merged. I'll expand on that last point and throw in Hardy as a source. Melchoir 02:12, 17 February 2007 (UTC)

Update: 1 + 2 + 4 + 8 + · · · now includes some of Quuxplusone's points, although it has yet to get to the 2-adic stuff. Melchoir 05:38, 17 February 2007 (UTC)

[edit] "Two's" and "ones'" complements?

A quick GBS search shows that both "twos complement" and "ones complement" are most often written without any apostrophe. This would seem preferable to the mixed way we have in this article. Or should we changes "ones'" back to "one's" or "two's" to "twos'"? Dicklyon 07:42, 19 December 2006 (UTC)

If "GBS" stands for Google Book Search, then I think what you're seeing is that Google doesn't consider the placement of apostrophes to be significant. Searching for twos complement and ones complement, with any of the three candidate punctuations, shows that the majority of the first page of results for any candidate punctuation are punctuated the way we have it: two's and ones'. My rationale is that Knuth does it that way, and has a good explanation for his choice, so let's follow the leader. But if everybody else also does it that way, that's good for us too. :) --Quuxplusone 06:09, 8 February 2007 (UTC)
Detail-oriented readers and copy editors should notice the position of the apostrophe in terms like two's complement and ones' complement: A two's complement number is complemented with respect to a single power of 2, while a ones' complement number is complemented with respect to a long sequence of 1s. (Volume 2, p. 203, according to [1])
No, I didn't rely on the search function to make the distinction; I just looked at all the occurrences to see how they were punctuated. I do agree with the logic of what you found there, I guess we're fine. Dicklyon 06:20, 8 February 2007 (UTC)

[edit] Division

This page covers addition, subtraction and multiplication. But what about division? (restoring/non-restoring) —Preceding unsigned comment added by 128.54.69.212 (talk • contribs) 18:50, 7 February 2007

It's in the to-do list. Have at it. Dicklyon 01:08, 8 February 2007 (UTC)

[edit] Weighting of LSB is assumed to be 1 for this article.

The weight of the least significant bit (LSB) is often assumed in this article to be 1, which is not a problem for addition or subtraction, and multiplication. However, the value 0111 in a two's compliment system can represent 7, 7/8, 7/4, for LSB weights of 1, 1/8th, and 1/4 respectively. This *usually* does not matter for many operators; however, it does in fact matter for some operators. E.g, the square root operator used on 0100 would produce 0010 if the weight of the LSB is 1, but would produce approimately 0101 (trucation) or 0110 (rounding) if the weight of the LSB is 1/8. Tata2007 18:11, 3 October 2007 (UTC)

It is always much easier to discuss the two's-complement representation of integers, but you're right that a note somewhere about how fixed-point fractions and floating-point mantissas use these integers with a power-of-two multiplier, whether implicit or explicit. Dicklyon 21:11, 3 October 2007 (UTC)

[edit] "howto" tag

I re-added the howto template, and also added the {{disputed}} template to open it up to wider discussion. The section does read like a how to or a receipe. Tata2007 14:36, 4 October 2007 (UTC)

I just removed the {{disputed}} template tag as it was not the correct template (it called into question the factual accuracy, which in fact is not in dispute). Tata2007 14:38, 4 October 2007 (UTC)
I think the section is fine. I would argue that the process of converting numbers to two's complement form is integral to readers' understanding on the issue. --pie4all88 19:39, 6 October 2007 (UTC)
I think it's OK, too. The tag says "This section contains instructions, advice, or how-to content," but I don't interpret it that way. It's a bit too-detailed as a description and example of the process of generating a two-complement, but it's certainly not advice, and not really instructions per se. So tune it up instead of tagging it. Dicklyon 19:44, 6 October 2007 (UTC)
If it needs a tune up (and I think it does) the tag will help attract editors to do this. Tata2007 20:13, 8 October 2007 (UTC)

[edit] ubiquitous two's-complement

I am considering adding a fact tag to the following sentence, but is also has other problems (implicit comparison to one's complement is too subtle).

“ The two's-complement system is ubiquitous today because it doesn't require that the addition and subtraction circuitry examine the signs of the operands to determine whether to add or subtract, making it both simpler to implement and capable of easily handling higher precision arithmetic. ”

The implication is that computers implement two's complement much more often than one's complement for the reason stated. E.g., it might be more precisely written:

“ The two's-complement system is ubiquitous today for a number of reasons. First, addition and subtraction circuitry is simplier than what is required for one's complement system. Second, two's complement does not have abiguity with zero while one's complement has positive and negative zeros. ”

This, I believe, it true and verifiable; but I don't have a refernce at hand. Also, I do think the assertion that two's complement is "capable of easily handling higher precision arithmetic" should be sourced. Tata2007 14:53, 4 October 2007 (UTC)

One's complement is not the only plausible alternative. The system of sign & magnitude has also been used. Both are more complicated, and no system designed since about 1980, I think, uses anything but two's complement, for the reason given. Although, inside floating point numbers, perhaps sign and magnitude are still used. Dicklyon (talk) 17:09, 16 March 2008 (UTC)

[edit] Advantages of 2's compliment

Could someone clearly state the advantages of 2's compliment. Chendy (talk) 16:57, 16 March 2008 (UTC)

First, learn the word complement and what it means, and how it differs from compliment. Then note that this representation allows addition and subtraction of signed numbers to work very easily, with uniform simple logic, and for multiplication and division to also be not bad. That's why all modern computers use it. Dicklyon (talk) 17:07, 16 March 2008 (UTC)

[edit] Explanation

Table "8-bit two's-complement integers" is wrong for 127 value : 127 = 1111111b. —Preceding unsigned comment added by 66.130.36.239 (talk • contribs)

I presume you mean to explain this edit. Yet your explanation is backwards. What's up with that? Dicklyon (talk) 06:04, 15 May 2008 (UTC)