Большие числа (длинная арифметика)

1.

2.

Программа, которая позволяет складывать и вычитать
два больших числа.
Создадим диалоговое приложение и спроектируем его
как показано на рисунке.
В свойствах элементов lineEdit зададим нули как значение поля text.

3.

Добавим к проекту класс BigNum.
Добавим в файл bignum.h код, показанный ниже:
#ifndef BIGNUM_H
#define BIGNUM_H
#include <QtWidgets>
class BigNum
{
QVector<qint8> vec; // Массив для хранения цифр числа
public:
BigNum(){};
BigNum(QString);
};
QString toString();
BigNum operator +(BigNum);
BigNum operator -(BigNum);
bool operator <(BigNum);
#endif // BIGNUM_H

4.

Оперции над числами выполняются справа налево, поэтому
удобнее записать цифры чисел в обратном порядке.
Например: 957 + 68 = 1025
+
7
5
8
6
5
2
9
0
1

5.

файл bignum.cpp
#include "bignum.h"
#include <QDebug>
// Конструктор для создания большого числа из строки:
BigNum::BigNum(QString str)
{
//Записываем цифры в обратном порядке:
{
}
}
for (int i = str.length()-1; i>=0; --i)
qint8 item = str[i].toLatin1() - '0';
vec << item;

6.

Работа с векторами может осуществляться с помощью
итераторов.
Итератор в стиле STL
Функция контейнера begin() возвращает итератор , указывающий на
первый элемент контейнера. Функция контейнера end() возвращает
итератор , указывающий на воображаемый элемент, находящийся в
позиции, следующей за последним элементом

7.

//Функция для преобразования объекта BigNum в строку:
QString BigNum::toString()
{
QString tmp;
// Итератор в стиле STL:
QVector<qint8>::iterator it = vec.end();
// переписываем цифры в обратном порядке:
while (it != vec.begin())
{
qint8 item = *--it;
tmp += QChar(item+'0');
}
return tmp;
}

8.

Итераторы в стиле Java
указывают на ячейку памяти между элементами, а не на сами элементы.
По этому они указывают либо на начало контейнера (перед первым
элементом), либо на конец контейнера (после последнего элемента),
либо между двумя элементами.

9.

BigNum BigNum::operator +(BigNum b)
{
BigNum sum;
// Итераторы в стиле Java:
QVectorIterator<qint8> it1(vec);
QVectorIterator<qint8> it2(b.vec);
qint8 digit = 0; // цифра в текущем разряде
qint8 carry = 0; // перенос

10.

while (it1.hasNext() || it2.hasNext())
{
qint8 a = it1.hasNext() ? it1.next() : 0;
qint8 b = it2.hasNext() ? it2.next() : 0;
digit = a + b+ carry ;
carry = digit / 10;
digit %= 10;
// qDebug() << carry << " " << digit;
sum.vec.push_back(digit);
}
if (carry) sum.vec.push_back(carry);
return sum;
}

11.

bool BigNum::operator <(BigNum b)
{
if (vec.size()<b.vec.size()) // первое число короче второго
return true; // значит первое меньше
else if (vec.size() == b.vec.size()) // одинаковое количество цифр
{
for (int i = vec.size()-1; i >=0; i--)
// проходим массивы с конца, поскольку цифры записаны в обратном порядке
{
if (vec[i] == b.vec[i]) continue;
// если цифры равны, переходим к следующему разряду
if (vec[i]<b.vec[i]) return true; // 123 и 130
else return false; // 234 и 145
}
return false;
}
else
return false;
}

12.

BigNum BigNum::operator -(BigNum b)
{
BigNum difference; // разность
// Итераторы в стиле Java:
QVectorIterator<qint8> it1(vec);
QVectorIterator<qint8> it2(b.vec);
bool sign = false;
if ( *this < b) // применяется операторная функция
{
it1 = QVectorIterator<qint8>(b.vec);
it2 = QVectorIterator<qint8>(vec);
// поменяли местами итераторы, чтобы вычитать из большего числа
sign = true; // нужно будет добавит минус к результату
}
qint8 digit = 0; // цифра в текущем разряде
qint8 borrow = 0; // заем из следующего разряда

13.

while (it1.hasNext()|| it2.hasNext())
{
qint8 a = it1.hasNext()? it1.next() : 0;
// qDebug() << " a = " << a;
if (borrow) a--;
// Если занимали, то число в текущем разряде уменьшаем
qint8 b = it2.hasNext()? it2.next() : 0;
// qDebug() << " b = " << b;
borrow = (b > a || a < 0) ? 10 : 0; // Когда нужно занимать?
a += borrow; // если произвели заем, добавляем в текущем разряде 10
digit = a - b ;
difference.vec.push_back(digit);
}

14.

// Итератор в стиле STL:
QVector<qint8>::iterator it = difference.vec.end();
// qDebug() <<"difference:";
// Удаляем нули, стоящие в начале числа: 1000 - 999 = 0001
while (*--it == 0 && difference.vec.size()>1)
{
difference.vec.pop_back();
}
if (sign) difference.vec << '-' - '0';
// ‘0’ потом будем прибавлять
return difference;
}

15.

файл dialog.cpp
#include "dialog.h"
#include "ui_dialog.h"
#include "bignum.h"
Dialog::Dialog(QWidget *parent) :
QDialog(parent),
ui(new Ui::Dialog)
{
ui->setupUi(this);
ui->lineEdit->setFocus();
ui->lineEdit->setSelection(0,255);
}
Dialog::~Dialog()
{
delete ui;
}

16.

void Dialog::on_pushButton_clicked()
{
BigNum a(ui->lineEdit->text());
BigNum b(ui->lineEdit_2->text());
BigNum c = a + b;
ui->label_3->setText(c.toString());
}
void Dialog::on_pushButton_2_clicked()
{
BigNum a(ui->lineEdit->text());
BigNum b(ui->lineEdit_2->text());
BigNum c = a - b;
ui->label_3->setText(c.toString());
}