大整数计算器

作者: zhizhuwang | 来源:发表于2016-07-30 16:37 被阅读592次

需求

编程语言中内置的int类型能表示的范围是32位或者64位，有时我们需要参与运算的数，可能会远远不止32位或64位，一般我们称这种基本数据类型无法表示的整数为大整数。

我们需要实现一个程序，完成大整数的基本运算，如加法、减法、乘法和除法，其中，大整数用字符串来表示。例如：

“9999999999999999999999999999” + “-9999999999999999999999999999” = “0”

“10000000000000000000000000000” - “1” = “9999999999999999999999999”

“222222222222222” * "333333333" = "74074073999999925925926"

实例化

从分析需求开始，我们可以将大整数的计算分为加、减、乘、除，并在此过程中将需求分解为下列测试用例的列表。（除法暂没包括）

测试用例的列表不仅是对需求进行实例化的产物，同时也是我们开发过程中的路标和灯塔，指引着前进的方向。

加法：

"1" + "2" == "3";
"11" + "222" == "233";
"1" + "99" == "100";
"11" + "99" == "110";

"5" + "-3" == "2";
"5" + "-6" == "-1";
"-123" + "23" == "-100";
"-111" + "-222" == "-333";

减法

"4" - "3" == "1";
"44" - "3" == "41";
"123" - "24" = "99"
"4" - "6" == "-2"
"23" - "100" == "-77"

"45" - "-123" == "168"
"-45" - "123" == "-168"
"-45" - "-123" == "78"

乘法

"4" * "3" == "12"
"11" * "22" == "242"

"11" * "-22" == "-242"
"-11" * "22" == "-242"
"-11" * "-22" == "242"
"0" * "-22" == "0"

实现

首先从加法开始，编写测试用例。

void test_add()
{ 
    char * result = NULL;

   assert(strcmp(result = add("1","2"), "3") == 0);
   free(result);

   assert(strcmp(result = add("4","2"), "6") == 0);
   free(result);

   assert(strcmp(result = add("11","222"), "233") == 0);
   free(result);

   assert(strcmp(result = add("1","99"), "100") == 0);
   free(result);
}

按照TDD的三部军规，应该在每个失败的用例之后，编写快速的实现代码，然后重构。这里限于篇幅，无法全部展现其中的过程，对其中的部分过程进行了快进。

char digit_value(const char* str, int pos)
{
    return pos >= strlen(str) ?
            0 : *(str + strlen(str) - pos - 1) - '0';
}

digit_value函数取出一个整数中的某一位，方向从低位到高位。比如digit_value("12345", 0)取出个数的数值5.

unsigned int max_width(const char* left, const char* right)
{
    return strlen(left) > strlen(right) ? strlen(left) : strlen(right);
}

两个正整数相加，结果最大的位数为较大整数的位数（无进位），或较大的位数加1（有进位）.

char * add(const char * left, const char * right)
{
  char *result = NULL;
  int digit_pos = 0;
  unsigned int sum = 0, carry_bit = 0;
  unsigned int len = max_width(left,right);
  unsigned int max_width = len + 1;

  result = (char *)calloc(max_width + 1, sizeof(char));

  while(digit_pos < max_width)
  {
      sum = digit_value(left, digit_pos) 
               + digit_value(right, digit_pos) + carry_bit;
      result[max_width - 1 - digit_pos] = sum % 10 + '0';
      carry_bit = sum / 10;

      digit_pos++;
  }
  if(result[0] == '0')
      memmove(result, result + 1, max_width);
  result[max_width] = '\0';
  return result;

}

add函数为两个正整数相加的过程。其计算过程与小学生进行多位数的加法类似。将两数按最低位对齐，逐位相加；如果相加结果大于10，则需要进位。

下一个测试用例？

按照前面拟定的测试用例列表，现在应该实现add("5","-3")。

assert(strcmp(result = add("5","-3"), "2") == 0);
free(result);

如何快速实现呢？发现有点难以下手。

经过对正整数和负整数相加的过程进行分析之后，我们发现这个过程其实是一个减法。

即A + (-B) = A - B，其中A,B>0。

认识到这一点，果断放弃加法，转而先实现减法。

实现减法

void test_sub()
{
    char * result = NULL;
    assert(strcmp(result = sub("4","3"), "1") == 0);
    free(result);

    assert(strcmp(result = sub("44","3"), "41") == 0);
    free(result);

    assert(strcmp(result = sub("123","24"), "99") == 0);
    free(result);

}

此处略去三个测试用例的实现过程。

char * sub(const char *left, const char * right)
{
    char * result = NULL;
    int digit_pos = 0;
    unsigned int max_digit = strlen(left);
    int diff = 0, borrow_bit = 0;

    result = (char *)calloc(max_digit+1, sizeof(char));

    while(digit_pos < max_digit)
    {
        diff = digit_value(left, digit_pos) 
                - borrow_bit - digit_value(right, digit_pos);
        borrow_bit = (diff < 0 ? 1 : 0);
        result[max_digit - 1 - digit_pos] = diff + 10 * borrow_bit + '0';
        digit_pos ++;
    }
    for(digit_pos = 0; digit_pos<strlen(result); digit_pos++)
        if(result[digit_pos] != '0') break;
    memmove(result, result+digit_pos, max_digit);

    result[max_digit] = '\0';
    return result;
}

目前实现了正整数的减法，且被减数大于减数。其过程与加法的过程类似，不同之处在于，减法过程中可能需要借位。

继续实现减法，下一个测试用例是被减数小于减数的情况。

sub("5","6") == "-1";

对于小减大的情况，可以转化为大减小,然后再求负值。即A -B = -(B - A)，其中A,B>0。

将之前的sub函数重命名为subInternal，新的sub函数逻辑如下所示：

char * sub(const char *left, const char * right)
{
    if (less_than_by_abs(left, right))
        return negate(subInternal(right,left));
    else
        return subInternal(left,right);
}

其中，negate函数对一个整数求负值。

char * negate(char * s)
{
    char *result = calloc(strlen(s)+1+1, sizeof(char));
    memcpy(result+1, s, strlen(s));
    result[0] = '-';
    result[strlen(s)+1] = '\0';
    free(s);
    return result;
}

less_than_by_abs函数判断两个正整数的大小。

int less_than_by_abs(const char* left, const char* right) {
    return strlen(left) < strlen(right) ||
            (strlen(left) == strlen(right) && strcmp(left, right) < 0);
}

到这里为止，可以再转回加法，对上面没有完成的测试用例进行实现。

assert(strcmp(result = add("5","-3"), "2") == 0);
free(result);

assert(strcmp(result = add("5","-6"), "-1") == 0);
free(result);

assert(strcmp(result = add("-123","23"), "-100") == 0);
free(result);

利用刚才实现的减法，完成加法。

首先将上面实现的add函数重命名为add_internal,然后引入对整数符号的判断。新的add函数如下所示。

char * add(const char * left, const char * right)
{
    if(is_positive(left) && is_negative(right))  return sub(left, right+1);
    if(is_negative(left) && is_positive(right))  return sub(right,left+1);
    else                                         return add_internal(left, right);
}

其中的逻辑可以描述为：正+负可以转换为正-正，负-正可以转换为正+正，再取负。

int is_negative(const char * number)
{
    return *number == '-';
}
int is_positive(const char * number)
{
    return !is_negative(number);
}
unsigned int greater_than_by_abs(const char * l, const char* r)
{
    return strlen(l) > strlen(r) ||
            (strlen(l) == strlen(r) && strcmp(l, r) > 0);
}

到哪里了？

对于加法，已经实现A+B，A+(-B), (-A)+B，其中A,B>=0。还缺少两个都是负数的情况。

assert(strcmp(result = add("-111","-222"), "-333") == 0);
free(result);

经过补充和重构之后的add如下：

char * add(const char * left, const char * right)
{
    if(is_positive(left) && is_negative(right))  return sub(left, right+1);
    if(is_negative(left) && is_positive(right))  return sub(right,left+1);
    if(is_negative(left) && is_negative(right))  return negative(add(left+1, right+1));
    else                                         return add_internal(left, right);
}

每一个分支对应着一种符号组合的情况。

到目前为止，加法已经完全实现。

继续减法

assert(strcmp(result = sub("45","-123"), "168") == 0);
free(result);

对于A-(-B)，其中A,B>=0，可以转化为 A+B。

char * sub(const char *left, const char * right)
{
    if(is_positive(left) && is_negative(right))
        return add(left, right+1);
    if (less_than_by_abs(left, right))
        return negative(subInternal(right,left));
    else
      return subInternal(left,right);
}

负减正

对于(-A)-B，其中A,B>=0，可以转化为 -(A+B)。

assert(strcmp(result = sub("-45","123"), "-168") == 0);
free(result);

对应下面sub函数中第二个分支。

char * sub(const char *left, const char * right)
{
    if(is_positive(left) && is_negative(right))
        return add(left, right+1);
    if(is_negative(left) && is_positive(right))
        return negate(add(left+1, right));
    if (less_than_by_abs(left, right))
        return negate(subInternal(right,left));
    else
        return subInternal(left,right);

}

负-负

assert(strcmp(result = sub("-45","-123"), "78") == 0);
free(result);

对于|A| < |B|的情况，其结果可以转化为 B - A，也等价于 |B| - |A|.

char * sub(const char *left, const char * right)
{
    if(is_positive(left) && is_negative(right))
        return add(left, right+1);
    if(is_negative(left) && is_positive(right))
        return negate(add(left+1, right));
    if(is_negative(left) && is_negative(right))
        return sub(right+1, left+1);
    if (less_than_by_abs(left, right))
        return negate(subInternal(right,left));
    else
        return subInternal(left,right);
}

经过完善和重构的sub函数如下所示。

char * sub(const char *left, const char * right)
{
    if(is_positive(left) && is_negative(right))    return add(left, right+1);
    if(is_negative(left) && is_positive(right))    return negate( add(left+1, right));
    if(is_negative(left) && is_negative(right))    return sub(right+1, left+1);
    if(is_positive(left) && is_positive(right))
    {
        if (less_than_by_abs(left, right))    return negate( subInternal(right,left));
    }
    return subInternal(left,right);
}

至此加法和减法都已完全实现。从上面的实现可以看出，核心的计算逻辑包含在addInternal和subInternal两个函数中，其余的功能全部在此基础上通过组合完成。

乘法

void test_mul()
{
    char * result = NULL;

    assert(strcmp(result = mul("4","3"), "12") == 0);
    free(result);
}

一个简单粗暴的实现。

char * mul(const char *left, const char * right)
{
    int max_width = strlen(left) * strlen(right) + 1;
    char * result = malloc(max_width + 1);

    int a = digit_value(left,0);
    int b = digit_value(right,0);
    int product = a * b;

    if(product > 10)
    {
        result[max_width - 1] = product % 10 + '0';
        result[max_width - 2] = product /10 + '0';
    }
    result[max_width] = '\0';
    return result;
}

重构之后：

char * mul(const char *left, const char * right)
{
    char * acc = add(left,"0");
    char * p;
    int i = 1;

    for(i = 1; i<right[0] - '0'; i++)
    {
        p = add(left, acc);
        free(acc);
        acc = p;
    }  
    return acc;
}

多位数的乘法：

assert(strcmp(result = mul("11","22"), "242") == 0);
free(result);

其计算逻辑与小学生进行乘法计算类似。第二个整数的每一位分别与被乘数相乘，然后将结果左移一位（乘10），再累加到中间结果上。最终的累加值即为最后的乘积。

char * mul(const char *left, const char * right)
{
    int pos = 0;
    char * acc = add("0","0");
    char * p = NULL;
    char * p1 = NULL;
    char * p2 = NULL;

    while(pos < strlen(right))
    {
        p2 = mulByX(acc, 10);
        p1 = mulByX(left, right[pos] - '0');
        p = add(p2, p1);
        free(p1);
        free(p2);
        acc = p;
        pos++;
    }
    return acc;
}

其中的mulByX函数将一个大整数与一个单位正整数进行相乘。

char * mulByX(const char *n, int x)
{
    char * acc = add("0","0");
    char * p;
    int i = 1;

    for(i = 0; i < x; i++)
    {
        p = add(n, acc);
        free(acc);
        acc = p;
    }
    return acc;
}

正×负

其结果为两个整数相乘，再取负值。

assert(strcmp(result = mul("11","-22"), "-242") == 0);
free(result);

char * mul(const char *left, const char * right)
{
    int pos = 0;
    char * acc = add("0","0");
    char * p = NULL;
    char * p1 = NULL;
    char * p2 = NULL;

    if(is_positive(left) && is_negative(right))
    {
        return negate( mul(left, right+1));
    }
    while(pos < strlen(right))
    {
        p2 = mulByX(acc, 10);
        p1 = mulByX(left, right[pos] - '0');
        p = add(p2, p1);
        free(p1);
        free(p2);
        acc = p;
        pos++;
    }
    return acc;
}

同样地，将之前的mul重命名为mulInternal，新的mul重构之后如下所示：

char * mul(const char *left, const char * right)
{ 
    if(is_positive(left) && is_negative(right))
    {
        return negative( mul(left, right+1));
    }
    return mulInternal(left, right);
}

负×正

assert(strcmp(result = mul("-11","22"), "-242") == 0);
free(result);

与前面正×负类似。

char * mul(const char *left, const char * right)
{ 
    if(is_positive(left) && is_negative(right))
    {
        return negate( mul(left, right+1));
    }
    if(is_negative(left) && is_positive(right))
    {
        return negate( mul(left+1, right));
    }
    return mulInternal(left, right);
}

负×负

负负相乘等于正。

assert(strcmp(result = mul("-11","-22"), "242") == 0);
free(result);

新的mul函数如下。

char * mul(const char *left, const char * right)
{
    if(is_positive(left) && is_negative(right))
        return negative( mul(left, right+1));
    if(is_negative(left) && is_positive(right))
        return negative( mul(left+1, right));
    if(is_negative(left) && is_negative(right))
        return mul(left+1, right+1);
    return mulInternal(left, right);

}

乘0

与0相乘等于0。

assert(strcmp(result = mul("0","-22"), "0") == 0);
free(result);

int is_zero(const char * n)
{
    return strlen(n) == 1 && n[0] == '0';
}

只要有一个乘数为0，结果就为0，避免无谓的计算。

 char * mul(const char *left, const char * right)
 {
    if(is_zero(left) || is_zero(right)) return add("0", "0");
    if(is_positive(left) && is_negative(right))
        return negative( mul(left, right+1));
    if(is_negative(left) && is_positive(right))
        return negative( mul(left+1, right));
    if(is_negative(left) && is_negative(right))
        return mul(left+1, right+1);
    return mulInternal(left, right);
  }

大功告成

最终的加、减、乘的计算过程如下所示。

char * add(const char * left, const char * right)
{
    if(is_positive(left) && is_negative(right))  return sub(left, right+1);
    if(is_negative(left) && is_positive(right))  return sub(right,left+1);
    if(is_negative(left) && is_negative(right))  return negative(add(left+1, right+1));
    else                                         return add_internal(left, right);
}

char * sub(const char *left, const char * right)
{
    if(is_positive(left) && is_negative(right))    return add(left, right+1);
    if(is_negative(left) && is_positive(right))    return negative( add(left+1, right));
    if(is_negative(left) && is_negative(right))    return sub(right+1, left+1);
    if(is_positive(left) && is_positive(right))
    {
        if (less_than_by_abs(left, right))    return negative( subInternal(right,left));
    }
    return subInternal(left,right);
}

char * mul(const char *left, const char * right)
{
    if(is_zero(left) || is_zero(right))          return add("0", "0");
    if(is_positive(left) && is_negative(right))  return negative( mul(left, right+1));
    if(is_negative(left) && is_positive(right))  return negative( mul(left+1, right));
    if(is_negative(left) && is_negative(right))  return mul(left+1, right+1);
    return mulInternal(left, right);
}

总结

原子与组合。
在最终的add sub mul函数中，关注于根据操作数不同的符号组合，执行不同的逻辑。而这里的逻辑是业务领域的高层逻辑，不关心算术运算的实现细节。

需求中加法、减法和乘法的实现细节，只体现在addInternal subInternal mulInternal三个函数中，它们是实现过程中的原子；其它高层的业务逻辑均在其基础通过组合的方式完成。使得设计具有良好的层次感和灵活性。
测试驱动设计。
测试用例在实现过程中具有很好的指引作用，通过测试用例的逐步深入，得以发现不同符合组合之间的转换规则。
领域概念。
实现过程中提取出来的函数：is_positive,is_negative,is_zero,
,negate,less_than_by_abs,greater_than_by_abs,mulByX,digit_value,max_width，均对应着算术运算领域中的相应概念。使得程序具有良好的可理解性。

大整数计算器

需求

实例化

加法：

减法

乘法

实现

下一个测试用例？

实现减法

到哪里了？

继续减法

负减正

负-负

乘法

多位数的乘法：

正×负

负×正

负×负

乘0

大功告成

总结

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读