Файл: Разработка модуля для выполнения операций с натуральными числами в 16-ричной системе счисления (Виды позиционных систем счисления).pdf

Введение

В современном мире мы постоянно имеем дело с числами. Они окружают нас в повседневной деятельности. Историческая наука определяет, что и несколько тысячелетий назад (не менее пяти тысяч лет) уже существовала наука о числах и арифметических действиях над ними. При этом правила записи чисел и работы с ними, конечно, несколько отличались, чем сейчас. Однако, тем не менее, числа, так же как и сейчас, изображалось с помощью одного или нескольких символов. Подобные символы, используемые при записи числа в математике и информатике, называют цифрами [10].

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

Под системой счисления понимается способ записи (изображения) чисел. Системы счисления (как существовавшие ранее, так используемые и сегодня) делятся на две группы: позиционные и непозиционные. Наиболее разработанными являются позиционные системы счисления (ПСС) – системы записи чисел, в которых вклад каждой цифры в величину числа зависит от её положения (позиции) в последовательности цифр, изображающей число. Те системы счисления, в которых каждой цифре соответствует величина, не зависящая от её места в записи числа, называются непозиционными. Также существуют различные смешанные системы счисления. В настоящее время конечно используются ПСС, которые представляют собой результат длительного исторического развития непозиционных систем счисления. Причем наибольшее распространение получила десятичная система счисления, а также двоичная система счисления. Теме не менее, на практике используются и другие системы счисления.

Для представления двоичных чисел вне компьютера используют более компактные по длине чисел восьмеричную (для записи кодов чисел и машинных команд) и шестнадцатеричную (для записи адреса команд) системы счисления. Шестнадцатеричная система счисления широко используется в низкоуровневом программировании и компьютерной документации, поскольку в современных компьютерах минимальной адресуемой единицей памяти является 8-битный байт, значения которого удобно записывать двумя шестнадцатеричными цифрами. [2, 10]

---

Объект исследования: арифметические операции с натуральными числами в 16-ричной системе счисления.

Предмет исследования: программная реализация арифметических операций с натуральными числами в 16-ричной системе счисления.

Целью данной работы является разработка модуля для выполнения операций с натуральными числами в 16-ричной системе счисления.

Для достижения поставленной цели необходимо решить следующие задачи:

• подобрать и проанализировать литературу по данной теме;
• изучить теоретические основы выполнения вычислительных операций в 16-ричной системе счисления: особенности и правила выполнения арифметических операции с 16-ричными натуральными числами;
• разработать на языке программирования C и протестировать программное приложение для выполнения операций с натуральными числами в 16-ричной системе счисления.

Для решения поставленных задач был подобрана научная литература по системам счисления ([2, 4, 7, 8, 9, 10]) и объектно-ориентированным языкам программирования, в частности по C# [1, 3, 5, 6, 11-15].

1. Теоретически основы выполнения вычислительных операцийв 16-ричной системе счисления

Виды позиционных систем счисления

В ПСС цифры, используемые в записи числа, имеют различные значения в зависимости от их места (позиции) в числе. Создание подобной позиционной нумерации, основанной на привязке значений цифр к их позиции в числе, приписывается шумерам и вавилонянам. Такая нумерация также была развита индусами и имела важное значение в развитии человеческой цивилизации. К числу позиционных систем счисления также относится современная десятичная система счисления, возникновение которой связано со счётом на пальцах.

В Европе такая система счисления появилась в средние века через итальянских купцов, в свою очередь получивших ее от арабов [10].

Под ПСС обычно понимается с-ричная система, определяемая целым числом c > 1, которое называется основанием. Любое целое число y без знака в c-ричной системе счисления представляется в виде конечной линейной комбинации степеней числа c: , где z_k – это целые числа (цифры), которые удовлетворят следующему неравенству [8]:

---

При этом коэффициенты с^k в такой записи числа называются весовыми коэффициентами. Значимость коэффициентов и соответствующих им цифр определяется номером разряда k. Как правило, в записи ненулевых чисел начальные нули опускаются.

Обычно число y записывают в виде последовательности его c-ричных цифр, перечисляемых слева направо по убыванию старшинства разрядов [2, 8]:

y=z_n-2z_n-1….z₀.

К примеру, число тридцать три представляется в десятичной системе счисления в виде: 33₁₀=3*10¹+3*10⁰.

Часто употребляемыми в настоящее время ПСС являются следующие [2]:

1. ПСС с основанием два – в информатике, дискретной математике и программировании;
2. ПСС с основанием три;
3. ПСС с основанием восемь;
4. ПСС с основанием десять – в обыденной жизни людей;
5. ПСС с основанием двенадцать;
6. ПСС с основанием шестнадцать – в программировании;
7. ПСС с основанием двадцать;
8. ПСС с основанием шестьдесят – при определении единиц измерения времени, углов, координат и т.д.

В ПСС с ростом основания количество разрядов (используемых при записи цифр) уменьшается. [2, 10, 7]

1.2 Особенности 16-ричной системы счисления

Шестнадцатеричная система счисления относится к классу ПСС по основанию 16. При этом цифрами в данной системе счисления используются цифры (0…9) и буквы (A…F), которые имеют значения: A – 10₁₀, B – 11₁₀, C – 12₁₀, D – 13₁₀, E – 14₁₀, F 15₁₀ соответственно [4, 9].

Шестнадцатеричная ПСС довольно часто используется в низкоуровневом программировании, а также при написании компьютерной документации, так как в современных персональных ЭВМ минимальной адресуемой единицей памяти является байт (8 бит), значения которого удобно записывать двумя шестнадцатеричными цифрами. Подобное обозначение было использовано в системе IBM/360, в то время как в документации других компьютерных систем использовали восьмеричную систему счисления (PDP-11, БЭСМ-6). Также в стандарте Unicode номер символа записывают в шестнадцатеричном виде, при этом используя не менее 4 цифр (при необходимости – с ведущими нулями) [4, 9].

Для перевода шестнадцатеричного числа в десятичное необходимо это число представить в виде суммы произведений степеней основания шестнадцатеричной системы счисления на соответствующие цифры в разрядах шестнадцатеричного числа.

---

Например, требуется перевести число «2A4»₁₆ из шестнадцатеричной ПСС в десятичную ПСС. В числе «2A4» три цифры. В соответствии с вышеуказанным правилом представим число «2A4» как сумму степеней с основанием шестнадцать:

2A4₁₆ = 2·16²+10·16¹+4·16⁰= 2·256+10·16+4·1 = 512+160+4 = 676.

При реализации указанных преобразований следует помнить, что в шестнадцатеричной ПСС: A=10; B=11; C=12; D=13; E=14; F=15.

Шестнадцатеричная ПСС получила развитие вследствие того, что двоичные числа очень трудно читать, особенно если они очень большие. При этом перевод двоичного числа в десятичное достаточно труден, а в шестнадцатеричное – нет, так как в последнем случае существует ускоренные методы перевода многозначного двоичного числа в шестнадцатеричную систему на основе разбиения его на тетрады, справа налево и замены каждой тетрады соответствующей шестнадцатеричной цифрой. Для перевода числа из шестнадцатеричной системы в двоичную нужно заменить каждую его цифру на соответствующую тетраду из нижеприведённой таблицы перевода (таблица 1.1). К примеру, для числа 010110100011₂ получим [9]:

010110100011₂ = 0101 1010 0011 = 5A3₁₆.

Чтобы перевести десятичное число в шестнадцатеричное, необходимо выполнить следующие действия:

1. Проверяем, не меньше ли 16 наше число: если да, то результат достигнут. Действительно, такое десятичное число необходимо лишь заменить соответствующей ему шестнадцатеричной цифрой из таблицы 1. Если же наше десятичное число больше 16, переходим к шагу 2.

2. Делим наше число «нацело» на 16 и запоминаем целочисленный остаток от этого деления. Результат этого деления снова сравниваем с 16. Если результат деления меньше 16, то его стоит тоже запомнить как последний из остатков.

3. Шаг 2 повторяем до тех пор, пока результат деления не будет меньше 16. Целочисленные остатки на всех этапах запоминаем. Они понадобятся в шаге 4.

4. Все остатки записываем в обратном порядке и заменяем в них числа от 10 до 15 шестнадцатеричными цифрами от A до F.

Таблица 1.1

К примеру, переведем десятичное число 89 в шестнадцатеричное. Оно больше 16, поэтому разделим его на 16. Частное равно 5 и 9 в остатке. 5 меньше 16, значит, деление прекращается и 5 запомним как последний остаток. То есть у нас есть два остатка: 9 и 5. Теперь их надо записать в обратном порядке, получаем: 89 = 59₁₆. Проверим, действительно ли 0×59 равно 89? Распишем его по привычной уже схеме: 59₁₆= 5×16¹ + 9×16⁰ = 5×16 + 9 = 89.

---

Действительно, получилось. Но в выбранном примере число 89 очень быстро закончилось, если так можно сказать. В противном случае деление потребовалось бы продолжить. Покажем это на более сложном примере. Возьмем число 3728: 3728 / 16 = 233 и 0 в остатке. Затем 233 / 16 = 14 и 9 в остатке. Результат этого деления равен 14, он меньше 16. Деление заканчиваем и запоминаем этот результат деления как последний остаток. Нам осталось лишь записать эти остатки в обратном порядке и заменить десятичное число 14 на шестнадцатеричную цифру E. Итак, искомое число E90.

На рисунке 1.1. представлен пример перевода десятичного числа 500 в шестнадцатеричную систему счисления на основе деления в столбик. [4, 2, 8, 9, 7]

Рис.1.1.

Результат перевода 1F4₁₆.

1.3 Арифметические операции с 16-ричными числами

Рассмотрим перечень необходимых для выполнения арифметических операций правил. Первое правило – нельзя забывать, что шестнадцатеричная система счисления есть ПСС, так как из этого правила следует важный момент: при сложении чисел нужно складывать только те цифры, которые находятся в одинаковых разрядах.

Рассмотрим сложение чисел в столбик в обычной десятичной ПСС и применим данный подход для сложения 16-ричных чисел.

Допустим, требуется сложить числа 134 и 59. Запишем данные числа друг под другом таким образом, чтобы разряды в них совпадали – единицы под единицами, десятки под десятками и так далее. При этом будем суммировать цифры одинаковых разрядов, начиная с единиц при этом двигаясь, справа налево:

134

+

59

193

При реализации данной арифметической операции помнить о том, что реализуется сложение десятичных чисел, у которых основанием является цифра 10, а сложение разрядов реализуется по очереди справа налево: 4 + 9 = 13. Полученный результат 13 является большим, чем основание 10. Если результат больше или равен основанию, необходимо из полученного результата это основание вычесть, то есть из 13 необходимо вычесть 10, а полученный результат необходимо записать под цифрами 4 и 9. При этом в левый разряд необходимо перенести единицу. В разряде с десятков мы складываем 3 + 5 и добавляем к ним перенесенный 1 десяток. Результат – 9. Результат меньше основания 10, поэтому под десятками просто записываем 9. Затем складываем сотни. Но единицу не с чем складывать, значит просто переносим ее в результат. Итак: 134 + 59 = 193.

---