Binary arithmetic by hand; how many values n bits can hold

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• What is 3AF₁₆ in decimal? from Lesson 0.1.2
• How many bits make one hex digit? from Lesson 0.1.2
• What is 11010₂ in decimal? from Lesson 0.1.1

1 · The Hook

🎣

A car's odometer that shows 9999 rolls over to 0000 after one more kilometre: the "1" that should appear on the left has nowhere to go. Binary adders do the same thing. This lesson does arithmetic by hand in binary and introduces the carry out that signals "the answer didn't fit", the seed of the overflow questions in Phase 1.

2 · Predict First

🤔

What is 1 + 1 in binary? And 1 + 1 + 1?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

1 + 1 = 10₂ (write 0, carry 1). 1 + 1 + 1 = 11₂ (write 1, carry 1).

🗣️

In plain words

Binary arithmetic follows the same column method you learned at school, only you carry whenever a column reaches 2 instead of 10. Multiplying by a power of two just shifts the bits left, and dividing shifts them right.

1. Addition

Column rules: 0 + 0 = 0, 0 + 1 = 1, 1 + 1 = 0 carry 1, 1 + 1 + 1 = 1 carry 1.

1 0 1 1      (11)
 + 0 1 1 0      ( 6)
 ---------
 1 0 0 0 1      (17)   carries: 1 1 1 from right to left

2. Subtraction (with borrows)

0 − 0 = 0, 1 − 0 = 1, 1 − 1 = 0, 0 − 1 = 1 borrow 1 (borrow 2 from the next column). 1100₂ − 0101₂ = 0111₂ (12 − 5 = 7).

3. Multiplication (shift and add)

Multiply by each bit of the multiplier: a 1 copies the multiplicand (shifted), a 0 gives zeros; then add. 101₂ × 11₂ = 101 + 1010 = 1111₂ (5 × 3 = 15).

4. Shifts

• Shift left by k places = multiply by 2ᵏ: 0011₂ (3) → 1100₂ (12).
• Shift right by k places = divide by 2ᵏ, dropping the remainder: 1101₂ (13) → 0011₂ (3) for k = 2.

5. How big can results get?

• n-bit unsigned numbers: 0 … 2ⁿ − 1.
• Adding two n-bit numbers can need n + 1 bits. In a fixed n-bit adder the extra bit is the carry out; for unsigned numbers, carry out = 1 means the true sum didn't fit.
• Multiplying an n-bit number by an m-bit number can need n + m bits (8-bit × 8-bit → up to 16 bits: 255 × 255 = 65,025 < 2¹⁶).

4 · Visual

4-bit adder, unsigned:  1001 (9) + 1000 (8)

     1 0 0 1
   + 1 0 0 0
   ---------
   1 0 0 0 1      true sum 17 needs 5 bits
   ^
   carry out = 1  -> the 4-bit result 0001 (= 1) is wrong for unsigned numbers

5 · Worked Examples

Example 1 Easy

Add 1011₂ and 0110₂.

Solution

10001₂ (11 + 6 = 17).

Example 2 Medium

Compute 1100₂ − 0101₂.

Solution

0111₂ (12 − 5 = 7).

Example 3 GATE

Two 8-bit unsigned numbers are multiplied. How many bits are needed to hold every possible product?

Solution

255 × 255 = 65,025 < 65,536 = 2¹⁶ → 16 bits.

6 · GATE Traps

⚠️

• 1 + 1 is 10 (0 carry 1), never 2.
• In a fixed-width adder the carry out is lost from the result; for unsigned numbers it means the answer is too big.
• Right shift drops bits: it divides and throws away the remainder.
• n + m bits for an n × m product, not n × m bits.

7 · Memory Hook

🧠

"Carry at 2. Left shift doubles, right shift halves. Sums need one extra bit, products need n + m."

8 · Connect the Dots

Chapter 0.1 is complete: bits, bases and unsigned arithmetic. But how does a computer store negative numbers with only 0s and 1s? Phase 1 answers that with sign-magnitude, 1's complement and the system every computer uses: 2's complement.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT1 markAddition

What is 1011₂ + 0110₂, written in decimal?

Numerical answer: ________

Q2MCQ1 markSubtraction

1100₂ − 0101₂ = ?

• (A) 0111₂
• (B) 0011₂
• (C) 1001₂
• (D) 0110₂

Q3NAT1 markShift

The 8-bit pattern 00010110 is shifted left by 2 places. What is the new value in decimal?

Numerical answer: ________

Q4NAT2 marksProduct size

A 12-bit unsigned number is multiplied by a 6-bit unsigned number. Minimum number of bits that can hold every product?

Numerical answer: ________

Q5MCQ1 markCarry out

In a 4-bit unsigned adder, 1001₂ + 1000₂ gives a 4-bit result and a carry out. Which is true?

• (A) Result 1001, carry 0
• (B) Result 0001, carry 0
• (C) Result 1111, carry 1
• (D) Result 0001, carry 1: the true sum didn't fit

10 · Rule Card

• Binary column addition: carry when a column reaches 2; subtraction borrows 2.
• Multiplication: shift and add copies of the multiplicand.
• Left shift k = × 2ᵏ; right shift k = ÷ 2ᵏ (remainder dropped).
• Sum of two n-bit numbers needs up to n + 1 bits (carry out); product of n-bit and m-bit needs up to n + m bits.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

binary additioncarrybinary subtractionborrowshift-and-add multiplicationleft and right shiftscarry outunsigned overflowsize of sums and products

12 · Answer Vault