Binary Arithmetic — Lecture Notes
INFORMATION SECURITY / COMPUTER ORGANIZATION
Unit: Digital Logic & Number Systems
Binary Arithmetic
Binary Addition · Subtraction · Representations of Binary Numbers · Arithmetic Building Blocks · Adder
· Subtractor
These lecture notes cover how numbers are represented and manipulated in binary, and the combinational logic
circuits — half/full adders and subtractors — that implement addition and subtraction at the hardware level. This
is foundational material for computer organization, cryptographic arithmetic, and understanding low-level
vulnerabilities such as integer overflow.
1. Introduction
Digital systems — including every processor, ALU, and cryptographic accelerator — perform all computation
using binary (base-2) arithmetic. Understanding how numbers are represented and how addition/subtraction are
realized in hardware is essential for:
• Designing and analysing ALUs (Arithmetic Logic Units) and CPU datapaths.
• Understanding integer overflow and underflow — a major class of software vulnerability.
• Implementing efficient arithmetic in cryptographic algorithms (modular arithmetic, RSA, AES).
• Reasoning about fixed-width register behaviour in reverse engineering and exploit development.
2. Representations of Binary Numbers
A digital word of n bits can represent numbers in several ways. The choice of representation affects how addition,
subtraction, and range are handled in hardware.
2.1 Unsigned Binary Numbers
An n-bit unsigned number represents only non-negative integers, in the range 0 to 2ⁿ − 1. Each bit position carries
a weight that is a power of 2.
Example (8-bit unsigned):
00001101₂ = 1×2³ + 1×2² + 0×2¹ + 1×2⁰ = 8 + 4 + 1 = 13₁₀
2.2 Signed Representations
To represent negative numbers, one bit (conventionally the leftmost, or Most Significant Bit — MSB) is reserved
to indicate sign. Four common schemes are used.
2.2.1 Sign-Magnitude
The MSB is the sign bit (0 = positive, 1 = negative); the remaining n−1 bits hold the magnitude.
Page 1 of 10
Binary Arithmetic — Lecture Notes
+9 (8-bit) = 0 0001001
-9 (8-bit) = 1 0001001
• Simple and intuitive, but has two representations of zero (+0 = 00000000, -0 = 10000000).
• Addition/subtraction hardware is more complex because sign and magnitude must be handled separately.
2.2.2 1's Complement
A negative number is formed by inverting (complementing) every bit of the corresponding positive number.
+9 = 00001001
-9 = 11110110 (invert every bit of +9)
• Still has two representations of zero (00000000 and 11111111).
• Subtraction is implemented via addition plus an 'end-around carry' (explained in Section 4.2).
2.2.3 2's Complement
The negative of a number is formed by inverting all bits and adding 1. This is the representation used by virtually
all modern processors.
+9 = 00001001
Invert: 11110110
Add 1: + 00000001
-9 = 11110111
• Exactly one representation of zero — arithmetic hardware is simplest.
• Range for n bits: −2ⁿ⁻¹ to +2ⁿ⁻¹ − 1 (e.g., 8-bit: −128 to +127).
• Addition and subtraction use the SAME adder circuit — this is the key hardware advantage (Section 5–6).
2.2.4 Excess-N (Biased) Representation
A fixed bias is added to every number so that all stored values are non-negative; used in floating-point exponents
(e.g., Excess-127 in IEEE-754 single precision).
Stored value = True value + Bias
Example (Excess-127): true exponent -3 → stored as -3 + 127 = 124 = 01111100
2.3 Range Comparison (n-bit word)
Zero
Representation Range
representations
Unsigned 0 to 2ⁿ − 1 1 (unique)
Sign-Magnitude −(2ⁿ⁻¹ − 1) to +(2ⁿ⁻¹ − 1) 2 (+0, −0)
1's Complement −(2ⁿ⁻¹ − 1) to +(2ⁿ⁻¹ − 1) 2 (+0, −0)
2's Complement −2ⁿ⁻¹ to +2ⁿ⁻¹ − 1 1 (unique)
Page 2 of 10
Binary Arithmetic — Lecture Notes
3. Binary Addition
3.1 Rules of Binary Addition
A B Sum Carry
0 0 0 0
0 1 1 0
1 0 1 0
1 1 0 1
Note: 1 + 1 = 10₂ — i.e., Sum = 0 with a Carry of 1 propagated to the next higher bit position, exactly like carrying
in decimal addition.
3.2 Unsigned Addition — Worked Example
1 1 1 (carries)
0 1 0 1 1 0 1 (109)
+ 0 0 1 1 0 1 1 ( 27)
-----------------
1 0 0 0 1 0 0 (136)
3.3 Signed Addition (2's Complement)
Signed numbers in 2's complement are added using ordinary binary addition; the sign bit is treated just like any
other bit. Any carry-out of the MSB is simply discarded (it is NOT added back, unlike 1's complement).
Example: (+9) + (-4), 8-bit 2's complement
+9 = 00001001
-4 = 11111100
--------------
Sum = 1 00000101 → discard carry-out → 00000101 = +5 ✓
3.4 Overflow Detection
Signed overflow occurs when the result of adding two numbers of the SAME sign produces a result of the
OPPOSITE sign — the answer no longer fits in the available bits.
• Rule: Overflow = Carry into the sign bit XOR Carry out of the sign bit.
• Overflow can only occur when adding two positives or two negatives; adding numbers of opposite sign can
never overflow.
Example (4-bit, range -8..+7): (+5) + (+4)
0101
+ 0100
------
1001 = -7 in 2's complement → WRONG (expected +9)
Carry into sign bit = 1, carry out of sign bit = 0 → XOR = 1 → OVERFLOW
Note: Integer overflow of exactly this kind is a common root cause of security bugs — e.g., a signed length
calculation wrapping to a negative value and bypassing a bounds check.
Page 3 of 10
Binary Arithmetic — Lecture Notes
4. Binary Subtraction
4.1 Direct Subtraction (Borrow Method)
A B Difference Borrow
0 0 0 0
0 1 1 1
1 0 1 0
1 1 0 0
This mirrors pencil-and-paper decimal subtraction: when A = 0 and B = 1, we borrow 1 from the next higher
column (equivalent to 10₂ − 1 = 1).
1 1 0 1 0 1 (53)
- 0 1 1 0 1 1 (27)
--------------
0 1 1 0 1 0 (26)
Note: Direct borrow subtraction requires separate hardware from addition, which is why 1's/2's complement
methods (below) are preferred in digital design — they reuse the same adder circuit.
4.2 Subtraction Using 1's Complement
To compute A − B: take the 1's complement of B, add it to A, then if there is an end-around carry (a carry out of
the MSB), add that carry back into the LSB of the result.
Example: 1010 (10) - 0011 (3), 4-bit
1's complement of 0011 = 1100
1010
+ 1100
------
10110 → end-around carry = 1
0110 + 1 (carry) = 0111 = 7 ✓
Note: If there is NO end-around carry, the result is negative and is itself in 1's-complement form — it must be re-
complemented to read its magnitude.
4.3 Subtraction Using 2's Complement
To compute A − B: take the 2's complement of B (invert and add 1), then add to A. Any carry out of the MSB is
simply discarded (unlike 1's complement, it is NOT added back).
Example: 1010 (10) - 0011 (3), 4-bit
2's complement of 0011: invert → 1100, +1 → 1101
1010
+ 1101
------
10111 → discard carry → 0111 = 7 ✓
Example: 0011 (3) - 1010 (10), 4-bit — result is negative
2's complement of 1010: invert → 0101, +1 → 0110
Page 4 of 10
Binary Arithmetic — Lecture Notes
0011
+ 0110
------
1001 (no carry out → result is negative, already in 2's complement)
Magnitude: invert 1001 → 0110, +1 → 0111 = 7 → result = -7 ✓
Note: This 'complement-and-add' technique is precisely why every modern ALU implements subtraction as A + (̄B +
1) using the same binary adder as addition — see Section 6.3.
4.4 Summary: Choosing a Subtraction Method
Method Extra hardware needed Used in practice?
Separate subtractor
Direct borrow Rare in CPUs
circuit
1's complement + end- Complementer + extra add
Legacy systems
around carry cycle
2's complement (add Complementer + reuse of Standard in modern
negative) adder CPUs
5. Arithmetic Building Blocks: Adders
Addition circuits are built from two fundamental combinational building blocks: the Half Adder and the Full
Adder. Cascading these produces multi-bit adders used inside every ALU.
5.1 Half Adder (HA)
A Half Adder adds two single bits, A and B, producing a Sum and a Carry. It cannot accept a carry-in from a
previous stage — hence 'half'.
A B Sum (S) Carry (C)
0 0 0 0
0 1 1 0
1 0 1 0
1 1 0 1
Boolean expressions:
Sum S = A ⊕ B (XOR gate)
Carry C = A · B (AND gate)
Logic diagram:
Page 5 of 10
Binary Arithmetic — Lecture Notes
Note: A Half Adder uses exactly one XOR gate and one AND gate — the minimum hardware needed to add two bits
without carry-in.
5.2 Full Adder (FA)
A Full Adder adds three bits: the two operand bits A and B, plus a Carry-in (Cin) from the previous (lower-order)
stage. It produces a Sum and a Carry-out (Cout). Full adders are what make multi-bit addition possible.
A B Cin Sum (S) Cout
0 0 0 0 0
0 0 1 1 0
0 1 0 1 0
0 1 1 0 1
1 0 0 1 0
1 0 1 0 1
Page 6 of 10
Binary Arithmetic — Lecture Notes
A B Cin Sum (S) Cout
1 1 0 0 1
1 1 1 1 1
Boolean expressions:
Sum S = A ⊕ B ⊕ Cin
Carry Cout = A·B + Cin·(A ⊕ B) = A·B + B·Cin + A·Cin
5.2.1 Full Adder Built From Two Half Adders
A Full Adder is commonly implemented by cascading two Half Adders and one OR gate:
• HA1 adds A and B, producing an intermediate Sum (S1) and Carry (C1).
• HA2 adds S1 and Cin, producing the final Sum (S) and a second Carry (C2).
• Cout = C1 OR C2 — a carry is generated if EITHER half-adder stage produced one.
5.3 Ripple Carry Adder (Multi-bit Addition)
To add n-bit numbers, n Full Adders are chained together: the Carry-out of each stage feeds the Carry-in of the
next, more-significant stage. This is called a Ripple Carry Adder because the carry 'ripples' through the chain.
• The bit-0 (least significant) stage typically uses a Half Adder (no carry-in) OR a Full Adder with Cin
permanently tied to 0.
• Drawback: propagation delay grows linearly with word length, since each stage must wait for the previous
stage's carry.
• Faster alternatives used in real CPUs include Carry-Look-Ahead Adders and Carry-Select Adders, which
compute carries in parallel to reduce delay.
6. Arithmetic Building Blocks: Subtractors
Page 7 of 10
Binary Arithmetic — Lecture Notes
6.1 Half Subtractor (HS)
A Half Subtractor computes A − B for single bits, producing a Difference and a Borrow. It cannot accept a
borrow-in — hence 'half'.
Difference
A B Borrow (Bo)
(D)
0 0 0 0
0 1 1 1
1 0 1 0
1 1 0 0
Difference D = A ⊕ B (XOR gate)
Borrow Bo = ̄
A · B (NOT-A AND B)
6.2 Full Subtractor (FS)
A Full Subtractor computes A − B − Bin, where Bin is a Borrow-in from the previous (lower-order) stage. It
produces a Difference and a Borrow-out (Bout).
A B Bin Diff (D) Bout
0 0 0 0 0
0 0 1 1 1
0 1 0 1 1
0 1 1 0 1
1 0 0 1 0
1 0 1 0 0
1 1 0 0 0
1 1 1 1 1
Difference D = A ⊕ B ⊕ Bin
Borrow-out Bout = ̄
A·B + ̄
A·Bin + B·Bin = ̄
A·B + Bin·(A ⊕ B)̅̅̅̅̅̅̅(equiv. form: ̄
A·B +
(̄
A⊕B)... simplified below)
Note: Common simplified form: Bout = ̄A·B + Bin·̄(A ⊕ B) — a full subtractor can also be built from two half
subtractors plus an OR gate, mirroring the full-adder-from-half-adders construction in Section 5.2.1.
6.3 Building a Subtractor From an Adder (2's Complement Method)
Rather than building separate subtractor hardware, real ALUs compute A − B by feeding A and the 2's
complement of B into a standard binary adder — reusing the exact same Full Adder chain used for addition
(Section 5.3).
This is achieved with one control line, M (Mode: 0 = add, 1 = subtract), connected as follows:
Page 8 of 10
Binary Arithmetic — Lecture Notes
• Each bit of B is passed through an XOR gate together with M: Bi ⊕ M. When M = 0, this passes B
unchanged. When M = 1, this inverts every bit of B (the first step of 2's complementing it).
• M is also fed into the Carry-in (Cin) of the very first (least-significant) Full Adder stage. Setting Cin = 1
adds the '+1' needed to complete the 2's complement.
• Result: when M = 0, the circuit computes A + B. When M = 1, the circuit computes A + ̄B + 1 = A − B.
M ──────────────┬───────────────────── Cin (of LSB Full Adder)
│
B3 ──[XOR]── B3⊕M │
B2 ──[XOR]── B2⊕M ┌──────┘ (M fans out to every XOR gate
B1 ──[XOR]── B1⊕M │ AND the carry-in of stage 0)
B0 ──[XOR]── B0⊕M ──┘
A3,(B3⊕M) → FA3 → S3 A1,(B1⊕M) → FA1 → S1
A2,(B2⊕M) → FA2 → S2 A0,(B0⊕M) → FA0 → S0 (Cin = M)
Note: This single elegant trick — one XOR per bit plus tying the carry-in to the mode line — is why one piece of
hardware (the adder) implements BOTH addition and subtraction in every modern ALU, and is the standard exam
diagram for 'Adder-Subtractor circuit'.
7. Quick-Reference Summary
Concept Key formula / rule
Half Adder S = A⊕B, C = A·B
Full Adder S = A⊕B⊕Cin, Cout = AB + BCin + ACin
Half Subtractor D = A⊕B, Bo = ̄
A·B
Full Subtractor D = A⊕B⊕Bin, Bout = ̄
A·B + Bin·̄
(A⊕B)
2's complement of B invert all bits, then add 1
Subtraction via adder A − B = A + ̄
B + 1
Carry-in to sign bit ⊕ Carry-out of sign
Signed overflow test
bit
8. Practice Questions
• 1. Represent −45 in 8-bit sign-magnitude, 1's complement, and 2's complement.
• 2. Add (+37) and (−58) using 8-bit 2's complement arithmetic and verify the result.
• 3. Perform 01001 − 01111 using both the borrow method and the 2's complement method; confirm the
results agree.
• 4. Draw and label the logic diagram of a Full Adder built from two Half Adders and an OR gate.
• 5. Derive the Boolean expression for Bout of a Full Subtractor from its truth table using a Karnaugh map.
• 6. Explain, with a circuit diagram, how a 4-bit adder is converted into a 4-bit adder-subtractor using XOR
gates and a mode control line M.
Page 9 of 10
Binary Arithmetic — Lecture Notes
• 7. For 4-bit signed addition of (+6) and (+5), show the bit-level addition and demonstrate the overflow-
detection rule.
Page 10 of 10