Binary Arithmetic

Every answer on this page is a function of four things: the two operands, the operation, the word width, and whether the pattern is read as signed or unsigned. A binary arithmetic result quoted without a width is incomplete, because the same thirty-two bits mean different numbers at different widths and the flags that describe the result depend entirely on where the most significant column is.

Four column rules cover every case:

• 0 + 0 = 0
• 0 + 1 = 1
• 1 + 1 = 0, carry 1
• 1 + 1 + 1 = 1, carry 1

The carry row is written above the operands, and the digit above column i is the carry into column i. Adding 00001011 (11) and 00001101 (13) gives 00011000 (24). Each column of that ripple is one full adder.

Carry out is the unsigned overflow indicator and V is the signed one. Every result on this page reports both, because a bit pattern does not know which reading you meant.

At eight bits, 0x7F + 0x01 = 0x80 gives V = 1 and C = 0: 127 + 1 is 128, which does not fit the signed range, but does fit the unsigned one. 0xFF + 0x01 = 0x00 gives C = 1 and V = 0: as unsigned values 255 + 1 overflows, while as signed values (−1) + 1 = 0 is exactly right. The rule is V = c_w ⊕ c_(w−1) — the carry into the sign column differs from the carry out of it — equivalently, both operands share a sign and the result does not.

Column by column: 0 − 0 = 0, 1 − 0 = 1, 1 − 1 = 0, and 0 − 1 = 1 with a borrow from the next column left. The borrow row runs above the operands in the same position the carry row does. Working 4 − 13 at eight bits borrows out of the most significant column, which is what the C flag reports.

A − B is A + (~B) + 1. The hardware does not have a subtractor: it has an adder, an inverter and a carry-in of 1. Working 4 − 13 this way gives the same difference as borrowing, line for line, and this tool shows both so they can be compared.

The final carry out of that addition is not part of the answer. Read plainly, a carry out of 1 means “no borrow was needed” and a carry out of 0 means “a borrow happened”. The two’s complement converter shows the complement chain in isolation.

Courses that still teach one’s complement subtract by adding the one’s-complement of B and then adding any carry out back into the least significant column — the end-around carry. It is not obsolete trivia: the same fold is what the Internet checksum does, on the parity and checksum page.

Shift and add: one partial product per multiplier bit, left-shifted by that bit’s index, then summed. 1011 × 1101 = 10001111 — 11 × 13 = 143. The rows for zero multiplier bits are shown as all zeros rather than omitted, because the shift positions are part of the method.

A w × w multiply produces a 2w-bit product. Storing it back in w bits is a separate decision, and it is where the answer is usually lost.

Shift-and-add is a rule about magnitudes, so a signed multiply needs either a sign correction or a recoding. Booth’s algorithm recodes each pair of adjacent multiplier bits into an action — 00 and 11 shift only, 10 subtracts the multiplicand, 01 adds it — and then shifts arithmetically, so runs of ones cost one subtraction and one addition instead of one addition each. (−5) × 3 traces out to −15 with two arithmetic steps.

The textbook formulation cannot take −2^(w−1) as its multiplicand, because negating it is the one negation that overflows. That is a limitation of the formulation, not a defect in the trace, and it is stated rather than hidden. The algorithm is A. D. Booth, “A Signed Binary Multiplication Technique”, Quarterly Journal of Mechanics and Applied Mathematics 4(2):236–240, 1951.

This page shows restoring division: shift a bit of the dividend into the remainder register, subtract the divisor, and if the result is negative restore the previous remainder and record a quotient bit of 0, otherwise keep it and record 1. 13 ÷ 4 gives q = 3, r = 1; 200 ÷ 7 gives q = 28, r = 4. Non-restoring division is the common variant and reaches the same quotient by a different route; it is named here so the difference is a choice rather than a surprise.

When exactly one operand is negative, two conventions disagree, and both satisfy a = q·b + r. Truncation rounds the quotient toward zero and gives a remainder with the sign of the dividend; flooring rounds toward −∞ and gives a remainder with the sign of the divisor.

Division by zero has no answer and is reported as an error rather than as a flag nobody reads. MIN ÷ −1 — −128 ÷ −1 at eight bits, or −2147483648 ÷ −1 at thirty-two — is the only signed division that overflows, because its true quotient is one past the top of the range. On x86 it raises a hardware exception rather than wrapping.

• For a division, substitute into a = q·b + r and see that it holds.
• Convert both operands to decimal with the number base converter, do the arithmetic in decimal, and compare.
• Check the least significant bit: A + B and A − B both end in the same bit as A ⊕ B, because a carry never reaches column 0.

• Most significant bit first, left to right; bits are 0-indexed from the least significant end.
• The digit above column i is the carry into column i; the carry out is displayed separately and is not part of the result.
• C is the carry or borrow out of the most significant column, V is signed overflow, N is the sign bit of the result and Z is set when the result is zero.
• Borrow-out is reported in the x86 sense, where 1 means a borrow happened; the Arm sense is its complement.
• Division truncates toward zero by default, and the convention is named.

Positional arithmetic is stated here without attribution, which is the honest treatment: attributing “1 + 1 = 10” would be noise. The one named result is Booth’s recoding — A. D. Booth, “A Signed Binary Multiplication Technique” (opens in a new tab), Quarterly Journal of Mechanics and Applied Mathematics 4(2):236–240, 1951.