Home · part 2 of 9

From adding to subtracting

How 3 − 5 comes out as 0xFE, why that is the right answer, and how an adder subtracts without a subtractor: invert B, add 1, and read the borrow off the carry.

Width Load

Every section on this page shows the same A − B. Change it here, or tap bits in section 3.

1. A byte wraps around

A register has a fixed number of bits, so it can hold only so many patterns: 16 at 4 bits, 256 at 8. Count up past the last one and you are back at zero. Count down past zero and you are back at the last one. The patterns sit on a wheel, not a line.

Subtracting B means stepping back B places around that wheel. If the steps never pass zero, the answer is the ordinary one. If they do, the register lands on a pattern near the top of the range, and that pattern is the result. Nothing has gone wrong: the hardware did the only thing it can do.

Outermost: the four bits of each pattern. Then its unsigned reading, then its signed reading. Amber dot: A. Red dot: A − B.

The wheel also explains why the same pattern has two readings. Going round the outside, the numbers run 0 up to 15. Going round the inside, the top half has been relabelled as negatives, so 15 is −1, 14 is −2, and so on. Stepping back from 3 by 5 lands on the pattern that is 14 to one reading and −2 to the other. The circuit does not know which label you are using, and does not need to.

In C
  • For unsigned types the wheel is the law: the standard defines arithmetic as modulo 2n, so 0u − 1 is UINT_MAX by definition. That is why a loop written for (unsigned i = n − 1; i >= 0; i−−) never ends: i steps back past 0 to 4294967295 and the test stays true.
  • For signed types the standard refuses to say. Signed overflow is undefined behaviour, and compilers use that: given x + 1 > x with int x, GCC and Clang may fold it to true because the only case where it is false is one they are allowed to ignore. The hardware still wraps; the compiler just does not promise to let you see it.
  • Converting an out-of-range value to a narrower signed type, as in int8_t x = 200;, is implementation-defined, and every mainstream compiler does what the wheel does: x becomes −56.

2. Negating: NOT, then add 1

WidthNegate, as signed

Stepping back B places is the same as stepping forward by the wheel's size minus B. At 4 bits, subtracting 5 is adding 11. At 8 bits, subtracting 5 is adding 251. So if the circuit can make 16 − B, or 256 − B, from B, it can subtract with nothing but an adder.

Inverting every bit of B gives 15 − B at 4 bits (255 − B at 8), because each column that held a 1 now holds a 0 and vice versa, and all-ones is 15. Adding 1 more makes it 16 − B, exactly the number to add. That is the whole trick: −B = NOT B + 1.

Negation is a signed idea: NOT B + 1 is −B under the signed reading. Under the unsigned reading the same pattern is simply 16 − B (or 256 − B), the number you add to subtract B. Tap a bit of B to try any value. This section uses only B; A comes back in section 3.

In C: where −8 bites
  • At full width this pattern is INT_MIN, −231 for a 32-bit int. -x when x == INT_MIN is undefined behaviour, and on real hardware the same pattern comes back, so the "made positive" value is still negative.
  • abs(INT_MIN) is undefined for the same reason and in practice returns INT_MIN. Code that uses abs(a − b) as a distance can get a negative distance, which then indexes an array or passes a bounds check.
  • INT_MIN / −1 has to produce +231, which does not fit; on x86 the divide instruction raises an exception and the process dies. Dividing by a value read from input is where this surfaces.
  • A parser that reads digits as a positive number and then negates cannot parse "−2147483648", because +2147483648 never fitted. Correct parsers accumulate negatively.
  • The flag the hardware raises, V, is invisible from C. To see the case, use __builtin_sub_overflow and friends, or compile with -fsanitize=signed-integer-overflow.

3. The adder does it

Width Load

An adder already has a carry-in on bit 0. Feed NOT B into its B inputs and set that carry-in to 1, and it computes A + NOT B + 1, which is A − B. In hardware the inversion is one XOR gate per bit with a SUB wire on its other input: SUB low passes B through, SUB high inverts it and also drives the carry-in. The same adder adds and subtracts, which is why no CPU has a separate subtractor.

Tap bits in A or B to change the sum. The carries row shows the 1 entering bit 0 and the carry out leaving the top bit.

That last point is where the carry flag comes from. If a carry comes out of the top bit, the adder reached 16 (or 256) and dropped it, which cancels the 16 we added with NOT B + 1, so the result is the plain difference and no borrow happened. If no carry comes out, the 16 is still in there: the result wrapped, because B was bigger than A. ARM and most other designs store this carry out as C, so after a subtraction C = 1 means no borrow, C = 0 means a borrow. x86 stores the opposite and calls it the borrow flag, but the circuit is the same.

In C
  • C has no way to read the carry flag. The idiom for "did this unsigned subtraction borrow" is to compare afterwards: if (a − b > a) is true exactly when the subtraction wrapped, because an answer larger than what you started from can only come from going round the wheel.
  • The same trick for addition is if (a + b < a). Both are only valid for unsigned operands, where the wrap is defined; for signed operands the comparison itself may be optimised away.
  • Modern compilers expose the flags indirectly: __builtin_add_overflow(a, b, &r) returns whether the result fitted, and compiles to the add plus a test of C or V depending on the types.

4. Doing it on paper

You do not have to think in bits to get the right pattern. Work in decimal, then fit the answer into the width, then convert with the top bit worth minus its place value. The adder above and this method always agree, because both are arithmetic on a wheel of 2n patterns; the method just does the wrap as one explicit step. Two cases at 4 bits, one that fits and one that does not:

And the same three steps for whichever A − B is loaded, read as signed. Load 7 − (−1) or 0x80 − 1 for more wraps.

Width Load

On the number line, the grey band above the axis is the signed range and the amber band below it the unsigned range; the ticks mark their ends. The black dot is the true decimal answer; an arrow shows the shift of one wheel size when the answer has to be fitted. Both landings are the same bits.

In C
  • Step 2 is exactly what C promises for unsigned arithmetic: the result is reduced modulo 2n, every time, portably.
  • For signed arithmetic C promises nothing when step 2 would have to act. The hardware does the reduction anyway, so you will usually observe it, but the compiler may have assumed it cannot happen and rearranged your code first. -fwrapv tells GCC and Clang to make the wrap a promise.
  • Step 3, reading the pattern with the top bit worth minus its place value, is what every C compiler and debugger does when it prints a signed value. Printing the same variable with %u instead of %d is choosing the other reading of the same bits.

Where this leads