🔢 Binary Arithmetic
Addition, subtraction, multiplication, and division in binary. Understanding how computers perform arithmetic at the hardware level.
Binary Addition
Binary addition follows the same principles as decimal addition but with only two digits (0 and 1). The four basic rules are: 0+0=0, 0+1=1, 1+0=1, 1+1=0 with carry 1.
Addition
1010 = 10
+ 0111 = 7
10001 = 17 (carry: 1)
Half Adder & Full Adder
Building Blocks
Half Adder
| A | B | Sum | Carry |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
Sum = A ⊕ B Carry = A · B
Full Adder
| A | B | Cin | Sum | 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 |
| 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
Sum = A⊕B⊕Cin Cout = A·B + B·Cin + Cin·A
Ripple Carry Adder
A ripple carry adder chains full adders together: the carry-out of one stage feeds the carry-in of the next. Simple but slow because carry must propagate through all stages.
4-bit Ripple Carry Adder
Carry Lookahead Adder (CLA)
Performance Improvement
For each bit position i:
- Generate: Gᵢ = Aᵢ · Bᵢ (carry is generated if both bits are 1)
- Propagate: Pᵢ = Aᵢ ⊕ Bᵢ (carry propagates if exactly one bit is 1)
- Carry: Cᵢ₊₁ = Gᵢ + Pᵢ · Cᵢ
- Sum: Sᵢ = Pᵢ ⊕ Cᵢ
CLA computes all carries in parallel in 2-3 gate delays regardless of bit width.
python
def carry_lookahead_adder(A: int, B: int, bits: int = 4):
mask = (1 << bits) - 1
G = A & B # generate
P = A ^ B # propagate
carry = 0
result = 0
for i in range(bits):
gi = (G >> i) & 1
pi = (P >> i) & 1
carry = gi | (pi & carry)
bit = ((P >> i) & 1) ^ ((carry >> 1) & 1) if i > 0 else ((P >> i) & 1) ^ 0
result |= (bit << i)
carry_out = (carry >> (bits - 1)) & 1 if bits > 0 else 0
return result & mask, carry_outBinary Multiplication & Division
Multiplication
Repeated shift-and-add: multiply by each multiplier bit, shift left, and sum partial products. n-bit × n-bit produces up to 2n-bit result.
1011 (11)
× 1101 (13)
-----
1011 (partial)
0000
1011
1011
10001111 (143)
Division
Repeated shift-and-subtract (restoring/non-restoring). Compare divisor with current remainder; if smaller, subtract and set quotient bit to 1.
1101 (13) ← quotient
-----
11)100111
-011
----
0011
-011
----
011
-011
010 (2) ← remainder
Code Example
python
def binary_add(a: str, b: str) -> str:
"""Add two binary strings, return binary result."""
result = []
i, j = len(a)-1, len(b)-1
carry = 0
while i >= 0 or j >= 0 or carry:
bit_a = int(a[i]) if i >= 0 else 0
bit_b = int(b[j]) if j >= 0 else 0
total = bit_a + bit_b + carry
result.append(str(total % 2))
carry = total // 2
i -= 1; j -= 1
return ''.join(reversed(result))
def binary_multiply(a: str, b: str) -> str:
result = "0"
n = len(b)
for i, bit in enumerate(reversed(b)):
if bit == "1":
shifted = a + "0" * i
result = binary_add(result, shifted)
return resultInterview Questions
What is the difference between a ripple carry adder and a carry lookahead adder?
A ripple carry adder chains full adders where each carry must wait for the previous stage, leading to O(n) delay. A carry lookahead adder computes generate (G=A·B) and propagate (P=A⊕B) signals in parallel, computing all carries simultaneously in O(1) delay, at the cost of more complex hardware.
How does overflow occur in binary addition and how can it be detected?
Overflow occurs when the result of addition exceeds the representable range. For signed numbers, overflow is detected when carry-in to the MSB differs from carry-out of the MSB. For unsigned numbers, overflow is detected by checking the final carry-out bit.
Explain the difference between restoring and non-restoring division.
In restoring division, if subtraction yields a negative remainder, the divisor is added back (restored). In non-restoring division, the remainder is left negative and the next step uses addition instead, making it faster since it avoids the restore step. Non-restoring is more common in hardware.