Consider the problem of adding two -bit binary integers, stored in two -element arrays and . The sum of the two integers should be stored in binary form in an -element array . State the problem formally and write pseudocode for adding the two integers.

The problem can be formally stated as…

Input: Two -bit binary integers stored in two -element array of binary digits (either 0 or 1) and .

Output: A -bit binary integer stored in -element array of binary digits (either 0 or 1) such that .


Pseudocode for BINARY-ADD(A, B)

1
2
3
4
5
6
7
8
9
10
11
12
n = A.length

for i = 1 to (n + 1)
    C[i] = 0

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

Note: As we are adding number represented in binary, we have to start bit by bit addition from the least significant digit. This is reflected in line 7.

If you have any question or suggestion or you have found any error in this solution, please leave a comment below.