问题

用 C++ 实现大整数的加减,思路是什么?

回答
好的,咱们来聊聊用 C++ 实现大整数加减法这档事儿。这玩意儿说起来不复杂,但真要实现起来,得把一些基本原理掰扯清楚。

为啥要“大”整数?

电脑内置的 `int`、`long long` 这类数据类型,都有个上限。比如,`long long` 通常是 64 位,最大也就支持到 9 千万亿左右。但生活中很多场景,比如科学计算、金融领域,需要的数字可能远超这个范围。这就需要我们自己来造轮子了,搞一套能表示任意大数字的加减法。

怎么表示“大”整数?

既然内置类型不行了,我们就得找个东西来装这些数字。最直观的办法是啥?用字符串呗!每一位数字就是一个字符。

比如,数字 `12345` 可以表示成字符串 `"12345"`。

但这有个问题,字符串处理起来效率不高,而且直接加减也很麻烦。更好的方式是把数字拆开,用数组或者向量来存储。怎么拆?按位拆!

咱们可以把一个大整数看成是由很多个小数字组成的。就像我们平时写数字一样,是从右往左一位一位算的。那么,我们就可以用一个数组(或者 C++ 里的 `std::vector`),把大整数的每一位都存进去。

比如,数字 `12345`,我们可以这样存:
数组索引 0 存个位数 `5`
数组索引 1 存十位数 `4`
数组索引 2 存百位数 `3`
...以此类推

这样有什么好处?我们就可以模仿我们平时手动做加减法的方式来操作了。

加法思路:模拟手工加法

还记得小时候老师教的竖式加法吗?就是从个位开始,一位一位加,有进位就往上一位带。我们的大整数加法,思路就跟这个一模一样。

假设我们有两个大整数 `A` 和 `B`,它们分别存储在两个向量 `vecA` 和 `vecB` 里。

1. 准备工作:
先确定哪个数更大(或者长度更长),方便我们按位相加。
创建一个新的向量 `vecResult` 来存放加法的结果。长度应该至少和较长的那个数一样。
准备一个变量 `carry`(进位),初始值是 0。

2. 逐位相加:
从两个数的最低位(也就是向量的第一个元素,对应个位数)开始,进行循环。
在每一位上,我们把 `vecA` 中对应位的数字、`vecB` 中对应位的数字,再加上上一位的进位 `carry`,得到一个当前位的和。
这个和,我们取它的个位数作为结果向量 `vecResult` 中当前位的值。
这个和的十位数,就是下一位的进位 `carry`。

举个例子:
假设 `A = 123` (存为 `[3, 2, 1]`),`B = 456` (存为 `[6, 5, 4]`)。

第一位(个位): `vecA[0] = 3`,`vecB[0] = 6`。 `carry = 0`。
和 = `3 + 6 + 0 = 9`。
结果位 `vecResult[0] = 9`。
进位 `carry = 0`。

第二位(十位): `vecA[1] = 2`,`vecB[1] = 5`。 `carry = 0`。
和 = `2 + 5 + 0 = 7`。
结果位 `vecResult[1] = 7`。
进位 `carry = 0`。

第三位(百位): `vecA[2] = 1`,`vecB[2] = 4`。 `carry = 0`。
和 = `1 + 4 + 0 = 5`。
结果位 `vecResult[2] = 5`。
进位 `carry = 0`。

循环结束后,如果 `carry` 还有值(比如加法结果是 1000),说明我们还有一位需要加到结果里。

3. 处理长度不一致的情况:
如果两个大整数的位数不一样,我们在位相加的时候,可以认为长度较短的那个数,高位都是 0。比如 `123 + 45`,就相当于 `123 + 045`。所以,在循环里访问向量时,要注意边界,如果某个向量的索引已经超出了它的长度,就当作是 0 来处理。

4. 最终进位:
当所有位都加完了,如果 `carry` 仍然大于 0,说明最后还有一位进位。需要把这个进位加到结果的最高位。如果结果向量已经满了,就需要在向量后面再追加一位。

减法思路:同样模拟手工减法,但要注意“借位”

减法和加法思路类似,也是逐位相减,但是需要处理“借位”这个概念。

假设我们要计算 `A B`。

1. 准备工作:
首先要确保 `A >= B`,否则结果是负数,这个我们暂时不考虑,先只处理 `A >= B` 的情况。如果 `B > A`,我们可以先记下来,最后结果取反。
确定 `A` 和 `B` 的长度,并让它们长度一致(用高位补 0)。
创建一个结果向量 `vecResult`。
准备一个变量 `borrow`(借位),初始值是 0。

2. 逐位相减:
从最低位开始,循环。
在每一位上,用 `vecA` 的当前位减去 `vecB` 的当前位,再加上上一位的借位 `borrow`。
注意,这里是减去 `borrow`,因为 `borrow` 是从上一位“借”过来的。
如果当前位减完后小于 0,说明这一位需要向前一位借位。我们就给当前结果加上 10,然后将 `borrow` 设置为 1。否则 `borrow` 设置为 0。
将计算出的当前位的值存入 `vecResult`。

举个例子:
假设 `A = 456` (存为 `[6, 5, 4]`),`B = 123` (存为 `[3, 2, 1]`)。

第一位(个位): `vecA[0] = 6`,`vecB[0] = 3`。 `borrow = 0`。
当前位计算:`6 3 0 = 3`。
结果位 `vecResult[0] = 3`。
新的 `borrow = 0`。

第二位(十位): `vecA[1] = 5`,`vecB[1] = 2`。 `borrow = 0`。
当前位计算:`5 2 0 = 3`。
结果位 `vecResult[1] = 3`。
新的 `borrow = 0`。

第三位(百位): `vecA[2] = 4`,`vecB[2] = 1`。 `borrow = 0`。
当前位计算:`4 1 0 = 3`。
结果位 `vecResult[2] = 3`。
新的 `borrow = 0`。

再来个需要借位的例子: `A = 432` (存为 `[2, 3, 4]`),`B = 158` (存为 `[8, 5, 1]`)。

第一位(个位): `vecA[0] = 2`,`vecB[0] = 8`。 `borrow = 0`。
当前位计算:`2 8 0 = 6`。
由于小于 0,所以这一位是 `6 + 10 = 4`。
结果位 `vecResult[0] = 4`。
新的 `borrow = 1`(向前一位借了 1)。

第二位(十位): `vecA[1] = 3`,`vecB[1] = 5`。 `borrow = 1`。
当前位计算:`3 5 1 = 3`。
由于小于 0,所以这一位是 `3 + 10 = 7`。
结果位 `vecResult[1] = 7`。
新的 `borrow = 1`(向前一位借了 1)。

第三位(百位): `vecA[2] = 4`,`vecB[2] = 1`。 `borrow = 1`。
当前位计算:`4 1 1 = 2`。
结果位 `vecResult[2] = 2`。
新的 `borrow = 0`。

结果就是 `274`。

3. 处理符号:
如果一开始判断出 `B > A`,我们应该先执行 `B A`,然后给最终结果加上负号。

4. 去除前导零:
计算完成后,结果向量的最高位可能不是我们期望的非零数字。比如 `100 99`,计算过程可能会产生 `[1, 0, 0]`,但实际上是 `1`。我们需要从结果向量的最高位开始,把前面所有的 0 都去掉,直到遇到第一个非零数字为止。如果计算结果是 0,则结果就是 0。

数据结构的选择

`std::vector`: 这是 C++ 中最常用的动态数组。我们可以用它来存储大整数的每一位数字。`push_back()` 可以方便地添加元素。
字符串(`std::string`): 虽然可以用字符串来表示,但通常是作为输入的初始格式。在内部进行计算时,还是转换成数字向量更方便。

实现的关键点

字符串转向量: 需要遍历字符串,将每个字符减去 `'0'` 得到对应的数字,然后存入向量。注意字符串的顺序和向量的顺序是相反的,字符串是从左到右(高位到低位),而向量通常是从低位到高位存储,这样处理进位和借位更方便。
向量转字符串: 计算完成后,需要把向量里的数字转换回字符串方便输出。同样要注意顺序,从向量的最高位往最低位输出。
边界条件: 特别是处理长度不一致的时候,要确保不越界访问。
符号处理: 对于减法,要妥善处理被减数小于减数的情况。
效率考虑: 虽然这里讨论的是基础的加减,但如果处理非常非常大的数字,可能还需要考虑使用更高级的算法(比如 Karatsuba 算法),不过那超出了基础加减的范畴了。

总的来说,大整数加减法的核心就是模拟手工计算的过程,把数字拆成一位一位的,然后用循环处理进位和借位。这就像搭积木一样,一块一块地把大数堆砌起来或者拆解开。

希望这个详细的解释能让你对大整数加减法的实现思路有一个清晰的认识!

网友意见

user avatar

首先,这个问题可归类为

Arbitrary-precision arithmetic

(任意精度计算),一般会包含任意精度的整数(或定点数)、有理数及浮点数。

许多答案提及到使用10进制(或是10进制的字符串)进行运算,但这并不是唯一的方法,而且比较慢。

如果程序有大量的计算,而把结果转换成10进制显示并非程序的主要功能,那么可以考虑使用2^n进制。例如在32位架构下,使用vector<uint32_t>及去代表一个任意精度的无号整数。

我们首先要实现n位全加器,用2^n进制的话可以使用机器本身的算术指令,例如以下的 C++实现:

       uint32_t FullAdder32(uint32_t a, uint32_t b, uint32_t inCarry, uint32_t* outCarry) {     uint64_t c = static_cast<uint64_t>(a)                + static_cast<uint64_t>(b)                + static_cast<uint64_t>(inCarry);     *outCarry = static_cast<uint32_t>(c >> 32);     return static_cast<uint32_t>(c & 0xFFFFFFFF); }      

一些编译器提供带进位的加法,例如VC x86中有_addcarry_u32()和addcarry_u64()指令。

任意精度的无号整数的加法和减法可以使用简单的漣波进位加法器(ripple carry adder)实现,也可考虑使用并行的超前进位加法器(carry-lookahead adder)。

       // 最低位在A.front(),最高位在A.back()。 void RippleCarryAdder(     const vector<uint32_t>& A     const vector<uint32_t>& B     vector<uint32_t>* R) {     assert(!A.empty());     assert(!B.empty());     assert(R != NULL);      const size_t n = max(A.size(), B.size())     R->clear();     R->reserve(n + 1);      // 为简单起见,超越范围的输入补零。可优化为不同cases的循环,减少inner-loop分支。     uint32_t inCarry = 0u;     for (size_t i = 0; i < n; i++) {         uint32_t outCarry;         R->push_back(FullAdder32(              i < A.size() ? A[i] : 0u,               i < B.size() ? B[i] : 0u,              inCarry,              &outCarry));         inCarry = outCarry;     }      // 最后的进位     if (inCarry)         R->push_back(inCarry); } // 注意:随手写,未经测试      

减法可使用二进位补数记法(two's complement representation),然后用加法处理。二进位补数记法的取反很简单,而加一也可以放在开始时设置inCarry=1。但要注意处理负数的结果,要支持负数的话,每个任意精度的数还要多加一个符号标记。

然而,如果需要把结果转换为十进制,便需要除法或c。每次除10取模可得一个10进位。除以一个常数可以优化为乘数及移位,详情可看《

Hacker's Delight (豆瓣)

》。

另一种方法,是使用接近机器位数的10^n进位作为基数(base),例如32位架构可以使用10^9。优点是可以简单地转换为10进位的输出,缺点是浪费了一些运算能力。

题目没提及乘法和除法,简单提一提。乘法要分开低位的乘法和高位的乘法,如VC x86中的__mulh()便是64位乘法结果的高位部分,如果没有相关指令就要把输入切为一半一半来计算。然后像竖式计算般把每对输入相乘然后加总,这称为长整数乘法(long multiplication)。另外还有一些更快的方法,如

Karatsuba algorithm

、Toom–Cook multiplication、Schönhage–Strassen algorithm。除法的话也有长除法(long division)和其他更快的算法。

类似的话题

  • 回答
    好的,咱们来聊聊用 C++ 实现大整数加减法这档事儿。这玩意儿说起来不复杂,但真要实现起来,得把一些基本原理掰扯清楚。 为啥要“大”整数?电脑内置的 `int`、`long long` 这类数据类型,都有个上限。比如,`long long` 通常是 64 位,最大也就支持到 9 千万亿左右。但生活中.............
  • 回答
    你提出的这个问题非常棒,也非常普遍。《深度探索 C++ 对象模型》这本书确实深入挖掘了 C++ 的底层细节,而虚继承就是其中一个常常让读者感到“蛋疼”但又觉得好像用处不大的特性。是否需要继续深究虚继承,这取决于你的目标和对 C++ 的追求。 如果你只是想成为一个能“正常”使用 C++ 的开发者,.............
  • 回答
    当然,我们来聊聊如何在 C 中实现一个避免装箱的通用容器。这实际上是一个挺有意思的话题,因为它触及了 C 类型系统和性能优化的核心。你提到的“装箱”(boxing)是指当一个值类型(比如 `int`, `float`, `struct`)被当作引用类型(比如 `object`)来处理时,会在托管堆上.............
  • 回答
    这个问题啊,问得挺实在的。很多人听到Python和Java都是用C/C++实现的,就觉得,“既然底层都是C/C++,那直接用C/C++不就得了?省事儿。” 这话听起来没毛病,但其实这里面涉及到很多关于编程语言设计、生态构建和实际应用场景的取舍,远不是“省事”两个字能概括的。咱们一层一层剥开来看。 为.............
  • 回答
    Android 平台在开发语言的选择上,确实存在一个有趣且值得深入探讨的问题:未来的 Android 开发是否能完全拥抱 C/C++,还是说现有的架构已经将 Java 锁定为主要舞台?要理解这个问题,我们得先看看 Android 的“出身”和“性格”。Android 最初诞生于 Linux 内核之上.............
  • 回答
    当然可以,用C语言在100行之内实现一个基本的贪吃蛇游戏是完全可行的。下面我将一步一步地告诉你如何做到这一点,并尽量讲得清楚明白,让它读起来像是出自一个真心想和你分享编程乐趣的老司机之手。我们要实现的是一个非常精简的版本,只包含最核心的元素: 游戏区域: 一个固定的矩形区域。 蛇: 由一系列.............
  • 回答
    好的,非常乐意为您详细讲解如何使用 C 语言和 Windows API 实现一个基本的 SSL/TLS 协议。您提到参考资料已备齐,这非常好,因为 SSL/TLS 是一个相当复杂的协议,没有参考资料很难深入理解。我们将从一个高层次的概述开始,然后逐步深入到具体的 Windows API 函数和 C .............
  • 回答
    C++ STL中的`map`和`Python`的字典(`dict`)在实现上选择不同的数据结构(红黑树 vs 哈希表),主要源于语言设计哲学、性能需求、内存管理、有序性要求等多方面的权衡。以下是详细分析: 1. 红黑树 vs 哈希表的核心差异| 特性 | 红黑树 .............
  • 回答
    当然可以,C语言作为一门编译型语言,其强大的跨平台能力很大程度上得益于其设计理念和标准库。通过遵循一定的规则,并且在不同平台上都拥有能够解析和生成对应机器码的编译器,C语言的源代码确实能够实现跨平台运行。这背后的原理可以从几个关键点来理解:1. C语言的标准化与抽象层:C语言之所以能实现跨平台,最根.............
  • 回答
    确实,在C语言的学习和考试中,有时会故意设置一些陷阱,比如用相同的变量名来命名形参、实参、局部变量和全局变量,让学生去区分它们的作用域和生命周期。这种做法,从教学角度来看,是非常有实际意义的,甚至可以说是至关重要的。让我详细地解释一下其中的道理:核心问题:理解“作用域”和“生命周期”C语言的精妙之处.............
  • 回答
    我理解你的感受。学了一个学期的C语言,却感觉好像一直在做数学题,这在很多初学者身上是很常见的,也确实会让人产生“C语言有什么实际用途”的疑问。别急,我们一点点来聊聊,为什么会这样,以及C语言到底能干什么。一、 初学C语言,为何“似曾相识”的数学题?这主要是因为C语言在设计之初,就非常强调底层操作和对.............
  • 回答
    作为一名C开发者,想要打造一款令人眼前一亮的桌面应用界面,绝非一日之功。这需要我们从多个维度去思考和实践,结合美学原则、用户体验设计以及技术手段,才能最终呈现出既实用又赏心悦目的作品。本文就来深入探讨一下,如何在C桌面应用开发中做出漂亮的界面。一、 理解“漂亮”的内涵:超越视觉的极致体验首先,我们要.............
  • 回答
    C/C++ 在工业软件开发中的角色:一位经验丰富的工程师的看法要回答“C/C++ 是否适合开发工业软件”,我觉得这个问题本身就带有一点“事后诸葛亮”的味道。在我们这些做工业软件的人看来,C/C++ 一直以来就是 工业软件开发的主力军,甚至可以说是 不可或缺 的存在。说它“适合”?这更像是在问“水适合.............
  • 回答
    解析 JSON 字符串,即使是简单的,也需要我们细致地观察字符串本身的结构,然后根据这些结构来提取我们需要的数据。我们可以把 JSON 字符串想象成一个嵌套的盒子,里面装着各种类型的值。我们的任务就是一层一层地打开这些盒子,取出里面的东西。核心思路:识别 JSON 的基本构成元素JSON 的核心就两.............
  • 回答
    在 C 语言中绘制心形有多种方法,最常见和易于理解的方法是使用字符输出,也就是在控制台上用特定的字符(如 `` 或 ``)组合成心形的形状。另一种更高级的方法是使用图形库(如 SDL、Allegro 或 Windows GDI)来绘制真正的图形心形,但这需要更多的设置和知识。这里我们主要讲解 字符输.............
  • 回答
    好的,咱们来聊聊怎么用 C 语言算 1000 的阶乘。这可不是件小事,因为 1000 的阶乘是个超级无敌大的数字,远超出了 C 语言里任何内置数据类型能表示的范围。所以,咱们得自己动手,实现一个能处理大数乘法的算法。问题所在:为什么内置类型不行?在 C 语言里,我们常用的数字类型有 `int`、`l.............
  • 回答
    从零开始,用 C++ 打造属于你的图形用户界面很多时候,我们希望程序能够以更加直观、易用的方式与用户交互,而不是仅仅停留在命令行界面。这时候,图形用户界面(GUI)就显得尤为重要了。很多人可能觉得 C++ 编写 GUI 是一件非常复杂的事情,需要依赖各种庞大的框架。但事实上,我们可以从最基础的概念入.............
  • 回答
    好的,咱们不聊那些虚头巴脑的,直接说说怎么用C语言把一个三维球体给“画”出来。你可能以为这是什么高大上的图形学才能做的事情,其实不然,很多时候我们理解的三维“画”其实是模拟。要用C语言“画”一个三维球体,咱们主要有两种思路,一种是控制台输出(ASCII art),一种是借助图形库(比如SDL, Op.............
  • 回答
    好嘞,咱们这就来聊聊怎么用 C 语言搭一个简易计算器。别担心,不讲那些晦涩难懂的理论,咱们一步一步来,就像搭积木一样,让它一点点变得能用起来。1. 目标:我们想做什么?首先,得明确我们要造个什么样的计算器。最基本的,就是能做加、减、乘、除这四种运算。所以,咱们的用户需要输入: 第一个数字 运.............
  • 回答
    好的,不使用列表,我来详细说说如何用C语言生成一个范围在 (0, 1) 之间的随机浮点数。在C语言中,我们通常依赖标准库中的函数来处理随机数。最核心的函数是 `rand()`。1. `rand()` 函数的初步认识`rand()` 函数位于 `` 头文件中。它会返回一个介于 0 和 `RAND_MA.............

本站所有内容均为互联网搜索引擎提供的公开搜索信息,本站不存储任何数据与内容,任何内容与数据均与本站无关,如有需要请联系相关搜索引擎包括但不限于百度google,bing,sogou

© 2025 tinynews.org All Rights Reserved. 百科问答小站 版权所有