[Introduction to Algorithms, CLRS] Exercises 2.1-4

This is a solution for Introduction to Algorithms. I write this for my study purpose.

Exercises 2.1-4

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:

- Problem:

Input: Two n-bit binary integers stored in two n-element array of binary digits (either 0 or 1) A=⟨a1,a2,...,an⟩ and B=⟨b1,b2,...,bn⟩.

Output: A (n+1)-bit binary integer stored in (n+1)-element array of binary digits (either 0 or 1) C=⟨c1,c2,...,cn+1⟩ such that C=A+B.

- Pseudocode:

BINARY-SUM(A, B, C)

1    carry = 0 

2     for i = A.length to 1  

3        C[i+1] = (carry + A[i]+B[i]) % 2

4        carry = (carry + A[i]+B[i]) / 2

5    C[1] = carry

I assumed that the least significant bit is stored in nth element in the arrays.

Cf: https://atekihcan.github.io/CLRS/E02.01-04/