需求
编程语言中内置的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);
}
总结
-
原子与组合。
在最终的addsubmul函数中，关注于根据操作数不同的符号组合，执行不同的逻辑。而这里的逻辑是业务领域的高层逻辑，不关心算术运算的实现细节。需求中加法、减法和乘法的实现细节，只体现在
addInternalsubInternalmulInternal三个函数中，它们是实现过程中的原子；其它高层的业务逻辑均在其基础通过组合的方式完成。使得设计具有良好的层次感和灵活性。 测试驱动设计。
测试用例在实现过程中具有很好的指引作用，通过测试用例的逐步深入，得以发现不同符合组合之间的转换规则。领域概念。
实现过程中提取出来的函数：is_positive,is_negative,is_zero,
,negate,less_than_by_abs,greater_than_by_abs,mulByX,digit_value,max_width，均对应着算术运算领域中的相应概念。使得程序具有良好的可理解性。
