CLRS 3e 2.1-4

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.

A = n bit binary array

B = n bit binary array

C= n+1 bit binary array

1:        sum=0  
2:        for i = 1 to n   
3:           sum = sum+A[i] + B[i]   
4:           C[i]=sum%2  
5:           sum=sum/2  
6:        C[n+1]=sum  

The way we do overflows with integers is using the base 10.  Modulo by 10 gives the last digit after adding.  Division by 10 gives the carry over.  For binary numbers, the same applies with base 2.

If we add 2 binary numbers A = 11 (number 3) and B = 11 (number 3) we get C = 110 (number 6)