Algebra of Binary Numbers

At a Glance

• Frequency: 2 sub-parts across 1 of 13 years (2023)
• Priority tier: T4
• Marks (count): 10 (2)
• Average solve time: ~10 min per sub-part
• Difficulty mix: medium 2
• Section: A | Dominant type: computation

Why This Chapter Matters

Binary arithmetic is mechanical once the rules are memorised, but UPSC rewards clear column-by-column working and explicit carry notation. The 2023 paper set two sub-parts — one on addition/subtraction and one on 2’s complement — so both archetypes are tested. These are quick marks if prepared, but errors cascade without careful carry tracking.

Minimum Theory

Binary digit (bit) values. A number written in base 2 uses only digits 0 and 1. The positional value of bit $k$ (counting from the right, starting at 0) is $2^k$.

Binary addition rules.

$0+0=0,\quad 0+1=1,\quad 1+0=1,\quad 1+1=10_2 \text{ (sum 0, carry 1)},\quad 1+1+1=11_2 \text{ (sum 1, carry 1)}$

Work right to left; propagate the carry into the next column.

Binary subtraction. Compute $A - B$ by either:

• Direct borrowing (analogous to decimal), or
• Adding the 2’s complement of $B$ to $A$ (preferred in digital hardware).

1’s complement. Flip every bit: $\overline{1011} = 0100$.

2’s complement. $-N$ in 2’s complement $= \overline{N} + 1$ (1’s complement plus 1). Equivalently, leave all trailing zeros and the rightmost 1 unchanged; flip all bits to the left of that rightmost 1.

Range of $n$-bit 2’s complement. $-2^{n-1}$ to $2^{n-1}-1$.

Binary multiplication. Shift-and-add: for each bit of the multiplier, if the bit is 1 write a shifted copy of the multiplicand; if 0 write zeros. Sum all partial products.

Binary division. Long division in base 2: at each step, check whether the divisor fits into the current partial dividend (quotient bit 1 if yes, 0 if no); subtract and bring down the next bit.

XOR (exclusive OR). $A \oplus B = 1$ iff $A \ne B$. Used in half-adder carry-free sum: the sum bit of $A+B$ is $A \oplus B$, the carry bit is $A \cdot B$.

Question Archetypes

binary-addition (sub-part; 2023)

Recognition Cues

• “Add the following binary numbers” or “perform binary addition.”
• Two or more binary strings of equal or unequal length.

Solution Template

1. Align numbers on the right, padding shorter number with leading zeros.
2. Add column by column from right to left, tracking carry.
3. Write the carry row explicitly above the sum row.
4. State the result and, if asked, convert to decimal to verify.

Worked Example

2023 Paper 2, 2023-P2-Q7a (5 marks)

Perform binary addition: $10110101_2 + 01101110_2$.

Arrange the numbers and add column by column (carries shown above):

  Carry:  1 1 1 1 1 1 0 0
          1 0 1 1 0 1 0 1
        + 0 1 1 0 1 1 1 0
          -----------------
        1 0 0 1 0 0 0 1 1

Detailed column trace (right to left):

• Col 0: $1+0=1$; carry 0.
• Col 1: $0+1=1$; carry 0.
• Col 2: $1+1=10$; write 0, carry 1.
• Col 3: $0+1+1(\text{carry})=10$; write 0, carry 1.
• Col 4: $1+0+1=10$; write 0, carry 1.
• Col 5: $1+1+1=11$; write 1, carry 1.
• Col 6: $0+1+1=10$; write 0, carry 1.
• Col 7: $1+0+1=10$; write 0, carry 1.
• Col 8 (overflow): carry 1 → write 1.

Result: $100100011_2$.

Verification. $10110101_2 = 181_{10}$, $01101110_2 = 110_{10}$, sum $= 291_{10} = 100100011_2$ ✓.

$\boxed{10110101_2 + 01101110_2 = 100100011_2}$

twos-complement-subtraction (sub-part; 2023)

Recognition Cues

• “Subtract using 2’s complement” or “represent $-N$ in 2’s complement.”
• A statement about $n$-bit signed representation.

Solution Template

1. Write both numbers in $n$-bit binary (choose $n$ large enough to hold both and a sign bit).
2. Find 2’s complement of the subtrahend: flip all bits, add 1.
3. Add the minuend to the 2’s complement of the subtrahend.
4. If there is a carry out of the most significant bit, discard it — the result is positive.
5. If there is no carry out and the MSB of the result is 1, the result is negative; take its 2’s complement to find the magnitude.

Worked Example

2023 Paper 2, 2023-P2-Q7b (5 marks)

Using 8-bit 2’s complement arithmetic, subtract $45_{10}$ from $73_{10}$, i.e., compute $73 - 45$.

Step 1 — convert to 8-bit binary.

$73_{10} = 01001001_2, \quad 45_{10} = 00101101_2$

Step 2 — 2’s complement of $45_{10}$.

1’s complement of $00101101$: flip every bit $\to 11010010$.

Add 1: $11010010 + 1 = 11010011$.

So $-45$ in 8-bit 2’s complement is $11010011_2$.

Step 3 — add $73$ and $(-45)$.

  Carry:  0 1 0 0 1 0 0 1
          0 1 0 0 1 0 0 1   (73)
        + 1 1 0 1 0 0 1 1   (2's complement of 45)
          -----------------
        1 0 0 0 1 1 1 0 0

Result bits (8 bits): $00011100_2$; carry out of bit 7 = 1, discarded.

Step 4 — interpret.

Carry out exists $\Rightarrow$ result is positive. $00011100_2 = 28_{10}$.

Verification. $73 - 45 = 28$ ✓.

$\boxed{73_{10} - 45_{10} = 00011100_2 = 28_{10}}$

Common Traps

• Adding 1 to the 1’s complement incorrectly — carry must be propagated all the way through, not stopped at the first 0.
• Not choosing a wide enough $n$: always ensure both numbers fit in $n-1$ bits (the $n$-th bit is the sign bit).
• Forgetting to discard the final carry — in fixed-width 2’s complement arithmetic, the carry out of the MSB is not a separate bit; discarding it is the correct procedure for positive results.
• In binary addition, writing the carry incorrectly in the $1+1+1$ case: the sum bit is 1 and the carry is 1 (giving $11_2 = 3_{10}$).

Marks-Aware Writing

Each 5-mark sub-part expects: the setup (numbers aligned, conversion if needed), explicit column-by-column working for addition, and a decimal verification. For 2’s complement: show the 1’s complement step and the add-1 step separately — they are two distinct operations and each earns marks. Combining them without showing intermediate work loses the method marks.

Practice Set

Only one historical paper set these sub-parts (2023), both shown above.