一个有趣的挑战。 :)
我假设您想要任意长度的整数。我建议采用以下方法:
考虑数据类型“int”的二进制性质。考虑使用简单的二进制运算来模拟 CPU 中的电路在添加内容时所做的操作。如果您有更深入的兴趣,请考虑阅读这篇关于半加器和全加器的维基百科文章 http://en.wikipedia.org/wiki/Half_adder。你会做类似的事情,但你可以降低到如此低的水平 - 但由于懒惰,我想我会放弃并找到一个更简单的解决方案。
但在讨论有关加、减、乘的算法细节之前,让我们先了解一些数据结构。当然,一种简单的方法是将内容存储在 std::vector 中。
template< class BaseType >
class BigInt
{
typedef typename BaseType BT;
protected: std::vector< BaseType > value_;
};
您可能需要考虑是否要使向量具有固定大小以及是否要对其进行预分配。原因是,对于不同的操作,您必须遍历向量的每个元素 - O(n)。您可能想立即知道一个操作将有多复杂,而固定的 n 就可以做到这一点。
现在介绍一些对数字进行操作的算法。您可以在逻辑级别上执行此操作,但我们将使用神奇的 CPU 能力来计算结果。但我们将从 Half- 和 FullAdders 的逻辑说明中继承的是它处理进位的方式。作为示例,请考虑如何实施+= 运算符。对于 BigInt::value_ 中的每个数字,您可以将它们相加,然后查看结果是否产生某种形式的进位。我们不会按位进行操作,而是依赖于 BaseType 的性质(无论是 long、int、short 还是其他类型):它会溢出。
当然,如果你将两个数字相加,结果一定大于其中较大的一个,对吗?如果不是,则结果溢出。
template< class BaseType >
BigInt< BaseType >& BigInt< BaseType >::operator += (BigInt< BaseType > const& operand)
{
BT count, carry = 0;
for (count = 0; count < std::max(value_.size(), operand.value_.size(); count++)
{
BT op0 = count < value_.size() ? value_.at(count) : 0,
op1 = count < operand.value_.size() ? operand.value_.at(count) : 0;
BT digits_result = op0 + op1 + carry;
if (digits_result-carry < std::max(op0, op1)
{
BT carry_old = carry;
carry = digits_result;
digits_result = (op0 + op1 + carry) >> sizeof(BT)*8; // NOTE [1]
}
else carry = 0;
}
return *this;
}
// NOTE 1: I did not test this code. And I am not sure if this will work; if it does
// not, then you must restrict BaseType to be the second biggest type
// available, i.e. a 32-bit int when you have a 64-bit long. Then use
// a temporary or a cast to the mightier type and retrieve the upper bits.
// Or you do it bitwise. ;-)
其他算术运算类似。哎呀,你甚至可以使用 stl 函子 std::plus 和 std::minus、std::times 和 std::divides,...,但要注意进位。 :) 您还可以使用加号和减号运算符来实现乘法和除法,但这非常慢,因为这会重新计算您在每次迭代中先前调用加号和减号时已经计算出的结果。对于这个简单的任务有很多好的算法,use http://en.wikipedia.org/wiki/Multiplication_algorithm 维基百科 http://en.wikipedia.org/wiki/Division_algorithm或网络。
当然,您应该实现标准运算符,例如operator<<
(只需将 value_ 中的每个值向左移动 n 位,从value_.size()-1
...哦,记住携带:),operator<
- 您甚至可以在这里进行一些优化,检查粗略的位数size()
第一的。等等。然后通过 befriendig std::ostream 让你的类变得有用operator<<
.
希望这个方法有帮助!