What a Computer Does to a Number
What Really Happens When a Sum Does Not Fit
Last timeA Number in a Fixed Number of Bits
Adding one to the largest value does not raise an error, it lands at the bottom of the range. Here is the carry that does it, the modulus behind it, and where it hides.
The column with no column above it
Add 1 to 127 in eight bits. Both values fit, the true answer is 128, and 128 is
outside the signed range because the largest eight bit signed value is 127. So
something has to happen, and it is worth watching it happen one column at a
time rather than being told the answer.
Written as patterns the sum is 01111111 plus 00000001. Addition proceeds from
the right, each column adding two bits and the carry from the column below, and
producing a sum bit and a carry for the column above.
| step | bit position | the two bits | carry in | sum bit | carry out | what happened |
|---|---|---|---|---|---|---|
| 1 | 0 | 1 + 1 | 0 | 0 | 1 | 1 plus 1 is 2, which is 10 in binary, so the column keeps 0 and hands 1 upwards. This is the only column where both bits are set. |
| 2 | 1 | 1 + 0 | 1 | 0 | 1 | 1 plus 0 plus the carry is 2 again. The carry survives. |
| 3 | 2 | 1 + 0 | 1 | 0 | 1 | The same again, and it will be the same up to bit 6. |
| 4 | 3 | 1 + 0 | 1 | 0 | 1 | Four columns done and every one of them has emptied itself. |
| 5 | 4 | 1 + 0 | 1 | 0 | 1 | The carry is now travelling through the value rather than being absorbed by it. |
| 6 | 5 | 1 + 0 | 1 | 0 | 1 | Nothing here is unusual: this is how 0111 plus 0001 becomes 1000 at any width. |
| 7 | 6 | 1 + 0 | 1 | 0 | 1 | The last of the seven low bits, all of which are now clear. |
| 8 | 7 | 0 + 0 | 1 | 1 | 0 | The carry arrives at the top column and stops. Both bits here are 0, so the sum bit is the carry itself, and nothing leaves the byte. |
That is the part most accounts of this skip. Two separate things can go wrong in
the top column and they are independent. A carry coming out of it means the
unsigned reading has run past 255. A carry going in without coming out, or
coming out without having gone in, means the signed reading has run past its own
ends. Processors expose these as two different condition flags for that reason,
and the signed condition is the exclusive or of the carry in and the carry out,
which was checked here against the true sum for all 65,536 ordered pairs of
eight bit signed values with no disagreement.
Both cases are real and they do not coincide. For 127 plus 1 the carry in is 1
and the carry out is 0, so the signed sum has overflowed while the unsigned
reading, 128, is perfectly fine. For 255 plus 1, which is the same bits as minus
1 plus 1, the carry in is 1 and the carry out is also 1, so the signed sum is
fine at minus 1 plus 1 equals 0 while the unsigned reading has run out. One
addition, two rules, two different verdicts.
It is not an error, it is a modulus
The carry out of the top column of a bit addition would have had the weight
. Throwing it away therefore subtracts exactly from the true answer,
and never anything else. For 255 plus 1 the true answer is 256 and the stored
answer is .
So the unsigned rule is simple to state. The stored result is the true sum
modulo , and the C standard says so directly, by defining an unsigned
result that cannot be represented to be reduced modulo one more than the largest
value the type can hold. There is no error condition to detect because, as far
as the language is concerned, nothing went wrong.
The signed rule is the same residue seen through a window in a different place.
The window runs from up to rather than from 0 up to
, so the residue has to be shifted before the modulus is taken and
shifted back afterwards.
The lesson stops here
8 more paragraphs to go
You have read the opening. The rest of the argument, the problems that check whether it landed, and the lines worth keeping at the end all come with a plan.
The first lesson of every course in the library reads the whole way through, free, so you can see exactly what the rest of them are.
See the planThe contentsThis is the reading half
Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.
The contents