Системы исчисления чисел, реализация перевода из одной системы в другую на С++

Содержание:

Введение

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

Предполагается, что на самых первых порах человек мог различать отдельные совокупности предметов – «один», «несколько», «много». При этом древние люди понимали, например, что три больше двух, а пять это уже много.

С развитием мозга человека, совокупности предметов стали более подробными – человек стал устойчиво различать числа больше трех, появились словесные понятия для чисел четыре, пять, шесть и так далее. Слово «семь» обозначало на тот момент большое, неисчисляемое количество предметов.

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

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

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

Вместе с усложнением чисел появилось понятие разрядности, которое известно нам сейчас. Заметки или зарубки наносились в определенном количестве, камешки собирались в кучки с определенным количеством камешков. В основу современной десятичной системы легла естественная емкость разряда – десять пальцев. В культурах и языках разных народов есть указание на числа 5, 10, 20 как формирующие название чисел, например, французское quatre-vingt, «четыре по двадцать» - восемьдесят.

Однако существовали и другие, обусловленные теми или иными факторами, основания – например, число сорок. Насекомое «сороконожка» имеет много ног, а «сорок сороков» обозначает очень большое число.

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

Глава 1. Позиционные и непозиционные системы исчисления

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

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

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

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

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

Глава 2. Двоичная система исчисления

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

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

В начале тридцатых годов прошлого столетия двоичная система легла в основу первых сложных вычислительных устройств, поскольку позволяла аппаратно реализовать различные действия. Ученые Франции, Германии, США и даже СССР шли в своих исследованиях в одном направлении, однако до определенного момента предпринимались попытки создавать вычислительные машины на логике, отличной от двоичной. Однако к середине сороковых годов, не без влияния А. Бекса, Х. Гольдстайна и, конечно же, Дж. Фон Неймана сформировалась устойчивая основа построения именно двоичных вычислительных машин и переход от десятичной арифметики к двоичной в сфере информационных технологий состоялся.

Глава 3. Восьмеричная система исчисления

Изначально использовалась для более короткой записи самого различного содержимого в представлении компьютера. Если двоичная система позволяет оперировать битами, то в случае с восьмеричной системой мы говорим о байте.

Алфавит восьмеричной системы состоит из восьми цифр – 0, 1, 2, 3, 4, 5, 6, 7, а так же, как и в двоичной системе, знаков плюс и минус для обозначения чисел больше и меньше нуля, а так же знака разделения целой и дробной части числа. Допустимо использование запятой или точки, в зависимости от региональных стандартов. Восьмеричная система позволяла писать программы в машинных кодах в более краткой форме по сравнению с двоичной системой, широко использовалась программистами пятидесятых-семидесятых годов. Однако со временем вычислительные машины перешли от восьмиразрядных систем к более сложным и в конечном счете в наши дни восьмеричная система используется только для хранения подходящей по размеру информации, например, прав доступа к файлу в Unix-системах, однако реализация различных функций перевода в эту систему есть в любом инженерном калькуляторе, а возможность работать с восьмеричными числами – практически в любом современном языке программирования.

Глава 4. Десятичная система исчисления

Известна нам с детства, используется практически по всему миру. Для записи используют современные «арабские» цифры 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, в обычной жизни используется для обозначения количества предметов, счета, обозначения сумм и так далее. Также возможна запись положительных и отрицательных числе при помощи знаков плюса и минуса. И точно также используется разделитель для целой и дробной части. Интересно, что некоторые стандарты допускают использование специального разделителя для отделения разрядов, кратных трём – тысяч, миллионов, миллиардов. Это искусственный способ, который во многом призван увеличить читаемость чисел, записанных в десятичной системе. Конечно же, с десятичной системой мы сталкиваемся чаще, чем с остальными, поэтому не будем подробно на ней останавливаться и перейдем к следующей.

Глава 5. Шестнадцатеричная система

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

В своем алфавите содержит привычные нам цифры от нуля до девяти из десятеричной системы, однако после этого еще идут буквы A, B, C, D, E, F, которые заменяют числа от 10 до 15. Точно также есть возможность записи отрицательных и положительных чисел, а так же разделения дробной и целой части при помощи разделителя.

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

Глава 6. Представление чисел в разных системах исчисления

Для наглядности представим таблицу, которая иллюстрирует, как одно и то же число будет выглядеть в разных системах исчисления:

Двоичная	Восьмеричная	Десятичная	Шестнадцатеричная
0	0	0	0
1	1	1	1
10	2	2	2
11	3	3	3
100	4	4	4
101	5	5	5
110	6	6	6
111	7	7	7
1000	10	8	8
1001	11	9	9
1010	12	10	A
1011	13	11	B
1100	14	12	C
1101	15	13	D
1110	16	14	E
1111	17	15	F
10000	20	16	10

Таблица 1. Представление чисел в разных системах исчисления

Данная таблица демонстрирует преимущества систем с большим основанием – обратите внимание, что в двоичной системе для числа 16 нужно уже пять разрядов, тогда как в шестнадцатеричной и восьмеричной системе для этого используются только два разряда! И чем больше число, тем более актуальна проблема его краткой записи и легкости чтения.

Глава 7. Как работает с числами ЭВМ?

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

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

Триггеры, объединенные в группы, используются для краткосрочного хранения чисел до, после и во время вычислений, а так же реализующие возможность произведения над хранимыми числами логических преобразований, называются регистрами. Регистры могут быть различных типов, в зависимости от модели и архитектуры процессора их может быть различное количество. Нам в контексте представления чисел интересны два типа регистров и соответствующее им представление – для работы с числами, у которых разделитель целой и дробной части всегда находится в одной и той же позиции и для работы с числами, позиция разделителя целой и дробной части в которых не является постоянной.

Глава 8. Числа с фиксированным разделителем целой и дробной части

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

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

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

Глава 9. Числа с нефиксированным разделителем целой и дробной части

Совершенно иначе хранятся числа с «плавающей запятой» - для того, чтобы не вычислять позицию разделителя, такие числа состоят из двух частей и так же хранятся – первая часть называется мантисса и обозначается m, вторая часть называется порядком p, который показывает степень, в которую возводится основание числа. Значащим элементом в этой ситуации является мантисса, основание, которое обозначается q, указывает на то, в какой системе исчисления находится число. Как правило, число (и мантисса, и порядок) задаются в двоичной форме. Мантисса указывается в виде правильной дроби, причем первый же значащий разряд идет непосредственно после разделителя целой и дробной части. Такое число называется нормализованным.

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

Глава 10. Прямой, обратный, дополнительный код

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

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

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

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

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

Десятичное число	Прямой код	Обратный код	Дополнительный код
-8	-	-	1000
-7	1111	1000	1001
-6	1110	1001	1010
-5	1101	1010	1011
-4	1100	1011	1110
-3	1011	1100	1101
-2	1010	1101	1110
-1	1001	1110	1111
0	1000 0000	1111 0000	0000
1	0001	0001	0001
2	0010	0010	0010
3	0011	0011	0011
4	0100	0100	0100
5	0101	0101	0101
6	0110	0110	0110
7	0111	0111	0111

Таблица 2. Представление положительных и отрицательных чисел.

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

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

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

Глава 11. Модифицированный код

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

Для кодирования в случае с модифицированными кодами применяются два разряда для кодирования знаков числа, причем в разряды пишутся 11 для знака «минус» и 00 для знака «плюс».

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

Переполнение разрядов может быть обработано следующим образом: при попадании в разряд знака 01 мы можем говорить о переполнении в положительную сторону, а в случае с 10 в разряде можно говорить о переполнении в отрицательную сторону. Старший знаковый разряд указывает на истинный знак в этом случае, а младший содержит «переполненную» значащую цифру числа.

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

Глава 12. Перевод двоичных чисел в десятичные

При представлении двоичных чисел принято говорить о «весе» числа – показателе степени основания системы. Вес помогает ориентироваться в размерности чисел, представленных в определенном количестве разрядов, а так же, конечно, помогает переводить числа из двоичной системы в десятичную.

Для осуществления перевода мы должны взять сумму всех цифр числа, умноженных на их вес в соответствии с разрядом. Например, переведем число (1011,1)₂ из двоичной системы в десятичную:

(1011,1)₂=1*2³+0*2²+1*2¹+1*2⁰+1*2^-1=8+2+1+1/2=11,5

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

Глава 13. Перевод десятичных чисел в двоичные

Обратное преобразование десятичного числа в двоичное можно сделать несколькими способами.

Широко применяется для перевода целых чисел из десятичной системы в двоичную метод деления. Он очень прост – мы делим исходное число на два «нацело», если у нас остается остаток единица, то мы записываем в младший разряд единицу, если нет – то ноль, а потом снова делим на два, пока не достигнем нуля или двойки в остатке, а исходное число будет уже невозможно разделить на два. Например, переведем в двоичный код число 150:

150\2=75 (остаток 0)

75\2=37 (остаток 1)

37\2=18 (остаток 1)

18\2=9 (остаток 0)

9\2=4 (остаток 1)

4\2=2 (остаток 0)

2\2=1 (остаток 0)

В итоге, записывая результат от старшего разряда к младшему, взяв в старший разряд результат последнего выражения, получаем:

150₁₀=10010110₂

Особенно наглядно этот способ выглядит при выполнении деления в столбик.

Для десятичных дробей меньше единицы применяется похожая методика, только вместо деления мы применяем умножение, при этом наполняем разряды единицами и нулями, исходя из значения результата умножения на два – если результат больше единицы, то мы берем единицу, если меньше – то ноль, в следующем действии используем только дробную часть, отбрасывая целую вне зависимости от ее значения. Например, возьмем число 0,625 в десятичной системе и переведем в двоичную систему:

0,625*2=1,25 (записываем 1)

0,25*2=0,5 (записываем 0)

0,5*2=1,0 (записываем 1)

0,0*2=0 (записываем 0)

Получаем в итоге: 0,625₁₀=0,101₂

Глава 14. Перевод в другие системы исчисления

Как вы уже, наверное, догадались, перевод в другие системы исчисления осуществляется по аналогии с двоичной системой исчисления. Например, для перевода в шестнадцатеричную систему исчисления мы будем использовать при делении или умножении основание системы – 16, а при переводе обратно в качестве весов будут использоваться основания системы с соответствующим показателем степени.

Существуют методы перевода между системами исчисления напрямую, например, из двоичной в шестнадцатеричную, но на практике чаще всего приходится переводить число в десятичную систему и только потом – в систему с желаемым основанием.

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

100100101101₂=1001 0010 1101₂=92D₁₆

Обратно это тоже работает:

EDA₁₆=E D A₁₆=11101101101₂

Глава 15. Постановка задачи

Теперь, когда мы достаточно хорошо усвоили теорию, мы можем использовать полученные знания на практике. Реализуем алгоритмы, о которых мы говорили, написав программу перевода чисел из одной из изученных систем – двоичной, восьмеричной, десятичной или шестнадцатеричной системы в систему с основаниями 2, 8, 10 или 16. Данная программа позволит в полной мере показать уровень усвоения материала, а также может служить калькулятором, позволяющим оперативно проводить такие вычисления.

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

Глава 16. Среда выполнения и методика тестирования программы.

Программа должна компилироваться компилятором gcc и выполняться в среде операционной системы Linux.

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

Исходное число	Основание результата	Ожидаемый результат	Фактический результат
10D	2	1010B	1010B
1001B	16	9H	9H
137O	10	95D	95D
EDAAH	8	166625O	166625O
10.5D	2	1010.1B	111110011B
123B	10	Error	11D
TEST	10	Error	Error
101B	20	Error	Error

Таблица 3. Результат тестирования программы.

Как видите, программа нуждается в доработке – она не обрабатывает дробные числа, а так же не следит за корректностью вводимых пользователем значений – можно ввести десятичное число и выдать его за число с основанием 2. Однако ошибки, связанные с вводом нечисловых значений в качестве исходного числа, а также незаданного в условии основания проверяются и выдают запланированный результат. На основе данного отчета можно подготовить задание на модернизацию программы.

Заключительная часть

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

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

Мы составили спецификацию будущей программы, определили условия, при которых она должна выполняться, после чего реализовали алгоритм в виде кода на языке С++, скомпилировали и выполнили тесты. По результатам тестов сделаны выводы относительно уровня написанной программы.

Библиографический список

А.С. Грошев – Информатика: Учебник для вузов / А.С. Грошев. – Архангельск, Архангельский государственный технический университет, 2010. – 470 с.

С. Симонович – Информатика. Базовый курс. Учебник для вузов / С. Симонович. – Санкт-Петербург, Питер, 2015. – 640 с.

Приложение 1. Исходный код программы

#include <string>

#include <vector>

#include <iostream>

#include <cmath>

using namespace std;

size_t getnumber(const string& in, size_t base) {

string literals="0123456789ABCDEF";

size_t n=0;

for(size_t i=0;i<in.length();i++)

{

size_t j=in.length()-1-i;

size_t m=literals.find(in[j]);

n+=m*(size_t)pow((double)base, (double)i);

}

return n;

}

string convert(size_t in, size_t base) {

string literals="0123456789ABCDEF";

string out;

while(in) {

size_t n=in%base;

out.insert(0, 1, literals[n]);

in/=base;

}

return out;

}

string convert(const string& val, size_t from_base, size_t to_base) {

return convert(getnumber(val, from_base), to_base);

}

string convertation(string val, size_t to_base) {

char base='';

char type=val[val.length()-1];

val.resize(val.length()-1);

switch(to_base) {

case 2:

base='B';

break;

case 16:

base='H';

break;

case 8:

base='O';

break;

case 10:

base='D';

break;

default:

cout<<"Ошибка! Некорректно или не указано значение основания исходного числа!"<<endl;

break;

}

switch(type) {

case 'B':

return convert(val, 2, to_base)+base;

break;

case 'H':

return convert(val, 16, to_base)+base;

break;

case 'O':

return convert(val, 8, to_base)+base;

break;

case 'D':

return convert(val, 10, to_base)+base;

break;

default:

cout<<"Ошибка! Некорректно или не указано значение основания результата!"<<endl;

break;

}

return "";

}

int main() {

string n;

int s;

cout << "Введите число с указанием изначальной системы счисления (B,O,D,H): " << endl;

cin >> n;

cout << "Введите основание системы для вывода результата: " << endl;

cin >> s;

cout<<convertation(n, s)<<endl;

}