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

I'm just happy that I don't need to write the loop invariant, since that seems tedious.

The formal statement:

Input: An array of booleans $A = \langle a_1, a_2, \ldots, a_n \rangle$, an array of booleans $B = \langle b_1, b_2, \ldots, b_n \rangle$, each representing an integer stored in binary format (each digit is a number, either 0 or 1, least-significant digit first) and each of length $n$.

Output: An array $C = \langle c_1, c_2, \ldots, c_{n+1} \rangle$ that such that $C' = A' + B'$, where $A'$, $B'$ and $C'$ are the integers, represented by $A$, $B$ and $C$.

Here is the pseudocode:

ADD-BINARY(A, B):
  C = new integer[A.length + 1]

  carry = 0
  for i = 1 to A.length
      C[i] = (A[i] + B[i] + carry) % 2  // remainder
      carry = (A[i] + B[i] + carry) / 2 // quotient
  C[i] = carry

  return C