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.

Input: An array of booleans \(A = \langle a_1, a_2, ..., a_n \rangle\) and an array of booleans \(B = \langle b_1, b_2, ..., b_n \rangle\), each representing an integer stored in binary format.

Output: An array of booleans \(C = \langle c_1, c_2, ..., c_n+1 \rangle\) such that \(C = A + B\).

BINARY-SUM (A, B)

1 C = new integer[A.length + 1]

2 carry = 0

3 for i = A.length to 1:

4      sum = A[i] + B[i] + carry

5      if sum <= 1:

6          C[i] = sum

7          carry = 0

8      else:

9          C[i] = sum - 2

10          carry = 1

11 C[0] = carry

12 return C