HiveBrain v1.2.0
Get Started
← Back to all entries
patterncMinor

C - Improving (really) big number addition

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
codereviewcstackoverflow
numberreallyadditionbigimproving

Problem

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    // printf
#include   // malloc
#include   // strlen

char * addStrings(char* string1, char* string2) {
  char *maxString = string1;
  char *minString = string2;

  // Override our larger if we were wrong.
  if (strlen(string1) = 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;
}

Solution

Function Error

-
What is myResult[0] when carry == 0?

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


Improvements

-
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)


-
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(


-
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--;


-
Check the return value of malloc()

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


-
No need for carry to besize_t.

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


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

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

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

-
Simplification

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


-
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

-
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);


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

-
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.

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

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


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

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


-
Test driver function error - off by 1

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


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

Code Snippets

if (carry) myResult[0] = '1';
// char * addStrings(char* string1, char* string2) 
char * addStrings(const char* string1, const char* string2)
// Returns an allocated string representing the sum of .... 
char * addStrings(
// or
char * addStrings_alloc(
// 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--;
char * myResult = malloc(maxSize + 2);
if (myResult == NULL) return NULL;

Context

StackExchange Code Review Q#128165, answer score: 2

Revisions (0)

No revisions yet.