Cormen Edition 3 Exercise 2.1 Question 4 (Page No. 22-23)

Question

Consider the problem of adding two $n$-bit binary integers, stored in two $n$-element arrays $A$ and $B$.The sum of the two integers should be stored in binary form in an $(n+1)$-element array $C$. State the problem formally and write pseudocode for adding the two integers.

Answer 1

Let's first see in general how addition works in any base system.

Let A and B be two numbers, for any position 'i' in A and B

$Sum_{i} = (a_{i} + b_{i} + c_{i-1})$%$Base$, where $c_{i-1}$ represents carry from previous position.

$Carry_{i} = (Sum_{i} )/Base$.

So, this formula can be used to add given n-bit binary number, where base will be 2.

Time Complexity = $\mathcal{O}(N)$

Space Complexity = $\mathcal{O}(N)$, for storing the result.

n = A.length
carry = 0
for i = n to 1
    C[i] = (A[i] + B[i] + carry) % 2
    carry = (A[i] + B[i] + carry) / 2
C[i] = carry

return C