Другие языки программирования и технологии

Язык программирования с++. Задача.

Давным-давно пытался изучить этот язык. Помню, давалась в книге задача. Нужно было сделать калькулятор. Причём калькулятор должен был уметь работать с целыми числами свыше 4 байт (свыше 4 294 967 296).
Подскажите (желательно с примером кода на с++, хотя можно и словами) , как сложить два четырёхбайтовых беззнаковых числа, и отследить это? Вдруг сумма превысит максимально допустимое число, которое поместится в 4 байта? Ведь тогда оно начнёт с нуля снова увеличиваться. Нужно сделать так, чтобы продолжалось сложение выше предела в 4 байта. Переменные типа Double и Float не использовать.
Так понимаю, при сложении нужно проверять какой-то регистр на переполнение и добавлять ещё дополнительную переменную, в которой будут дополнительные цифры?
Например, нам нужно сложить 4 000 000 000 + 2 600 000 258 и получить в итоге 6 600 000 258, а не 2 305 032 962 (с учётом переполнения переменной) . Где хранить это число 6 600 000 258 без потери точности?
Надеюсь, понятно объяснил суть задачи.
Мариан Гаина
Мариан Гаина
45 384
Для сложения любых чисел, которые выходят за рамки стандартных типов данных используются массивы интов, например.
В зависимости от того, на сколько вы хорошо понимаете как переводить десятичные числа в двоичную систему представления и как с этим работать, можно применить два подхода:

дилетантский, это когда вы каждую ячейку массива используете как несколько разрядов справа налево. Например, самая правая ячейка содержит значения 6ти знаков (до миллиона) - "младший разряд", следующая еще шесть (10 в 12й степени получается) - "следующий разряд" и т. д.

Тогда вы все эти ячейки массива для простоты понимания можете представить как цифры числа и вся работа с ними организовывается так же, как бы вы считали на бумажке - пять пишу, один в уме (переходит в следующий разряд) .

Соответственно считать вы можете пока не упретесь в ограничение по памяти.

Но такой вариант не эффективен.

Эффективнее двоичное представление данных, тут вам уже пользователь мозг рассказал как действовать на уровне ассемблера, т. к. это будет наиболее эффективно. Т. е. вы изначально преобразовываете число в виде строки на входе в двоичное представление, кладете его в память, разделенную на ячейки и на уровне битовых операций с переполнением проводите все операции.

Первый же вариант, когда вы берете массив интов - это уровень школы-колледжа, чисто на понимание алгоритмов работы с большими числами.
Николай Панфилов
Николай Панфилов
2 067
Лучший ответ
Мариан Гаина Ясно. Просто с ассемблером внутри с++ ещё не доводилось работать. Видимо можно использовать куски его кода внутри с++ ?
Смысл понятен, будем думать.
Мариан Гаина Только "не мне пользователь мозг рассказал, как действовать", а "мне, пользователю мозгу, рассказали как действовать" :)
Используйте готовые библиотеки.
Есть GMP : https://gmplib.org/
Есть Boost.Multiprecision : http://www.boost.org/doc/libs/1_55_0/libs/multiprecision/doc/html/index.html
Наверняка есть множество других.
Paata Kostava
Paata Kostava
88 903
А использование unsigned long long int тоже запрещено условиями задачи?
КК
Клим Кузьмин
24 825
Мариан Гаина Проблему решает лишь отчасти. Пусть unsigned long int у меня компилятор определяет размер в 4 байта. Тогда у unsigned long long int размер будет 8 байт. Как тогда сложить два восьмибайтовых числа? Здесь в задаче ограничение конкретно не в 4 байта. Цель - сделать безграничное сложение и умножение, чтоб при необходимости выделялись новые байты памяти для хранение всё более старших разрядов суммы или произведения.
Не надо так усложнять.
Откастите хотя бы один из аругментов в лонг лонг, он на десятке самых популярных осей 64-битный, а результат через побитовое И проверьте по маске.

Код писать не могу, латиница запрещена: -)
Андрей Соломенцев
Андрей Соломенцев
19 662
Мариан Гаина Эээ, а можете написать код в текстовом редакторе и снять скриншот с этого кода? И мне прислать в почту?
На ассемблере всё просто: сложил и контроль бита переполнения.
С языками всё интереснее: сложить просто, основная проблема - где хранить результат, если есть переполнение (в 4 байта они не влезают) .
В принципе, есть 64-битные целые, но проблем они не решают.

А с длинной арифметикой поступают как в начальной школе - в столбик. Только цифры не 0-9, а байты, слова или что там получится с учетом разрядности процессора. Для хранения можно использовать записи типа: длина записи + массив слов (открытый) .

На пальцах:
Складываем младшие слова, получаем слово суммы и 0 или 1 переполнения.
Потом складываем переполнение и старшие слова - тоже получим старшее слово суммы и 0 или 1 переполнения старшего разряда.
С умножением - аналогично.
Евгений Стасюк
Евгений Стасюк
11 112
Мариан Гаина В принципе так и думал - старшие, вышедшие за границы 4-байтной зоны, разряды помещать в следующий байт. Буду думать, как теперь это в коде реализовать. Спасибо.

Похожие вопросы