Please explain to me the solution for the problem below [closed]

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)

Answer 2

1. You add C[i] as well because C[i] may contain a carry bit from when you added A[i-1] + B[i-1] + C[i-1] in the previous iteration. For example if we do 1 + 1, our first iteration sum = 1 + 1 + 0 = 2, but since this is binary we have to carry the 1 and put it on C[1] and put the remainder (2 % 2 = 0) in C[0]. This gives us 10
2. C[i] gets sum % 2 because the sum of A[i] + B[i] + C[i] could be more than 1, but 1 is the most that will fit in that digit. The rest of the sum (if there is any) will be put in the carry bit. And that brings us to...
3. C[i+1] gets assigned sum / 2 because sum / 2 is the carry amount. It will be used in the next iteration when we do A[i] + B[i] + C[i] for i = i + 1.