Приветствую всех, это вторая статья из серии про реализацию больших чисел на языке C/C++. В прошлый раз я рассказывал про общую структуру класса BigNumber и способ хранения большого числа в памяти. Были реализованы функции нормирования большого числа для печати и две арифметические операции: сложение и вычитание.
Не знаю точно, сколько еще статей будет на эту тему, но с этих пор в начале каждой буду оставлять ссылки для навигации.
- Реализация больших чисел на C/C++ со сложением и вычитанием;
- Операторы сравнения больших чисел — реализация на C/C++;
- Умножение больших чисел — реализация на C/C++.
В прошлый раз я обещал, что следующим шагом станет реализация деления и умножения больших чисел, но потом понял, что они не выполнимы без возможности сравнивать два числа. Кроме того, большинство алгоритмов отпадает без этого функционала. Поэтому в этот раз я приведу реализации всех операторов сравнения: ==, !=, >, >=, <, <=.
Важно! Дабы не растягивать и без того длинный листинг исходного кода, я не буду здесь публиковать сам класс BigNumber, его вместе с реализацией сложения, вычитания и нормализации вы можете найти в прошлой статье.
Реализация операторов сравнения больших чисел
Что у нас есть для того, чтобы сравнить два больших числа? Только их знаки, размеры чанок и значения чисел в самих чанках. И этого нам будет достаточно. Алгоритм любого оператора будет строится следующим образом.
- Нормализовать оба числа и привести их к максимально удобоваримому виду;
- Далее смотрим знаки чисел и делим алгоритм на две ветки: если знаки равны и если не равны;
- Дальнейшие действия зависят от оператора, иногда можно сразу сделать вывод, если нет, то смотрим размер числа;
- Если и по размеру чисел не удалось сделать вывод, то сравниваем чанки по значениям.
Исходный код операторов сравнения
Для начала я покажу, как должны выглядеть объявления операторов в самом классе BigNumber.
|
1 2 3 4 5 6 7 |
public: bool operator == (BigNumber); bool operator != (BigNumber); bool operator <= (BigNumber); bool operator >= (BigNumber); bool operator < (BigNumber); bool operator > (BigNumber); |
Начнем с самых простых в реализации: == и !=.
Исходный код операторов == и !=
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
bool BigNumber::operator == (BigNumber num) { num._normalizationChunks(); num._normalizationSigns(); (*this)._normalizationChunks(); (*this)._normalizationSigns(); if (this->sign == num.sign) { //Если числа разного размера, то они не равны if (this->chunks.size() != num.chunks.size()) { return false; } //Сравнить почанково for (int i = this->chunks.size() - 1; i >= 0; i--) { if (this->chunks[i] != num.chunks[i]) { return false; } } return true; } //Если знаки не равны, то и числа не равны else { return false; } } bool BigNumber::operator != (BigNumber num) { num._normalizationChunks(); num._normalizationSigns(); (*this)._normalizationChunks(); (*this)._normalizationSigns(); if (this->sign == num.sign) { //Если числа разного размера, то они не равны if (this->chunks.size() != num.chunks.size()) { return true; } //Сравнить почанково for (int i = this->chunks.size() - 1; i >= 0; i--) { if (this->chunks[i] != num.chunks[i]) { return true; } } return false; } //Если знаки не равны, то и числа не равны else { return true; } } |
Исходный код операторов < и <=
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 |
bool BigNumber::operator < (BigNumber num) { num._normalizationChunks(); num._normalizationSigns(); (*this)._normalizationChunks(); (*this)._normalizationSigns(); //Если знаки не равны, то сразу делаем вывод if (this->sign != num.sign) { if (this->sign == -1) { return true; } else { return false; } } else { //Если можно сделать вывод по длине числа if (this->chunks.size() < num.chunks.size()) { return true; } if (this->chunks.size() > num.chunks.size()) { return false; } //Если одинаковой длины, сравниваем значения if (this->sign != -1) { for (int i = this->chunks.size() - 1; i >= 0; i--) { if (this->chunks[i] > num.chunks[i]) { return false; } if (this->chunks[i] < num.chunks[i]) { return true; } } if (this->chunks[0] >= num.chunks[0]) { return false; } else { return true; } } //Если первое число отрицательное else { for (int i = this->chunks.size() - 1; i >= 0; i--) { if (this->chunks[i] < num.chunks[i]) { return false; } if (this->chunks[i] > num.chunks[i]) { return true; } } if (this->chunks[0] <= num.chunks[0]) { return false; } else { return true; } } } return false; } bool BigNumber::operator <= (BigNumber num) { num._normalizationChunks(); num._normalizationSigns(); (*this)._normalizationChunks(); (*this)._normalizationSigns(); if (this->sign != num.sign) { if (sign == -1) { return true; } else { return false; } } else { if (this->chunks.size() < num.chunks.size()) { return true; } if (this->chunks.size() > num.chunks.size()) { return false; } if (sign != -1) { for (int i = this->chunks.size() - 1; i >= 0; i--) { if (this->chunks[i] > num.chunks[i]) { return false; } if (this->chunks[i] < num.chunks[i]) { return true; } } if (this->chunks[0] > num.chunks[0]) { return false; } else { return true; } } else { for (int i = this->chunks.size() - 1; i >= 0; i--) { if (this->chunks[i] < num.chunks[i]) { return false; } if (this->chunks[i] > num.chunks[i]) { return true; } } if (this->chunks[0] < num.chunks[0]) { return false; } else { return true; } } } return false; } |
Исходный код операторов > и >=
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 |
bool BigNumber::operator > (BigNumber num) { num._normalizationChunks(); num._normalizationSigns(); (*this)._normalizationChunks(); (*this)._normalizationSigns(); if (this->sign != num.sign) { if (this->sign == -1) { return false; } else { return true; } } else { if (this->chunks.size() > num.chunks.size()) { return true; } if (this->chunks.size() < num.chunks.size()) { return false; } if (sign == -1) { for (int i = this->chunks.size() - 1; i >= 0; i--) { if (this->chunks[i] > num.chunks[i]) { return false; } if (this->chunks[i] < num.chunks[i]) { return true; } } if (this->chunks[0] >= num.chunks[0]) { return false; } else { return true; } } else { for (int i = this->chunks.size() - 1; i >= 0; i--) { if (this->chunks[i] < num.chunks[i]) { return false; } if (this->chunks[i] > num.chunks[i]) { return true; } } if (this->chunks[0] <= num.chunks[0]) { return false; } else { return true; } } } return false; } bool BigNumber::operator >= (BigNumber num) { num._normalizationChunks(); num._normalizationSigns(); (*this)._normalizationChunks(); (*this)._normalizationSigns(); if (this->sign != num.sign) { if (sign == -1) { return false; } else { return true; } } else { if (this->chunks.size() > num.chunks.size()) { return true; } if (this->chunks.size() < num.chunks.size()) { return false; } if (sign == -1) { for (int i = this->chunks.size() - 1; i >= 0; i--) { if (this->chunks[i] > num.chunks[i]) { return false; } if (this->chunks[i] < num.chunks[i]) { return true; } } if (this->chunks[0] > num.chunks[0]) { return false; } else { return true; } } else { for (int i = this->chunks.size() - 1; i >= 0; i--) { if (this->chunks[i] < num.chunks[i]) { return false; } if (this->chunks[i] > num.chunks[i]) { return true; } } if (this->chunks[0] < num.chunks[0]) { return false; } else { return true; } } } return false; } |
Заключение
Вот собственно и все, в следующий раз уже точно будут реализации деления и умножения, спасибо за внимание!