Why Signed Integers Have One More Negative Number

This post started as an argument in a classroom.

My teacher told the class that in two's complement, nothing is removed from the length of the positive values. I pushed back. I said zero does not count as a positive number, so it eats a slot on the non-negative side, and that is why the positive maximum is one less than you might expect. He was not convinced, and neither was I. So I went looking for the actual mathematical reason, went back to the document where two's complement was first written down for a computer, and found that the answer is cleaner than either of us said out loud that day.

Here is the question. An N-bit signed integer has a maximum of 2^(N-1) - 1 but a minimum of -2^(N-1). For 8 bits that is +127 versus -128. Where does the "-1" on the positive side come from, and why is there no matching "-1" on the negative side?

Counting the Slots

Start from the simplest fact: an N-bit word has exactly 2^N possible patterns. Nothing more, nothing less. Two's complement splits this fixed set in half based on the most significant bit.

• Patterns starting with 1: half of everything, so 2^(N-1) patterns. Every one of these represents a strictly negative number: -1, -2, and so on down to -2^(N-1).
• Patterns starting with 0: also 2^(N-1) patterns. Every one of these represents a non-negative number: 0, 1, 2, and so on up to 2^(N-1) - 1.

Notice the word I used in the second line: non-negative, not positive. That is the entire game. The negative half contains no zero, so all 2^(N-1) of its patterns can be spent on strictly negative values. The non-negative half contains zero, and zero is not positive, so strictly positive numbers only get 2^(N-1) - 1 of the slots. Nothing is deleted from either side. The counts still add up to 2^N. It is the labeling that is asymmetric, because the two halves are equal in size, one half has no zero, and therefore the other half must spare a slot for it.

1000 0000 = -128   (-2^7, the only unpaired extreme)
0111 1111 = +127   (2^7 - 1)
0000 0000 =   0    (the slot that shrinks the positive side)

For every positive value there is a matching negative value under bit inversion and adding one, every one pairs up cleanly under addition to zero. Except -128. There is simply no positive 128, because there is no slot left for it.

The Negative Weight of the Sign Bit

Counting slots tells you why the bounds are where they are. The bit-weight view shows you the same thing mechanically, one addition at a time.

In two's complement, every bit carries its ordinary positive power of two, except the most significant bit, which carries a negative weight:

value = -a(N-1) * 2^(N-1) + a(N-2) * 2^(N-2) + ... + a(1) * 2 + a(0)

That is the whole definition. Everything else follows from it.

The most negative number is a 1 followed by all zeros. The sign bit contributes -2^(N-1) and nothing else does, so the minimum is exactly -2^(N-1). The most positive number is a 0 followed by all ones. The sign bit contributes nothing, and the remaining bits hold the geometric series 2^(N-2) + 2^(N-3) + ... + 2 + 1, which sums to 2^(N-1) - 1. Check it for 4 bits: 4 + 2 + 1 = 7, which is 2^3 - 1.

Chris Terman of MIT teaches it exactly this way in the 6.004 Computation Structures lecture videos from Spring 2017. Around the 1:18 mark of the video titled "Signed Integers: 2's complement," he says the high order bit of an N-bit two's complement number has a negative weight, derives the most negative number as -2^(N-1), and then derives the most positive as 2^(N-1) - 1, before walking through the 8-bit range of -128 to +127. He also gives a satisfying sanity check right after: all ones is the sum of the most negative and the most positive numbers, -2^(N-1) + 2^(N-1) - 1, which equals -1.

So the two explanations are the same fact from two sides. If the top bit weighs -2^(N-1), then switching it from 1 to 0 gives you at most everything below it, a series that stops one short of 2^(N-1). It stops one short because the value 0 already used one of the sign-bit-0 labels.

Where the -1 Actually Lives

If you want to see the "-1" written down in the most compact form possible, it hides in a strict inequality. In modular terms, two's complement is ordinary binary arithmetic that wraps modulo 2^N. Each pattern maps to a residue class, and by convention we pick the set of representatives running from -2^(N-1) to 2^(N-1) - 1. That upper endpoint has to stop one short because 2^(N-1) itself, as a member of the non-negative stretch starting at -2^(N-1), would need N+1 effective slots. The interval is closed on the left and open on the right, and the "-1" in the maximum is the visible trace of that open side.

Von Neumann, 1945

The first document to prescribe two's complement for a digital computer is John von Neumann's First Draft of a Report on the EDVAC, dated June 30, 1945. Section 8.1, "Treatment of the sign," on page 15, is where he sets the convention. This is the exact text:

"The extreme left digit will be reserved for the sign, so that its values 0,1 express the signs +, - respectively. If the binary point is between the digital positions i and i + 1 (from the left), then the positional value of the sign digit is 2^(i-1). Hence without the sign convention the number x would lie in the interval 0 <= x < 2^i, and with the sign convention the subinterval 0 <= x < 2^(i-1) is unaffected and corresponds to non-negative numbers, while the interval 2^(i-1) <= x < 2^i corresponds to negative numbers."

And then, a few sentences later:

"In other words: The digital sequences which we use represent, without the sign convention, the interval 0 <= x < 2^i, and with the sign convention the interval -2^(i-1) <= x < 2^(i-1). The second interval is correlated to the first one by subtracting 2^i if necessary; that is, their correspondence is modulo 2^i."

There it all is, in the founding document. The interval is -2^(i-1) <= x < 2^(i-1), with his i playing the role of our N, so the strict right edge is exactly the "-1" on the positive maximum. He calls the sign-bit-0 half "non-negative numbers," not positive ones, which is the zero-is-not-positive framing in 1945, verbatim. He even states the modulo correspondence that entire frameworks are built on today.

To be fair about what he did and did not do. He did not stop to spell out "the asymmetry exists because zero is non-positive" as an explicit argument. He set up the machinery, the negative sign digit weight, the interval bounds, the modulo relation, and the asymmetric range falls out. So cite von Neumann for the interval and the "non-negative" wording, and have your own blog do the explaining.

The 1949 EDSAC at Cambridge, directly inspired by this report, was the first operational stored-program machine to store negative binary integers in two's complement form. The rest is history: the System/360 in 1964 cemented it, and essentially every CPU since has used it.

The Verdict of the Argument

So, back to the classroom.

My teacher's statement, that nothing is removed from the length of the positive values, is literally true about pattern counts. The two halves hold 2^(N-1) patterns each and the totals sum to 2^N. Nothing is subtracted anywhere. But as an explanation of the asymmetric maximum, it does not do the job. It tells you the halves are equally full, and equally full halves cannot by themselves produce a range that ends one short on one side. If equality of full halves were the whole story, the maximum would be 2^(N-1).

My claim, that zero is not positive and therefore consumes one of the non-negative slots, is the standard and correct explanation. It is also older than either of us arguing about it, because von Neumann called that half "non-negative" in the very document that introduced two's complement to computing. Where my teacher was onto something real is the reminder that no pattern is wasted: the encoding achieves the perfect split, one unique zero, 2^(N-1) - 1 positives, and 2^(N-1) negatives. Both things are true. One of them explains the mystery, and it is the zero one.

The shortest correct version, if you ever need it under time pressure: an N-bit word holds 2^N patterns, signed interpretation splits them evenly, the negative half has no zero so it spends all its patterns on nonzero values, and the non-negative half pays exactly one pattern for zero, which leaves 2^(N-1) - 1 for the positives. The wall clock of this asymmetry is that -128 has no partner while +127 does.

Sources & References

• John von Neumann, "First Draft of a Report on the EDVAC" (1945), Section 8.1, page 15: MIT copy of the IEEE Annals edition, Internet Archive scan
• Chris Terman, "Signed Integers: 2's complement (4:34)," 6.004 Computation Structures, Spring 2017, MIT OpenCourseWare: OCW resource page
• "Two's complement," Wikipedia: Theory and History sections
• Michael D. Godfrey and D. F. Hendry, "The Computer as von Neumann Planned It," IEEE Annals of the History of Computing, 15(1), 1993: the corrected typescript used for the quoted text