31. Addition in different number systems – solution

Explanation of the task: a number is written with digits, and every digit is multiplied by a power of the base Q. For example, in the decimal system (Q = 10):

357 = 3*100 + 5*10 + 7*1
    = 3*10² + 5*10¹ + 7*10⁰
    = 3*Q² + 5*Q¹ + 7*Q⁰,   where Q = 10 is the base,
                             and 3, 5 and 7 are the coefficients (digits)
If Q != 10, then it is some other number system, not the decimal one.
If Q = 2, it is the BINARY number system, which has only the digits 0 and 1.
If Q = 8, it is the OCTAL system, with the digits 0 to 7. For example, the number 357 in the octal system would be

357 = 3*82 + 5*81 + 7*80

Converted into the decimal number system, that would be the number

3*64 + 5*8 + 7*1 = 192 + 40 + 7 = 239

​To solve the task in which two numbers X and Y written in a given base Q have to be added,
let us look at the example when Q = 10

X = 357 = 3*102 + 5*101 + 7*100

Y = 7892 = 7*103 + 8*102 + 9*101 + 2*100

Let us look at the procedure of adding (the small numbers in the first row are the carries):

  1 1 0      ← carry
    3 5 7
+ 7 8 9 2
---------
  8 2 4 9
In the procedure we add the digits starting from the rightmost one, and then we repeat the procedure (a loop), adding the digits
that are one place further to the left.
In doing so we have a carry (carry)
​ if the sum has reached or gone over the value 10 (Q).

The algorithm of the task

  • Define the resulting number, initialized to zero.
  • In a repeated procedure, using a loop, take one digit from each of the two numbers and add them together with the carry (if there is one).
  • If that sum is smaller than 10 (Q), add it to the resulting number, and the carry becomes 0
  • If the sum is 10 (Q) or more, a new carry is taken out (1)
  • and the remainder of dividing by 10 (Q) is added to the resulting number
  • The procedure is repeated until all digits have been taken out and there is no carry left

The solution of the task

#include <stdio.h>

/* For 2 numbers X and Y written in the system with base Q (1 < Q <= 10), find their sum */
int main(void) {
    long long X, Y, S = 0;          /* S - the sum */
    int Q;
    printf("Enter the base of the system\n");
    scanf("%d", &Q);                /* example: Q=10 */
    printf("Enter X and Y\n");
    scanf("%lld %lld", &X, &Y);     /* X=357, Y=7892 */
    int carry = 0;
    long long k = 1;                /* the place value of the current digit: 1, 10, 100, ... */
    while (X > 0 || Y > 0 || carry > 0) {    /* true; true; true; true; false */
        int d1 = X % 10;            /* 7; 5; 3; 0 */
        int d2 = Y % 10;            /* 2; 9; 8; 7 */
        int c = d1 + d2 + carry;    /* 9; 14; 12; 8 */
        int digit = c % Q;          /* 9; 4; 2; 8 */
        carry = c / Q;              /* 0; 1; 1; 0 */
        S = S + k * digit;          /* 9; 49; 249; 8249 */
        X = X / 10;                 /* 35; 3; 0; 0 */
        Y = Y / 10;                 /* 789; 78; 7; 0 */
        k = 10 * k;                 /* 10; 100; 1000; 10000 */
    }
    printf("S=%lld\n", S);          /* 8249 */
    return 0;
}

For the input 10, 357 7892 the program prints S=8249. For the octal system (8, 357 7) it prints S=366, and for the binary system (2, 101 11) S=1000.

The solution of the task in the C programming language is shown above.
First the base of the number system Q is read, and then the numbers X and Y are read. The example described in the comments is for the base Q=10, but the logic is the same for any other base. 
The while loop goes through the digits of the two numbers, from the rightmost digit to the left. The digits are taken out of the numbers by finding the remainder of dividing by 10 with the operator "%" and then dividing the number by 10 (the numbers are written with ordinary digits, only their meaning depends on the base Q).
The values separated by ";" in the comments are the values that change through the iterations. In this example there are 4 iterations (the value of the condition of the while loop was true 4 times).
The carry is equal to zero at the beginning, and in the following iterations it depends on whether the sum of the digits and the carry in the current column reached the value Q. If it did, the remainder is taken out of the result (that is the digit written in the result in the current column), together with the carry for the next iteration; if it did not, the carry becomes 0. The result S is built up gradually in every iteration by adding the term k*digit, where digit is the digit and k is the place value (1, 10, 100, …) of the column in which it is written.