[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.