Непозиционные системы счисления

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

Уже в эпоху палеолита люди стремились группировать точки, полосы и насечки по 3,4,5, или 7. Такая группировка облегчала счет. В древности люди считали на пальцах, поэтому предметы стали группировать по 5 или 10. В дальнейшем десяток десятков получил особое название, десяток сотен - свое название. Для удобства записи числа стали обозначать особыми знаками. Поскольку в такой записи положение знака не играет роли, подобные системы счисления стали называть непозиционными. Непозиционные системы счисления использовали древние египтяне, греки и римляне. Непозиционные системы счисления были более или менее пригодны для выполнения операций сложения и вычитания, но совсем не удобны для умножения и деления.

Чтобы облегчить работу, использовали счетные доски – абаки.

Позиционные системы счисления. Десятичная система счисления

В позиционных системах счисления один и тот же числовой знак (цифра) в записи числа имеет различные значения в зависимости от того места (разряда), где он расположен.

К позиционной шестидесятеричной системе перешли вавилоняне. Долгое время в вавилонской системе счета не было нуля, т. е. знака для пропущенного разряда. Сначала это не создавало неудобств, но когда стали составлять обширные математические и астрономические таблицы, возникла необходимость в таком знаке. Следы вавилонской системы счисления сохранились до наших дней в порядке счета времени (1 ч=60 мин. , 1 мин. =60 сек. ).

В V1 в. , точнее в 595г. индийцы создали способ записи, использующий лишь 9 цифр. Вместо нуля оставляли пустое место, а позднее ставили точку или маленький кружок. Особый знак для нуля появился в 1Х в. были выработаны правила выполнения арифметических операций над числами в десятичной системе счисления, не требовавшие использования абака, и этот способ записи распространился по всему миру. О десятичной системе счисления подробно рассказал среднеазиатский математик аль - Хорезми. Поскольку он написал свой труд на арабском языке, то системе в Европе дали неправильное название – «арабская».

Позиционные системы с произвольным основанием.

Мы привыкли к десятичной системе счисления. Компьютеру как нельзя лучше подходит двоичная система. Но иногда могут оказаться удобными системы с другими основаниями. Счёт на дюжины прекрасный тому пример. Здесь числовая база – степени числа 12.

В общем же случае представить произвольное число N в системе счисления с заданным основанием d означает записать его в виде где d – любое целое число, большее единицы. Коэффициенты a0, а1, ,аn называются цифрами в d – ичной записи N. Они могут принимать лишь d значений: 0,или 1, или 2, , или d-1. Заметим, что в случае d > 10 придётся придумывать новые символы для цифр.

Для нахождения цифр числа по заданному числу N и основанию d можно воспользоваться следующим способом: сначала находят самое большое базовое число , не превосходящее N. Затем число N делят на d, в результате чего получают неполное частное an и остаток r n-1, т. е.

Остаток r n-1 уже меньше базового числа , поэтому делим r n-1 на d! И получаем неполное частное an-1 и остаток r n-2:

Поступая подобным образом и далее, в конце концов «выберем» число до конца, получив попутно набор цифр an an-1, a1 a0.

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

Отсюда видно, что цифры an an-1, a1 a0 могут быть найдены последовательно, начиная с младшего разряда, в результате следушего многошагового процесса: a0 равно остатку то деления N на d; a1 равно остатку от деления на d неполного частного, полученного на предыдущем шаге; an равно остатку от деления на d неполного частного, полученного на предыдущем шаге.

То. Что число N в d-ичной системе счисления выражается цифрами an an-1, a1 a0, записывается так:

Например: 26700 = (110100001001100)2 = (1323300)5.

Положительным рациональным числом (обыкновенной положительной дробью) называется число, которое может быть записано в виде

Где p, q-натуральные числа. Число p называется числителем дроби, а число q-ее знаменателем.

Мы знаем, что дробь не изменится, если ее числитель и знаменатель умножить на одно и то же натуральное число n; другими словами, для любого натурального числа n справедливо равенство

Если числа p и q не имеют общих простых делителей, то дробь называется несократимой или правильной.

Если знаменатель q дроби равен 10 или 100, или 1000 и т. д. , то обыкновенную дробь можно записать в виде конечной десятичной дроби, каждая из которых называется десятичным разложением соответствующей обыкновенной дроби.

Очевидно также, что всякая конечная десятичная дробь может быть записана в виде обыкновенной дроби , где p-натуральное число, а q-некоторая степень числа 10.

Если знаменатель q обыкновенной дроби есть некоторая степень числа 10, то эта дробь может быть разложена в конечную десятичную дробь. Верно и обратное утверждение: конечная десятичная дробь представляет собой десятичное разложение обыкновенной дроби, знаменатель которой есть некоторая степень числа 10.

Восьмеричная система счисления

Восьмери́чная систе́ма счисле́ния — позиционная целочисленная система счисления с основанием 8. Для представления чисел в ней используются цифры 0 до 7.

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

Если мы обращаемся к восьмеричной системе счисления, то это означает, что можно использовать гораздо больше цифр, чем это принято в двоичной, но меньше, чем в десятичной, а именно можно оперировать восемью цифрами: 0, 1, 2, 3, 4, 5, 6, 7 — и не более.

Логика конвертирования десятичных чисел в восьмеричные (кодирование в восьмеричную систему счисления) совершенно идентична приведенной выше.

Более подробная информация — в разд. "Запись целых чисел в двоичной системе счисления" данной главы.

Действительно, в определенный момент цифры заканчиваются (наступает "кризис переходного периода").

Десятичное число "8" становится восьмеричным числом "10" ("восьмеричной десяткой"). Число "9" будет восьмеричным числом "11", число "10" — восьмеричным числом "12". И так далее до десятичного числа "15", которое в восьмеричном виде равно числу "17". А дальше?

Цифры снова кончились. Как будет представлено десятичное число "16" в восьмеричной системе счисления?

178 + 1 =. , но сумма "78 + 1" равняется "10" в восьмеричной системе счисления, а, следовательно, восьмеричный "десяток" необходимо складывать с "десятком", уже имеющимся, т. е. получается сумма, присутствующая в восьмеричной системе: "1 + 1 = 2". В результате получается, что

178 + 1 = 208.

Дальше — восьмеричное число "21" и т. п. , вплоть до восьмеричного числа "77". И только после этого будет восьмеричная "сотня".

Представим эту информацию в виде таблицы (табл. 4. 4).

Таблица 4. 4. Соответствие десятичных и восьмеричных чисел

Десятичные числа Восьмеричные числа Десятичные числа Восьмеричные числа

0-7 0-7 25-63 31-77

8 10 64 100

9-15 11-17 128 200

16 20 256 400

17-23 21-27 512 1000

24 30 1024 2000

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

Перевод чисел из одной позиционной системы в другую

Система счисления - это определенный способ записи чисел и соответствующие ему правила действия над числами.

Системы счисления бывают позиционными и непозиционными.

В позиционной системе счисления величина, которую обозначает цифра в записи числа, зависит от позиции цифры в этом числе. Совокупность различных цифр, используемых в позиционной системе счисления для записи чисел, называется алфавитом системы счисления. Для представления цифр больше 10 используют латинские буквы (А=10, В=11). Основание системы счисления - это размер алфавита. Число в позиционной системе можно представить в виде суммы произведений составляющих его цифр на соответствующие степени основания системы.

Любая позиционная система вводится следующим образом. Выбирается основание р — целое число и алфавит из р цифр: О, 1, 2,. , р-1. Тогда любое число Х в этой системе представляется в виде суммы произведений:

Х = аn*рn + an-1*pn-1 + + a0*p0

Здесь Х — это число в системе с основанием p, имеющее n+1 цифру в целой части — это цифры из алфавита системы.

Перевод чисел из одной позиционной системы в другую

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

В позиционных системах значение записи целого числа определяется по следующему правилу: пусть a na n-1a n-2a 1a 0 — запись числа A, а i – цифры, тогда

A = a n·pn+a n-1·pn-1 +a n-2·pn-2+. +a 1·p1+ a0·p0        (1), где p — целое число большее 1, которое называется основанием системы счисления

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

Пример:

1) Десятичная система p = 10 цифры: 0,1,2,3,4,5,6,7,8,9 число 5735 = 5·103+7·102+3·101+8·100

2) Троичная система p = 3 цифры: 0,1,2 число 2013 = 2·32+0·31+1·30

Замечание: нижним индексом в записи числа обозначается основание системы счисления, в которой записано число. Для десятичной системы счисления индекс можно не писать.

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

Во всех позиционных системах для записи отрицательных чисел так же как и в десятичной системе используется знак ‘–‘.   Для отделения целой части числа от дробной используется запятая. Значение записи a na n-1a n-2a 1a 0, a -1 a -2a m-2 a m-1a m числа A определяется по формуле, являющейся обобщением формулы (1):

A = an·pn+a n-1·p n-1+a n-2·p n-2++a1·p1+a0·p0+a-1·p-1+a -2·p-2++am-2·p–(m–2)+am–1·p–(m–1)+amp–m     (2),

Пример:

75,6 = 7·101+5·100+6·10–1

 –2,3145 = –(2·50+3·5–1+1·5–2+4·5–3)

Перевод чисел из произвольной системы счисления в десятичную:

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

Перевод чисел из произвольной системы счисления в десятичную выполняется непосредственным вычислением по формуле (1) для целых и формуле (2) для дробных чисел.

Перевод чисел из десятичной системы счисления в произвольную.

Перевести число из десятичной системы в систему с основанием p – значит найти коэффициенты в формуле (2). Иногда это легко сделать простым подбором. Например, пусть нужно перевести число 23,5 в восьмеричную систему. Нетрудно заметить, что 23,5 = 16+7+0,5 = 2·8+7+4/8 = 2·81+7·80+4·8–1 =27,48. Понятно, что не всегда ответ столь очевиден. В общем случае применяется способ перевода отдельно  целой и дробной частей числа.  

Для перевода целых чисел применяется следующий алгоритм (полученный на основании формулы (1)):

1. Найдем частное и остаток от деления числа на p. Остаток  будет очередной цифрой ai (j=0,1,2 ) записи числа в новой системе счисления.

2. Если частное равно нулю, то перевод числа закончен, иначе применяем к частному пункт 1.

Замечание 1. Цифры ai в записи числа нумеруются справа налево.

Замечание 2. Если p>10, то необходимо ввести обозначения для цифр с числовыми значениями, большими или равными 10.

Пример:

Перевести число 165 в семеричную систему счисления.

165:7 = 23 (остаток 4) => a0 = 4

23:7 = 3 (остаток 2) => a1 = 2

3:7 = 0 (остаток 3) => a2 = 3

Выпишем результат: a2a1a0, т. е. 3247.

Выполнив проверку по формуле (1), убедимся в правильности перевода:

3247=3·72+2·71+4·70=3·49+2·7+4 = 147+14+4 = 165.

Для перевода дробных частей чисел применяется алгоритм, полученный на основании формулы (2):

1. Умножим дробную часть числа на p.

2. Целая часть результата будет очередной цифрой am (m = –1,–2, –3 ) записи  числа в новой системе счисления. Если дробная часть результата равна нулю, то перевод числа закончен, иначе применяем к ней пункт 1.

Замечание 1.   Цифры am в записи числа располагаются слева направо в порядке возрастания абсолютного значения m.

Замечание 2.   Обычно количество дробных разрядов в новой записи числа ограничивается заранее. Это позволяет выполнить приближенный перевод с заданной точностью. В случае бесконечных дробей такое ограничение обеспечивает конечность алгоритма.

Пример 1:

Перевести число 0,625 в двоичную систему счисления.

 0,625·2 = 1,25 (целая часть 1) => a-1 =1

0,25·2  = 0,5 (целая часть 0) => a-2 = 0

0,5·2 = 1,00 (целая часть 1) => a-3 = 1

Итак, 0,62510 = 0,1012

Выполнив проверку по формуле (2), убедимся в правильности перевода:

0,1012=1·2-1+0·2-2+1·2-3=1/2+1/8 = 0,5+0,125 = 0,625.

 Пример 2:

Перевести число 0,165 в четверичную систему счисления, ограничившись четырьмя четверичными разрядами.

0,165·4 = 0,66 (целая часть 0) => a-1=0

0,66·4  = 2,64 (целая часть 2) => a-2= 2

0,64·4 = 2,56 (целая часть 2) => a-3= 2

0,56·4 = 2,24 (целая часть 2) => a-4= 2

Итак, 0,16510 ” 0,02224

Выполним обратный перевод, чтобы убедиться, что абсолютная погрешность не превышает 4–4:

0,02224 = 0·4-1+2·4-2+2·4-3+2·4-4= 2/16+2/64+2/256 = 1/8+1/32+1/128 = 21/128 = 0,1640625

0,1640625–0,165 = 0,00094 < 4–4 = 0,00390625

Перевод чисел из одной произвольной системы в другую

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

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

Пусть p и q – основания двух систем счисления. Будем называть эти системы системами счисления с кратными основаниями, если p = qn или q = pn, где n – натуральное число. Так, например, системы счисления с основаниями 2 и 8 являются системами счисления с кратными основаниями.

Пусть p = qn и требуется перевести число из системы счисления с основанием q в систему счисления с основанием p.   Разобьем целую и дробную части записи числа на группы по n последовательно записанных цифр влево и вправо от запятой. Если количество цифр в записи целой части  числа не кратно n, то надо дописать слева соответствующее количество нулей. Если количество цифр в записи дробной части  числа не кратно n, то нули дописываются справа. Каждая такая группа цифр числа в старой системе счисления будет соответствовать одной цифре числа в новой системе счисления.

Пример:

Переведем 1100001,1112  в четверичную систему счисления.

Дописав нули и выделив пары цифр, получим 01100001,11102.

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

012=110=14

102=210=24

002=010=04

012=110=14

112=310=34

102=210=24

Итак,  1100001,1112 = 01100001,11102 = 1201,324.

Пусть теперь требуется выполнить перевод из системы с большим основанием q, в систему с меньшим основанием p, т. е. q = pn. В этом случае одной цифре числа в старой системе счисления соответствует n цифр числа в новой системе счисления.

Пример: Выполним проверку предыдущего перевода числа.

1201,324 = 1100001,11102=1100001,1112

В шестнадцатеричной системе есть цифры с числовыми значениями 10,11,12, 13,14,15. Для их обозначения используют первые шесть  букв латинского алфавита A, B, C, D, E, F.

Приведем таблицу чисел от 0 до 16, записанных в системах счисления с основаниями 10, 2, 8 и 16.

Число в десятичной системе счисления  0   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 В восьмеричной  0  1  2 3 4 5 6 7 10 11 12 13 14 15 16 17 20 В двоичной  0  1 10 11 100 101 110 111 1000 1001 1010 1011 1100 1101 1110 1111 10000 В шестнадцатеричной  0  1 2 3 4 5 6 7 8 9 A B C D E F 10  Для записи шестнадцатеричных цифр можно использовать также строчные латинские буквы a-f.

Пример: Переведем число 110101001010101010100,112 в шестнадцатеричную систему счисления.

Воспользуемся кратностью оснований систем счисления (16=24). Сгруппируем цифры по четыре, дописав, слева и справа  нужное количество нулей

000110101001010101010100,11002 и, сверяясь с  таблицей, получим: 1A9554,C16

В какой системе счисления лучше записывать числа – это вопрос удобства и традиций. С технической точки зрения, в ЭВМ удобно использовать двоичную систему, так как в ней для записи числа используются только  две цифры 0 и 1, которые можно представить двумя легко различимыми состояниями “нет сигнала ” и “есть сигнал”.

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

Двоичная система счисления. Бит и байт. Сегментация памяти.

Рассмотрим, как в памяти компьютера хранятся данные.

Вообще, как компьютер может хранить, например, слово "диск"? Главный принцип - намагничивание и размагничивание одной дорожки (назовем ее так). Одна микросхема памяти - это, грубо говоря, огромное количество дорожек. Сейчас попробуем разобраться. Например: нуль будет обозначаться как 0000 (четыре нуля), один 0001, два 0010,

(т. е. правую единицу заменяем на 0 и вторую устанавливаем в 1).

Далее так: три 0011 четыре 0100 пять 0101 шесть 0110 семь 0111 восемь 1000 девять 1001 и т. д.

Уловили принцип? "0" и "1" - это т. н. биты. Один бит, как вы уже заметили, может быть нулем или единицей, т. е. размагничена или намагничена та или иная дорожка ("0" и "1" это условное обозначение). Если еще присмотреться, то можно заметить, что каждый следующий установленный бит (начиная справа) увеличивает число в два раза: 0001 в нашем примере = 1; 0010 два; 0100 четыре; 1000 восемь и т. д. Это и есть т. н. двоичная форма представления данных.

Т. о. чтобы обозначить числа от 0 до 9 нам нужно четыре бита (хоть они и не до конца использованы. Можно было бы продолжить: десять 1010, одиннадцать 1011 , пятнадцать 1111).

Компьютер хранит данные в памяти именно так. Для обозначения какого-нибудь символа (цифры, буквы, запятой, точки. ) в компьютере используется определенное количество бит. Компьютер "распознает" 256 (от 0 до 255) различных символов по их коду. Этого достаточно, чтобы вместить все цифры (0 - 9), буквы латинского алфавита (a - z, A - Z), русского (а - я, А - Я), а также другие символы. Для представления символа с максимально возможным кодом (255) нужно 8 бит. Эти 8 бит называются байтом. Т. о. один любой символ - это всегда 1 байт.

Т. о. слово "диск" будет занимать 4 байта или 4*8 = 32 бита. Как вы уже поняли, компьютер хранит в памяти не сами буквы этого слова, а последовательность "единичек" и "ноликов". "Почему же тогда на экране мы видим текст, а не "единички-нолики"? - спросите вы. Чтобы удовлетворить ваше любопытство, я забегу немного вперед и скажу, что всю работу по выводу самого символа на экран (а не битов) выполняет видеокарта (видеоадаптер), которая находится в вашем компьютере. И если бы ее не было, то мы, естественно, ничего бы не видели, что у нас творится на экране.

В Ассемблере после двоичного числа всегда должна стоять буква "b". Это нужно для того, чтобы при ассемблировании нашей программы Ассемблер смог отличать десятичные, шестнадцатеричные и двоичные числа. Например: 10 - это "десять", 10h - это "шестнадцать" а 10b - это "два" в десятичной системе.

Т. о. в регистры можно загружать двоичные, десятичные и шестнадцатеричные числа.

Например: mov ax,20 mov bh,10100b mov cl,14h

В результате в регистрах AX, BH и CL будет находится одно и тоже число, только загружаем мы его в разных системах. Компьютер же будет хранить его в двоичном формате (как в регистре BH).

Итак, подведем итог. В компьютере вся информация хранится в двоичном формате (двоичной системе) примерно в таком виде: 10101110 10010010 01111010 11100101 (естественно, без пробелов. Для удобства я разделили биты по группам). Восемь бит - это один байт. Один символ занимает один байт, т. е. восемь бит. По-моему, ничего сложного. Очень важно уяснить данную тему, так как мы будем постоянно пользоваться двоичной системой, и вам необходимо знать ее на "отлично".

Зачем нужны различные позиционные системы?

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

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

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

Вычислительные устройства.

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

Русские счёты

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

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