5 ms·

I think, you can't address two's complement without mentioning ones' complement. So what is ones' complement? Simply all bits flipped. (XOR the word length – e

I think, you can't address two's complement without mentioning ones' complement. So what is ones' complement? Simply all bits flipped. (XOR the word length – each bit becomes its complement.) There's a simplicity and beauty to this and math just works with addition and subtraction. There's also the notable feature of the most significant bit, which, if excluded from the usable range of numbers, becomes the sign-bit. If it is empty (clear), it must be a positive number, if it's set, we have a negative number (since it must be a clear bit flipped). So everything perfect, then? Not at all. What happens, if we flip all bits on zero (0000)? Well, it becomes all bits set (1111). How do we convert a number to it's signed counterpart? We flip all bits and … Oh, this must be negative zero. Maybe we can deal with this? Sort of. But it's somewhat nasty, because we need an extra steps to traverse zero. Say, we go from +1 to -1, there isn't just a zero in between, making this a difference of 2 – as it should be –, but there's +0 and -0. Three steps. That's odd. Can we do something about this? Namely, can we get rid of negative zero? Well, as we've seen, we have an extra step on the negative side of things… what about just adding 1 to compensate for this? So, for -1, we wouldn't write 1110 (flipping all bits of 0001), but 1111? Just the same, for -2, we would add 1 to 1101, making this 1110, and so on. – Well, this works! we just eliminated negative zero! Welcome to two's complement. (So, is it now perfect? Well, sort of. We now have introduced a certain asymmetry into our number system: on the side of things, where the sign-bit is clear, zero is the first number and +1 the second one, while numbers with the sign-bit set start with -1. Thus, we have an excess number on the negative side of the number range described by our word length. We just can't have it all. Well, we could switch to balanced ternary, but this is another story…)

omnicognate 3y ago
The apostrophe placement is significant: it's two's complement (complement of two) but ones' complement (complement of ones, plural).
- masswerk 3y ago
  Fixed. (I will do this error anytime.)
- jodrellblank 3y ago
  Thanks! I wonder if instead of ones’ and two’s we could use more distinct names like the Boolean values, trues’ and two’s… oh that isn’t better.
munchler 3y ago
Agreed. A crucial benefit of two’s complement is that it eliminates the distinction between +0 and -0.
nayuki 3y ago
> So, is it now perfect? Well, sort of. We now have introduced a certain asymmetry into our number system I think some systems use the INT_MIN bit pattern as a sort of not-a-number integer trap?
- masswerk 3y ago
  I think, it's more an aesthetic than a technical annoyance. But, since there was ones' compliment first (implemented in about every early computer), it may be worth mentioning that there was something lost, as well. (So, for a byte, the range is now -128…+127, which isn't that pretty, while it had been -127…+127 with ones' complement.) You may be right about NaN representation, but I don't know for certain. Notably, negative zero lived on in scientific computing, and you can have it even in JS, if you set the language version to "1.2". (Edit/Correction: setting the type to "javascript1.2" no longer works, all versions are now synonymous with just plain "javascript".)
FullstakBlogger 3y ago
Why does starting with ones' compliment make things easier? IMV, it makes it more confusing, because two's compliment seems like an arbitrary leap that happens to work. If you're tasked with mapping a subset of bit-states to negative numbers, it's intuitively obvious that there's already a state that yields 0 when you add 1 to it, as long as you wrap on overflow. With four bits that's 1111. That's a great representation of -1. If you want to get 0 by adding 2, you'd have to start from 1110, and so on. Just because the top bit can be used to identify a negative number when you use up half the states, doesn't mean it should be thought of as a logical flag. That's how you invent ones' compliment. I think of ones' compliment as a logical encoding, and two's compliment as an arithmetic encoding, and it shows in how easy negation is in ones' compliment, and how easy arithmetic is in two's compliment. The fact that everyone tries to teach them as if one is a precursor to the other is what's confusing.
- masswerk 3y ago
  It's really, because it's were we came from. Early computers used ones' complement and there had to be extra circuitry to fix the -0 issue. Two's complement was explicitly introduced to fix this. – So how do you explain a fix without mentioning the bug? Notably, ones' complement is easy to operate on, when reading values from blinkenlights or entering them via toggle switches, especially with octal grouping in triplets of bits. Which isn't that true for two's complement representation, as it is less intuitive (and digit positions shift with negative numbers). And the introduction of two's complement roughly coincides with operator consoles and switches becoming less important. (It's true, if two's complement does work, you must be able to express and generalize this in terms of number theory, but this doesn't mean that it really stands on its own feet in terms of raison d'être.) Regarding the sign-bit, this is an essential feature: checking the sign-bit for branching (or skipping) is the most basic approach to Turing complete computing. (Turing, the man himself, thought it is all there should be.) And it's also an essential bridge between numeric and logic computing, e.g., when we shift or rotate a bit vector to inspect the bit now in sign position.
  - Animats 3y ago
    There's also signed-magnitude, which Burroughs used. Burroughs even had a unified floating point and integer representation. 48-bit floats had a sign, an exponent sign, an exponent, and a mantissa. The binary point was at the low end of the mantissa, and if both inputs had a zero exponent and the result could be represented with a zero exponent, it would be. No need for a float/integer distinction in programs.
Someone 3y ago
> There's also the notable feature of the most significant bit, which, if excluded from the usable range of numbers, becomes the sign-bit. If it is empty (clear), it must be a positive number, if it's set, we have a negative number (since it must be a clear bit flipped) There also is the problematic feature that, according to that logic, zero is a positive number :-) > Can we do something about this? Namely, can we get rid of negative zero? Well, as we've seen, we have an extra step on the negative side of things… what about just adding 1 to compensate for this? So, for -1, we wouldn't write 1110 (flipping all bits of 0001), but 1111? Just the same, for -2, we would add 1 to 1101, making this 1110, and so on. – Well, this works! we just eliminated negative zero! Welcome to two's complement. I think that the “flip all the bits, add one” method to flip the sign in such a number came after the idea of using that mapping between numbers and bit patterns. I’m thinking that because the mapping naturally comes from the observation that unsigned n-bit integers do math modulo 2^n, and that, thus, the all-ones pattern stands for {(2^n 1) + k 2^n | k ∈ ℤ} ⇒ it’s an arbitrary choice whether to pick 2^n-1 and -1 as representatives of that set. ⇒ the hardware for implementing addition, subtraction and multiplication can be 100% identical, whatever representatives you pick for those numbers. One thing this loses compared to the ones’ complement is that it is harder to flip the sign of a number. However, it isn’t hard to discover the “flip all the bits, add one” method. A thing that it doesn’t really lose is that this encoding has a ‘weird’ number. To flip the sign of 1000…000, you compute 0111…111 + 1, which is 1000…000, so in some sense, that’s a second number that is its own negative in this encoding. That isn’t much different from two’s complement. It has two zeroes, this has one zero and another number that’s equal to its own negation.
- masswerk 3y ago
  I think, it may be worth keeping in mind how important it was to have an intuitively accessible representation in the era of console lights and toggle switches. Ones' complement and octal grouping (it's easy to interpret a triplet of bits) did this. – And subtraction was just addition with one of the operands inverted. On the other hand, you had to compensate for this by adding extra circuitry to handle transitions across zero (i.e., a change of the sign-bit occurring in additions or subtractions), and checking for -0 in code as well. As operator consoles became less important, this became less worth the effort and we transitioned. (Mind how the connection between octal digit positions and bits is lost in two's complement. This would have been a major issue.)
bsder 3y ago
The problem on computers is that "one's complement" needs "end around carry" which makes your adds take twice as long.
- masswerk 3y ago
  I think, it wasn't so much for speed as for then expensive extra circuitry. (On the few vintage instruction sets using ones' complement, I know, addition and subtraction still executes in the same time as any other internal ALU instruction. Then, cycle times were still mostly owed to slow core memory cycles and the fasted you'd ever get was a single memory cycle.)

omnicognate 3y ago

The apostrophe placement is significant: it's two's complement (complement of two) but ones' complement (complement of ones, plural).

masswerk 3y ago
Fixed. (I will do this error anytime.)
jodrellblank 3y ago
Thanks! I wonder if instead of ones’ and two’s we could use more distinct names like the Boolean values, trues’ and two’s… oh that isn’t better.

munchler 3y ago

Agreed. A crucial benefit of two’s complement is that it eliminates the distinction between +0 and -0.

nayuki 3y ago

> So, is it now perfect? Well, sort of. We now have introduced a certain asymmetry into our number system I think some systems use the INT_MIN bit pattern as a sort of not-a-number integer trap?

masswerk 3y ago
I think, it's more an aesthetic than a technical annoyance. But, since there was ones' compliment first (implemented in about every early computer), it may be worth mentioning that there was something lost, as well. (So, for a byte, the range is now -128…+127, which isn't that pretty, while it had been -127…+127 with ones' complement.) You may be right about NaN representation, but I don't know for certain. Notably, negative zero lived on in scientific computing, and you can have it even in JS, if you set the language version to "1.2". (Edit/Correction: setting the type to "javascript1.2" no longer works, all versions are now synonymous with just plain "javascript".)

FullstakBlogger 3y ago

Why does starting with ones' compliment make things easier? IMV, it makes it more confusing, because two's compliment seems like an arbitrary leap that happens to work. If you're tasked with mapping a subset of bit-states to negative numbers, it's intuitively obvious that there's already a state that yields 0 when you add 1 to it, as long as you wrap on overflow. With four bits that's 1111. That's a great representation of -1. If you want to get 0 by adding 2, you'd have to start from 1110, and so on. Just because the top bit can be used to identify a negative number when you use up half the states, doesn't mean it should be thought of as a logical flag. That's how you invent ones' compliment. I think of ones' compliment as a logical encoding, and two's compliment as an arithmetic encoding, and it shows in how easy negation is in ones' compliment, and how easy arithmetic is in two's compliment. The fact that everyone tries to teach them as if one is a precursor to the other is what's confusing.

masswerk 3y ago
It's really, because it's were we came from. Early computers used ones' complement and there had to be extra circuitry to fix the -0 issue. Two's complement was explicitly introduced to fix this. – So how do you explain a fix without mentioning the bug? Notably, ones' complement is easy to operate on, when reading values from blinkenlights or entering them via toggle switches, especially with octal grouping in triplets of bits. Which isn't that true for two's complement representation, as it is less intuitive (and digit positions shift with negative numbers). And the introduction of two's complement roughly coincides with operator consoles and switches becoming less important. (It's true, if two's complement does work, you must be able to express and generalize this in terms of number theory, but this doesn't mean that it really stands on its own feet in terms of raison d'être.) Regarding the sign-bit, this is an essential feature: checking the sign-bit for branching (or skipping) is the most basic approach to Turing complete computing. (Turing, the man himself, thought it is all there should be.) And it's also an essential bridge between numeric and logic computing, e.g., when we shift or rotate a bit vector to inspect the bit now in sign position.
- Animats 3y ago
  There's also signed-magnitude, which Burroughs used. Burroughs even had a unified floating point and integer representation. 48-bit floats had a sign, an exponent sign, an exponent, and a mantissa. The binary point was at the low end of the mantissa, and if both inputs had a zero exponent and the result could be represented with a zero exponent, it would be. No need for a float/integer distinction in programs.

Someone 3y ago

> There's also the notable feature of the most significant bit, which, if excluded from the usable range of numbers, becomes the sign-bit. If it is empty (clear), it must be a positive number, if it's set, we have a negative number (since it must be a clear bit flipped) There also is the problematic feature that, according to that logic, zero is a positive number :-) > Can we do something about this? Namely, can we get rid of negative zero? Well, as we've seen, we have an extra step on the negative side of things… what about just adding 1 to compensate for this? So, for -1, we wouldn't write 1110 (flipping all bits of 0001), but 1111? Just the same, for -2, we would add 1 to 1101, making this 1110, and so on. – Well, this works! we just eliminated negative zero! Welcome to two's complement. I think that the “flip all the bits, add one” method to flip the sign in such a number came after the idea of using that mapping between numbers and bit patterns. I’m thinking that because the mapping naturally comes from the observation that unsigned n-bit integers do math modulo 2^n, and that, thus, the all-ones pattern stands for {(2^n 1) + k 2^n | k ∈ ℤ} ⇒ it’s an arbitrary choice whether to pick 2^n-1 and -1 as representatives of that set. ⇒ the hardware for implementing addition, subtraction and multiplication can be 100% identical, whatever representatives you pick for those numbers. One thing this loses compared to the ones’ complement is that it is harder to flip the sign of a number. However, it isn’t hard to discover the “flip all the bits, add one” method. A thing that it doesn’t really lose is that this encoding has a ‘weird’ number. To flip the sign of 1000…000, you compute 0111…111 + 1, which is 1000…000, so in some sense, that’s a second number that is its own negative in this encoding. That isn’t much different from two’s complement. It has two zeroes, this has one zero and another number that’s equal to its own negation.

masswerk 3y ago
I think, it may be worth keeping in mind how important it was to have an intuitively accessible representation in the era of console lights and toggle switches. Ones' complement and octal grouping (it's easy to interpret a triplet of bits) did this. – And subtraction was just addition with one of the operands inverted. On the other hand, you had to compensate for this by adding extra circuitry to handle transitions across zero (i.e., a change of the sign-bit occurring in additions or subtractions), and checking for -0 in code as well. As operator consoles became less important, this became less worth the effort and we transitioned. (Mind how the connection between octal digit positions and bits is lost in two's complement. This would have been a major issue.)

bsder 3y ago

The problem on computers is that "one's complement" needs "end around carry" which makes your adds take twice as long.

masswerk 3y ago
I think, it wasn't so much for speed as for then expensive extra circuitry. (On the few vintage instruction sets using ones' complement, I know, addition and subtraction still executes in the same time as any other internal ALU instruction. Then, cycle times were still mostly owed to slow core memory cycles and the fasted you'd ever get was a single memory cycle.)