Please explain to me the solution for the problem below

Question

Problem:

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.

Solution:

1. C ← [1 ... n + 1] ▹ C is zero-filled.
2. for i ← 1 to n
3. do sum ← A[i] + B[i] + C[i]
4. C[i] ← sum % 2
5. C[i + 1] ← sum / 2 ▹ Integer division.
6. output C

Question:

1. I thought the C[i] is A[i]+B[i] why are you adding sum ← A[i] + B[i] + C[i] in step 3?
2. why sum % 2 (why need to use modulo in step 4?)
3. why sum / 2 (why need to use division in step 5?)

Could you please explain above solution with real example? Thanks.

Answer 1

C is both the solution and the carry. For a real example, let's add 11 + 3. I'll write in binary with decimal in parens)

A = 1011 (11) + B = 0011 (3) [C starts as 00000 (0)]
       ^               ^                      ^

The ^s mark the first position, and we go left, since we read left to right, but math goes right to left. Also, we divide integers, so 3/2 = 1, not 1.5. Now the steps.

1. sum = 1+1+0 = 10 (2), c[1] = 2 % 2 = 0, c[2] = 2/2 = 1
2. sum = 1+1+1 = 11 (3), c[2] = 3 % 2 = 1, c[3] = 3/2 = 1
3. sum = 0+0+1 = 01 (1), c[3] = 1 % 2 = 1, c[4] = 1/2 = 0
4. sum = 1+0+0 = 01 (1), c[4] = 1 % 2 = 1, c[5] = 1/2 = 0
^        ^ ^ ^                               ^
i        A B C, all at position i            note that we store the carry for the NEXT step

Result: C = 01110 (14)