C - Improving (really) big number addition

Question

I was lucky enough to stumble into this task during a job interview. I was gently guided to use string reversals and a few other things to speed up my process. I kept thinking that I wouldn't have done it the way I was coached. It bothered me enough that I went home and coded up my version.

How could I improve this code?

* EDIT * added a size_t for carry. Reduced the number of calles of strlen().

Rules:

• Program must be in C
• Can't use atoi, and only basic types
• Must be able to add arbitrarily large numbers
• Output must be a string

Example usage:

addbig 12345678901234567891234567891234567890123456789123456789 9876543210987654321098765432198765432109876543210987654321

Here's the code I came up with:

#include <stdio.h> // printf
#include <stdlib.h> // malloc
#include <string.h> // strlen
char * addStrings(char* string1, char* string2) {
 char *maxString = string1;
 char *minString = string2;
 // Override our larger if we were wrong.
 if (strlen(string1) < strlen(string2)) {
 maxString = string2;
 minString = string1;
 }
 int maxSize = strlen(maxString);
 // Allocate enough storage to include our carry and the null char at the end.
 char * myResult = malloc(maxSize + 2);
 // Null terminate the string
 myResult[maxSize + 1] = 0;
 size_t carry = 0;
 int mindex = strlen(minString) - 1;
 char x = 0;
 // One loop. Avoid -std=c99 flag
 int i = maxSize - 1;
 for (; i >= 0; i--) {
 // Default our char
 x = maxString[i] - '0';
 // We still have something left to add.
 if (mindex >= 0){
 x = x + (minString[mindex] - '0');
 mindex--;
 } 
 if (carry) x++;
 if (x >= 10) {
 x -= 10;
 carry = 1;
 } else {
 carry = 0;
 }
 myResult[i + 1] = x + '0';
 }
 // Take care of any leftover carry.
 if (carry) myResult[0] = '1';
 return myResult;
} // END addStrings()
int main(int argc, char **argv) {
 if (argc < 2) {
 printf("Usage: %s num1 num2\n", argv[0]);
 printf("Utility for big numbers.");
 printf("Adds num1 to num2, for any length of numbers.\n");
 return 1;
 }
 char * result = addStrings(argv[1], argv[2]);
 // Removing the initial space allocated by storage if we didn't overflow
 printf("%s\n", (result[0] == ' ') ? result + 1 : result);
 if (result) {
 free(result);
 return 0;
 }
 // Returned an error state, memory not freed.
 return -1;
}

• Pieter Witvoet: You only need 2 strlen calls, not 4.

Answer 1

Function Error

1. What is myResult[0] when carry == 0?

   if (carry) myResult[0] = '1';
   

Improvements

1. As code is not changing the the contents of the string, use const for potential compiler optimization and clarity to reviewers that code is in fact not changing the characters.

   // char * addStrings(char* string1, char* string2) 
   char * addStrings(const char* string1, const char* string2) 
   

2. Code that allocates memory should clearly say that as a comment and/or function name.

   // Returns an allocated string representing the sum of .... 
   char * addStrings(
   // or
   char * addStrings_alloc(
   

3. Really big strings can exceed length INT_MAX. Use size_t for indexing arrays and string lengths. size_t is the return type of strlen().

   // int maxSize = strlen(maxString);
   size_t maxSize = strlen(maxString);
   // int i = maxSize - 1;
   // for (; i >= 0; i--) {
   size_t i;
   for (i = maxSize; i > 0; ) {
    i--;
   

4. Check the return value of malloc()

   char * myResult = malloc(maxSize + 2);
   if (myResult == NULL) return NULL;
   

5. No need for carry to besize_t`.

   // size_t carry = 0;
   int carry = 0;
   

6. No provision for - numbers. (or ones with a leading '+')

7. No provision for trimming leads '0' in answer with input like addStrings("007", "007")

8. No provision for non-digits as in addStrings("x", "007")

9. Simplification

    // x = maxString[i] - '0';
    // if (carry) x++;
    x = maxString[i] - '0' + carry;
   

10. Below processing should have happened in the function.

     // Removing the initial space allocated by storage if we didn't overflow
     ... (result[0] == ' ') ? result + 1 : result)
    

Minor

1. Nomenclature. size is the size need for the array. length is the length of the string (not counting the null character). Suggest maxLength.

   // int maxSize = strlen(maxString);
   int maxLength = strlen(maxString);
   

2. Why the comment? Seems unneeded // Avoid -std=c99 flag

3. No provision for NULL input addStrings(NULL, "007") - but then NULL is not a valid string. For an interview question, I'd at least suggest that inputs may need sanitizing before use.

4. Style: Even single if() are easier to debug/maintain with {}

   // if (carry) myResult[0] = '1';
   if (carry) {
    myResult[0] = '1';
   }
   

5. Test driver simplification. free(NULL) is OK.

   // if (result) {
   // free(result);
   // return 0;
   //}
   free(result); 
   

6. Test driver function error - off by 1

   // if (argc < 2) {
   if (argc < 3) {
   // or better 
   if (argc != 3) {
   

7. I'd expect code to be tested and give a reasonable (or a least defined) result with addStrings("", "7") and addStrings("", "")

• MrMowgli: Seriously great response! #1 was a bug I introduced late last night after I core dumped freeing the memory allocated in the function. Apparently the pointer arithmetic loses the malloc accounting details, which is why #10 is that way. Why did you structure the size_t for loop that way?
• chux: @MrMowgli size_t is some unsigned type. size_t i = maxSize - 1; for (; i >= 0; i--) { is always true - infinite loop.
• MrMowgli: Got it. But why break out the i--?
• chux: @MrMowgli The i-- is just the first statement in the for loop. Could use for (i = maxSize; i-- > 0; ) { ... } 6.00001 or half-a-dozen of the other. It is a style issue.
• MrMowgli: Rather why not --i in the loop?

Answer 2

Malloc allocates uninitialized memory. You need to memset it unless you enjoy dealing with undefined behavior.

char * myResult = malloc(maxSize + 2);
memset(myResult, 0, maxSize + 2);

• chux: Aside from bug noted Function Error #1 the memset() is not needed. When zero filling is needed, simple to use calloc().
• David Foerster: No need to. All the requested memory is initialized later anyway.