Return the result of subtraction of character arrays in C++

Question

I'm trying to subtract strings where each ASCII character is treated as a decimal digit. For instance:

"1000000000001" - "0100000000001" = "900000000000"

How would I get started on an implementation of this if my function prototype looked like:

char* get_sub(char* a, char* b)

Answer 1

Just remember how you learned to do subtraction of large numbers in your Algorithms 001 class, the primary school. Subtract the least significant digits of both numbers, add 10 if smaller than 0, remember carry, go on to next digit pair.

Answer 2

It doesn't seems, but it's a quite complex problem (unless I'm getting too much old). This works only in N. So it must be true that a >= 0, b >= 0, a >= b. I won't explain how does it works. As I've written, it's quite complex :-) (and I'm not even happy of what I've written. I'm sure there is something I haven't thought)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* get_sub(const char* a, const char* b);

#define MAX(a, b) (((a) > (b)) ? (a) : (b))

int main(int argc, char* argv[])
{
    char *res = get_sub("10000","9999");
    printf("%s\n", res);
    free(res);
    return 0;
}

char* get_sub(const char* a, const char* b)
{
    size_t a1len = strlen(a);
    size_t a2len = strlen(b);

    size_t max = MAX(a1len, a2len);

    /* I'm using calloc to make it easier to debug. You could use malloc, but you'll have to uncomment a line below */
    char *res = (char*)calloc(max + 1, sizeof(char));

    int carry = 0;

    char *pres = res;
    for (const char *pa = a + a1len - 1, *pb = b + a2len - 1; pa >= a || pb >= b; pa--, pb--, pres++)
    {
        int val1 = pa >= a ? (*pa - '0') : 0;
        int val2 = pb >= b ? (*pb - '0') : 0;

        int diff = val1 - carry - val2;

        if (diff >= 0)
        {
            *pres = (char)(diff + '0');
            carry = 0;
        }
        else
        {
            *pres = (char)(10 + diff + '0');
            carry = 1;
        }
    }

    if (carry != 0)
    {
        free(res);
        return (char*)calloc(1, 1);
    }

    /* *pres = '\0'; */ /* Uncomment this line to use malloc */

    pres--;

    while (pres > res && *pres == '0')
    {
        *pres = '\0';
        pres--;
    }

    strrev(res);

    return res;
}

Answer 3

Taking the least significant digit of a and b, convert them to an integer by subtracting the value of the character '0'. (Some will correctly state that this is not portable, to which I say get back to me when you have found a practical system in modern use on which this will not work!). If the a digit is less than the b digit, add 10 to the a digit, set a "borrow flag", and subtract the a digit from the b digit. This value is the least significant digit of the answer.

Move to the next least significant digit, if the borrow flag is set, subtract 1 from the a digit, and clear the borrow flag, then repeat as above.

If one string runs out of digits before the other (i.e. is shorter), then the corresponding digit should be taken as being equal to zero.

This can be performed iteratively or recursively; I would not attempt recursion unless it has been specifically taught in the class and is therefore likely to be accepted as a solution, or even the required solution.

Answer 4

Here is a scaffold for a C++ solution, that doesn't solve the problem, but throws you some linguistic tinker-toys you'd need for a fairly straightforward implementation. It iterates backward through the digits and builds up a result which just has 1s where both numbers have nonzero digits, and 0s otherwise:

#include <string>
#include <iostream>

using namespace std;

// For a more circumspect treatment of the digit/char conversion, read up:
// http://stackoverflow.com/questions/439573/how-to-convert-a-single-char-into-an-int

char charFromDigit(int d) {
    return d + '0';
}

int digitFromChar(char c) {
    return c - '0';
}

// all this routine does is iterate backward through the digits of both
// numbers and build up a result which has a 1 digit if both numbers are
// non-zero for that place value, and a 0 digit if they're both 0

string get_something(const string& a, const string& b) {

    // get reverse ("r"begin) iterators so we can index backwards
    // across the two strings.  This way we look at the last digits
    // first

    string::const_reverse_iterator a_iterator = a.rbegin();
    string::const_reverse_iterator b_iterator = b.rbegin();

    // this variable holds the result that we build

    string result;

    // simple loop that just prints digits as long as the iterators
    // haven't indicated we're out of characters by reaching their
    // respective "r"ends...

    while (a_iterator != a.rend() || b_iterator != b.rend()) {

       int a_digit = 0;
       if (a_iterator != a.rend()) {
           a_digit = digitFromChar(*a_iterator);
           a_iterator++;
       }

       int b_digit = 0;
       if (b_iterator != b.rend()) {
           b_digit = digitFromChar(*b_iterator);
           b_iterator++;
       }

       cout << "A digit " << a_digit << ", B digit " << b_digit << endl;

       int out_digit = 0;
       if ((a_digit != 0) && (b_digit !=0))
           out_digit = 1;

       result.insert(result.begin(), charFromDigit(out_digit));
    }

    return result;
}

int main(int argc, char* argv[]) {
    string a ("1000000000001");
    string b ("0100000000001");

    cout << "A is " << a << endl;
    cout << "B is " << b << endl;

    cout << "Return Value = " << get_something(a, b) << endl;

    return 0;
}

The output of the program is:

A is 1000000000001
B is 0100000000001
A digit 1, B digit 1
A digit 0, B digit 0
A digit 0, B digit 0
A digit 0, B digit 0
A digit 0, B digit 0
A digit 0, B digit 0
A digit 0, B digit 0
A digit 0, B digit 0
A digit 0, B digit 0
A digit 0, B digit 0
A digit 0, B digit 0
A digit 0, B digit 1
A digit 1, B digit 0
Return Value = 0000000000001

Really it makes a big difference, if you're in a class, if you're solving it in the framework they're teaching you about. If everything you're learning is char* and strlen() and such, you're learning C... not idiomatic C++. In C++ you have a lot more automatic management of memory and an encouragement to use more generic algorithmic approaches.