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.

The problem can be formally stated as…

Input: Two $n$-bit binary integers stored in two $n$-element array of binary digits (either 0 or 1) $A = \langle a_1, a_2, . . . , a_n \rangle$ and $B = \langle b_1, b_2, . . . , b_n \rangle$.

Output: A $(n + 1)$-bit binary integer stored in $(n + 1)$-element array of binary digits (either 0 or 1) $C = \langle c_1, c_2, . . . , c_{n+1} \rangle$ such that $C = A + B$.

Pseudocode for BINARY-ADD(A, B)

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.