| include | Loading last commit info... | |
| src | ||
| .clang-format | ||
| .gitignore | ||
| README.md | ||
| xmake.lua |
int2048
高精度计算是一种程序设计的算法。由于中央处理器的字长限制，如 32 位 CPU 中一个整数最大只能取值 4,294,967,295。因此在进行更大范围的数值计算中，往往要采取模拟手段。通常通过分离字符的方法通过数字数组进行输入、通过数组倒序输出、通过模拟竖式计算进行计算。一般而言，主要模拟的是按位运算，可以用不同的进位制达成不同的目的。
本次作业要求用 C++ 实现整数的高精度加减乘除。
实现要求
要求实现一个 C++ 的大整数类，命名为 int2048。
接口已在 int2048.h 中给出，你需要新建一个 int2048.cpp 文件，在其中实现给定的接口。
当然，你也可以在兼容当前所有接口的基础之上，自己添加新的接口或修改原有接口（例如实现 swap 函数、右值构造函数）。
相应的实现应该在 int2048.cpp 中完成，不要在 int2048.h 中实现。在 OJ 提交中，需要将 int2048.cpp 中的实现复制到 int2048.h 之中，再进行提交。
一些特殊要求
你不需要考虑除数或模数为 0 的情况。在该情况下，程序的行为属于未定义行为。我们保证测试点中不会出现这样的数据。
在我们的大整数类的实现中，对于除法操作 x / y ，其结果总是向下取整（即类似 python 中整除操作的表现）:
# 这是一段 python 代码
print(10 // 3, -10 // 3, 10 // -3, -10 // -3)
# 输出 3 -4 -4 3
# 因为 -10 / -3 = 3.333... 向下取整即为 3
# 而 10 / -3 = -3.333... 向下取整即为 -4
需要注意的是，C++ 中，有符号整数的除法是向 0 取整。
// 这是一段 C++ 代码
std::cout
<< 10 / 3 << ' '
<< 10 / -3 << ' '
<< -10 / 3 << ' '
<< -10 / -3 << '\n';
// 输出 3 -3 -3 3
// 因为 -10 / -3 = 3.333 向 0 取整即为 3
// 而 10 / -3 = -3.333... 向 0 取整即为 -3
而对于取模操作 x % y ，其被定义为 x % y = x - (x / y) * y 。
评分标准
总分共占比 6% 其中
- Integer 占比 100%
- code review 若码风较差将酌情扣分
B 班
- 构造函数以及关系运算符 10%
- 无符号高精度加减法 10%
- 有符号高精度加减法 10%
- 高精度乘法 10%
- 高精度除法 15%
- 压位高精度加、减、乘法 30%
- 压位高精度除法 15%
- BONUS：压位快速高精度除法（分治乘法） 1%
- BONUS：压位快速高精度除法（二分加速试商） 4%
A 班
- 构造函数以及关系运算符 10%
- 无符号高精度加减法 5%
- 有符号高精度加减法 10%
- 高精度乘法 10%
- 高精度除法 10%
- 压位高精度加、减、乘法 20%
- 压位高精度除法（二分加速试商） 15%
- 压位快速高精度乘法（快速傅立叶变换） 20%
- BONUS：压位快速高精度除法（分治除法/牛顿迭代法） 5%
PS：BONUS 部分对代码性能也有要求，需要通过对应的测试数据点才能得到分数。且 BONUS 上限为 5%，超过不溢出。
如果你写了 BONUS 的除法并且通过了对应的测试点，那么你将不需要实现二分加速试商除法。
对于 A 班同学，需要特别注意的是，你的 int2048 将会在之后的大作业 python 解释器中被使用。请务必保证你的代码有足够的健壮性，能够应对各种极端情况。
截止时间
B 班
第 11 周周一（11 月 20 日） 18:00
A 班
第 9 周周一（11 月 6 日） 18:00
数据范围
参考具体题目。
所有测试点时限均设置为 std 耗时的 2.5 倍以上。