Целочисленная арифметика

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

Основные операции

Целочисленная арифметика включает стандартные арифметические действия: сложение, вычитание, умножение и деление. Однако, в отличие от арифметики вещественных чисел, деление целых чисел не всегда даёт целый результат, что порождает понятие деления с остатком.

Сложение и вычитание

Сложение и вычитание целых чисел выполняются по правилам, известным со школьной программы. Для многозначных чисел используются алгоритмы сложения и вычитания «в столбик». В компьютерной арифметике сложение и вычитание реализуются через двоичные сумматоры, при этом возможно возникновение переполнения — ситуации, когда результат выходит за пределы допустимого диапазона для данного представления числа.

Умножение

Умножение целых чисел — это многократное сложение. Алгоритмы умножения включают умножение «в столбик» для десятичных чисел и различные методы для двоичной системы, такие как алгоритм Бута. Произведение двух n-разрядных чисел может иметь до 2n разрядов, что требует учёта при проектировании вычислительных устройств.

Деление и деление с остатком

Деление целых чисел — это операция, обратная умножению. Для любых целых чисел a и b (b ≠ 0) существует единственная пара целых чисел q (частное) и r (остаток), таких что: a = b q + r, где 0 ≤ r < |b|. Это утверждение известно как теорема о делении с остатком. Остаток r всегда неотрицателен и меньше модуля делителя. В программировании часто используется операция взятия остатка (модуль), обозначаемая символом % или mod. Например, 7 mod 3 = 1, так как 7 = 3 2 + 1.

Представление целых чисел в вычислительных системах

В цифровых устройствах целые числа представляются в двоичной системе счисления. Различают два основных способа представления: беззнаковое и знаковое.

Беззнаковое представление

Используется для неотрицательных целых чисел. Все разряды числа используются для хранения его модуля. Диапазон представления для n-разрядного числа: от 0 до 2ⁿ − 1. Например, для 8-разрядного байта диапазон составляет от 0 до 255.

Знаковое представление

Для представления отрицательных чисел применяются несколько методов:

• Прямой код: старший разряд отводится под знак (0 — положительное, 1 — отрицательное), остальные — под модуль числа. Недостаток: два представления нуля (+0 и −0).
• Обратный код: для отрицательного числа все биты модуля инвертируются. Также имеет два нуля.
• Дополнительный код: наиболее распространённый метод. Для отрицательного числа к обратному коду прибавляется единица. Это позволяет выполнять сложение и вычитание по единым правилам, а также устраняет проблему двух нулей. Диапазон для n-разрядного дополнительного кода: от −2ⁿ⁻¹ до 2ⁿ⁻¹ − 1.

Переполнение

Переполнение возникает, когда результат арифметической операции выходит за пределы допустимого диапазона для данного представления. Например, при сложении двух положительных 8-разрядных чисел 127 и 1 (в дополнительном коде) получается 128, что интерпретируется как −128. Обнаружение переполнения является важной задачей при проектировании процессоров.

Применение

Целочисленная арифметика широко применяется в различных областях:

• Программирование: все типы данных целых чисел (int, long, short) основаны на целочисленной арифметике. Операции с ними выполняются быстрее, чем с числами с плавающей запятой.
• Криптография: многие криптографические алгоритмы, такие как RSA и ECC, используют операции с большими целыми числами (сотни и тысячи бит). Целочисленная арифметика лежит в основе модульной арифметики, которая является ключевой для этих алгоритмов.
• Цифровая обработка сигналов: в некоторых системах (например, в микроконтроллерах) для повышения скорости вычислений используются целочисленные операции вместо операций с плавающей запятой.
• Теория чисел: целочисленная арифметика является основой для изучения свойств целых чисел, таких как делимость, простые числа, наибольший общий делитель и алгоритм Евклида.

Особенности в программировании

В языках программирования целочисленная арифметика имеет ряд особенностей:

• Деление целых чисел: в большинстве языков (C, C++, Java, Python) деление двух целых чисел даёт целое частное, а остаток отбрасывается (или берётся по модулю). Например, 7 / 3 в C даёт 2, а 7 % 3 даёт 1.
• Переполнение: в языках, таких как C и C++, переполнение целых чисел со знаком является неопределённым поведением, что может приводить к ошибкам. В Java и Python переполнение обрабатывается по-разному: в Java оно приводит к циклическому переходу (wrap-around), а в Python целые числа имеют неограниченную точность (автоматически переходят в длинную арифметику).
• Длинная арифметика: для работы с числами, выходящими за пределы стандартных типов данных, используются библиотеки длинной арифметики (например, GMP, BigInteger в Java, Python). Они реализуют целочисленную арифметику с произвольной точностью, но работают медленнее.

Исторические аспекты

Основы целочисленной арифметики были заложены ещё в Древней Греции (Евклид, «Начала»). В XVII веке Готфрид Лейбниц разработал двоичную систему счисления, которая стала основой для компьютерной арифметики. В XX веке с развитием вычислительной техники целочисленная арифметика была формализована в виде алгоритмов, реализованных в процессорах. В 1940-х годах Джон фон Нейман предложил архитектуру, в которой арифметико-логическое устройство выполняет целочисленные операции.

Источники

• Кнут Д. Э. Искусство программирования. Том 2. Получисленные алгоритмы. — 3-е изд. — М.: Вильямс, 2007.
• Таненбаум Э., Остин Т. Архитектура компьютера. — 6-е изд. — СПб.: Питер, 2013.
• Виноград С. Целочисленная арифметика и её приложения. — М.: Мир, 1976.