Единичная система счисления

Необходимость в записи чисел стала возникать у людей еще в древности после того, как они научились считать. Свидетельством этого являются археологические находки в местах стойбищ первобытных людей, которые относятся к периоду палеолита ($10$-$11$ тыс. лет до н.э.). Изначально количество предметов изображали, используя определенные знаки: черточки, насечки, кружочки, нанесенные на камни, дерево или глину, а также узлы на веревках.

Рисунок 1.

Ученые эту систему записи чисел называют единичной (унарной) , поскольку число в ней образовано повторением одного знака, который символизирует единицу.

Недостатки системы:

при написании большого числа необходимо использовать большое количество палочек;

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

Позднее, чтобы облегчить счет, эти знаки люди стали объединять.

Пример 1

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

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

Вот некоторые примеры.

Древнеегипетская десятичная непозиционная система счисления

Данная система счисления появилась около 3000 лет до н.э. в результате того, что жители Древнего Египта придумали свою числовую систему, в которой при обозначении ключевых чисел $1$, $10$, $100$ и т.д. были использованы иероглифы, что было удобным при написании на глиняных дощечках, которые заменяли бумагу. Другие числа составлялись из них с помощью сложения. Сначала записывалось число высшего порядка, а затем низшего. Умножали и делили египтяне, последовательно удваивая числа. Каждая цифра могла повторяться до $9$ раз. Примеры чисел данной системы приведены ниже.

Рисунок 2.

Римская система счисления

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

$I$ (один палец) для числа $1$;

$V$ (раскрытая ладонь) для числа $5$;

$X$ (две сложенные ладони) для $10$;

для обозначения чисел $100$, $500$ и $1000$ использовались первые буквы соответствующих латинских слов (Сentum – сто, Demimille – половина тысячи, Мille – тысяча).

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

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

Число равно разности значений двух «цифр», если слева от большей стоит меньшая. В этом случае от значения большей отнимается значение меньшей. Вместе они образуют группу второго вида. При этом левая «цифра» может быть меньше правой максимально на $1$ порядок: перед $L(50)$ и $C(100$) из «младших» может стоять только $Х(10$), перед $D(500$) и $M(1000$) – только $C(100$), перед $V(5) – I(1)$.

Число равно сумме значений групп и «цифр», не вошедших в группы $1$ или $2$ вида.

Рисунок 3.

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

Алфавитные системы счисления

Данные системы счисления более совершенны. К ним относятся греческая, славянская, финикийская, еврейская и другие. В этих системах числа от $1$ до $9$, а также количество десятков (от $10$ до $90$), сотен (от $100$ до $900$) были обозначены буквами алфавита.

В древнегреческой алфавитной системе счисления числа $1, 2, ..., 9$ обозначались первыми девятью буквами греческого алфавита, и т.д. Для обозначения чисел $10, 20, ..., 90$ применялись следующие $9$ букв а для обозначения чисел $100, 200, ..., 900$ – последние $9$ букв.

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

Рисунок 4.

Замечание 1

Алфавитная система использовалась и в древней Руси. До конца $XVII$ века в качестве цифр использовались $27$ букв кириллицы.

Непозиционные системы счисления имеют ряд существенных недостатков:

Существует постоянная потребность введения новых знаков для записи больших чисел.

Невозможно представлять дробные и отрицательные числа.

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

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

Уже в эпоху палеолита люди стремились группировать точки, полосы и насечки по 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:

На практике определять 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". В результате получается, что

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

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

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

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

9-15 11-17 128 200

17-23 21-27 512 1000

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

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

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

В позиционной системе счисления величина, которую обозначает цифра в записи числа, зависит от позиции цифры в этом числе. Совокупность различных цифр, используемых в позиционной системе счисления для записи чисел, называется алфавитом системы счисления. Для представления цифр больше 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. Обычно количество дробных разрядов в новой записи числа ограничивается заранее. Это позволяет выполнить приближенный перевод с заданной точностью. В случае бесконечных дробей такое ограничение обеспечивает конечность алгоритма.

Перевести число 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.

Перевести число 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

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

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

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

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

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

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

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

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

Итак, 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).

Уловили принцип? "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 частей. На каждой такой части имеется зубец шестерёнки. Поворачиваясь вокруг своей оси, шестерёнка может останавливаться только в таких положениях, когда какой-либо её зубец устанавливается против окошка в корпусе арифмометра. На каждом зубце шестерёнки написана соответствующая цифра.

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

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

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

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

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

Наиболее употребительной оказалась индо-арабская десятичная система. Индийцы первыми использовали ноль для указания позиционной значимости величины в строке цифр. Эта система получила название десятичной, так как в ней десять цифр.

Различие между позиционной и непозиционной систем счисления легче всего понять на примере сравнения двух чисел. В позиционной системе счисления сравнение двух чисел происходит следующим образом: в рассматриваемых числах слева направо сравниваются цифры, стоящие в одинаковых позициях. Бoльшая цифра соответствует бoльшему значению числа. Например, для чисел 123 и 234, 1 меньше 2, поэтому число 234 больше, чем число 123. В непозиционной системе счисления это правило не действует. Примером этого может служить сравнение двух чисел IX и VI. Несмотря на то, что I меньше, чем V, число IX больше, чем число VI.

Основание системы счисления, в которой записано число, обычно обозначается нижним индексом. Например, 555 7 - число, записанное в семеричной системе счисления. Если число записано в десятичной системе, то основание, как правило, не указывается. Основание системы - это тоже число, и его указывают в обычной десятичной системе. Любое целое число в позиционной системе можно записать в форме многочлена:

Х s ={A n A n-1 A n-2 ...A 2 A 1 } s =A n ·S n-1 +A n-1 ·S n-2 +A n-2 ·S n-3 +...+A 2 ·S 1 +A 1 ·S 0

где S - основание системы счисления, А n - цифры числа, записанного в данной системе счисления, n - количество разрядов числа.

Так, например число 6293 10 запишется в форме многочлена следующим образом:

6293 10 =6·10 3 + 2·10 2 + 9·10 1 + 3·10 0

Примеры позиционных систем счисления:

· Двоичная (или система счисления с основанием 2) это положительная целочисленная позиционная (поместная) система счисления, позволяющая представить различные численные значения с помощью двух символов. Чаще всего это 0 и 1.

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

· Десятичная система счисления -- позиционная система счисления по целочисленному основанию 10. Наиболее распространённая система счисления в мире. Для записи чисел наиболее часто используются символы 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, называемые арабскими цифрами.

· Двенадцатеричная (широко использовалась в древности, в некоторых частных областях используется и сейчас) -- позиционная система счисления с целочисленным основанием 12. Используются цифры 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B. Некоторые народы Нигерии и Тибета до сих пор используют двенадцатеричную систему счисления, но отголоски ее можно найти практически в любой культуре. В русском языке есть слово "дюжина", в английском "dozen", в некоторых местах слово двенадцать употребляют вместо «десять», как круглое число, например, подождите 12 минут.

· Шестнадцатеричная (наиболее распространена в программировании, а также в шрифтах) -- позиционная система счисления по целочисленному основанию 16. Обычно в качестве шестнадцатеричных цифр используются десятичные цифры от 0 до 9 и латинские буквы от A до F для обозначения цифр от 10 до 15. Широко используется в низкоуровневом программировании и вообще в компьютерной документации, поскольку в современных компьютерах минимальной единицей памяти является 8-битный байт, значения которого удобно записывать двумя шестнадцатеричными цифрами.

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

Наибольший интерес при работе на ЭВМ представляют системы счисления с основаниями 2, 8 и 16. Этих систем счисления обычно хватает для полноценной работы как человека, так и вычислительной машины, однако иногда в силу различных обстоятельств все-таки приходится обращаться к другим системам счисления, например к троичной, семеричной или системе счисления по основанию 32.

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

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

Часто в информатике используют шестнадцатеричную систему, так как запись чисел в ней значительно короче записи чисел в двоичной системе. Может возникнуть вопрос: почему бы не использовать для записи очень больших чисел систему счисления, например по основанию 50? Для такой системы счисления необходимы 10 обычных цифр плюс 40 знаков, которые соответствовали бы числам от 10 до 49 и вряд ли кому-нибудь понравится работать с этими сорока знаками. Поэтому в реальной жизни системы счисления по основанию, большему 16, практически не используются.

Основные понятия

Система счисления - это совокупность правил записи чисел посредством конечного набора символов (цифр).

Системы счисления бывают:

• непозиционными (в этих системах значение цифры не зависит от ее позиции - положения в записи числа);
• позиционными (значение цифры зависит от позиции).

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

Примеры: унарная, римская, древнерусская и др.

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

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

p i = s i ,

Разряды числа нумеруются справа налево, причем младший разряд целой части (стоящий перед разделителем - запятой или точкой) имеет номер ноль. Разряды дробной части имеют отрицательные номера:

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

По определению веса разряда

p i = s i ,
где i - номер разряда, а s - основание системы счисления.

Тогда, обозначив цифры числа как a i , любое число, записанное в позиционной системе счисления, можем представить в виде:

x = a n s n + a n-1 s n-1 + ... + a 2 s 2 + a 1 s 1 + a 0 s 0 + a -1 s -1 + ...

Например, для системы счисления с основанием 4:

1302.2 4 = 1⋅4 3 + 3⋅4 2 + 0⋅4 1 + 2⋅4 0 + 2⋅4 -1

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

1302.2 4 = 1⋅4 3 + 3⋅4 2 + 0⋅4 1 + 2⋅4 0 + 2⋅4 -1 =
= 1⋅64 + 3⋅16 + 0⋅4 + 2⋅1 + 2⋅0,25 =
= 64 + 48 + 2 + 0,5 = 114,5

Таким образом, для перевода числа из любой системы счисления в десятичную следует:

1. пронумеровать разряды исходного числа;
2. записать сумму, слагаемые которой получаются как произведения очередной цифры на основание системы счисления, возведенное в степень, равную номеру разряда;
3. выполнить вычисления и записать полученный результат (указав основание новой системы счисления - 10).

Примеры:

Перевод из десятичной системы счисления

Вспомним пример перевода из системы счисления с основанием 4 в десятичную:

1302 4 = 1⋅4 3 + 3⋅4 2 + 0⋅4 1 + 2⋅4 0 = 114

Иначе это можно записать так:

114 = ((1 ⋅ 4 + 3) ⋅ 4 + 0) ⋅ 4 + 2 = 1302 4

Отсюда видно, что при делении 114 на 4 нацело в остатке должно остаться 2 - это младшая цифра при записи в четверичной системе. Частное же будет равно

(1 ⋅ 4 + 3) ⋅ 4 + 0

Деление его на 4 даст остаток - следующую цифру (0) и частное 1 ⋅ 4 + 3. Продолжая действия, получим аналогичным образом и оставшиеся цифры.

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

1. Выполнить последовательное деление с остатком исходного числа и каждого полученного частного на основание новой системы счисления.
2. Записать вычисленные остатки, начиная с последнего (т.е. в обратном порядке)

Примеры:

Системы счисления с кратными основаниями

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

Достаточно заменить каждый разряд шестнадцатеричной записи четырьмя (16=24 ) разрядами двоичной (и наоборот) по таблице.

шестнадцатеричная -> двоичная
A	3	2	E
1010	0011	0010	1110
двоичная -> шестнадцатеричная
(00)10	1010	0111	1101
2	A	7	D

Аналогично происходит и перевод между двоичной и восьмеричной системой, только разряд восьмеричной соответствует трем разрядам двоичной (8=2 3)

восьмеричная -> двоичная
	5	3	2	1
	101	011	010	001
двоичная -> восьмеричная
(0)10	101	001	111	101
2	5	1	7	5

Арифметика

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

Сложение

Двоичная система:

								(перенос)
1	0	0	1	1	0	1	1
	1	0	0	1	1	1	0
1	1	1	0	1	0	0	1
7	6	5	4	3	2	1	0	(номера разрядов)

В нулевом разряде: 1 + 0 = 0

В первом разряде: 1 + 1 = 2. 2 переносится в старший (2-й) разряд, обращаясь в единицу переноса. В первом разряде остается 2 - 2 = 0.

Во втором разряде: 0 + 1 + 1 (перенос) = 2; Переносим в старший разряд,

Продолжая вычисления, получим:

10011011 2 + 1001110 2 = 11101001 2

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

					(перенос)
3	4	2	6	1
	4	4	3	5
4	0	7	1	6
4	3	2	1	0	(номера разрядов)

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

34261 8 + 4435 8 = 40716 8

Шестнадцатеричная система:

					(перенос)
	A	3	9	1
	8	5	3	4
1	2	8	C	5
4	3	2	1	0	(номера разрядов)

A391 16 + 8534 16 = 128C5 16

Вычитание

Двоичная система:

								(перенос)
1	0	0	1	1	0	1	1
	1	0	0	1	1	1	0
	1	0	0	1	1	0	1
7	6	5	4	3	2	1	0	(номера разрядов)

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

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

Все системы счисления можно разделить на два класса: позиционные и непозиционные .

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

I (1), V(5), X(10), l(50), c(100), d(500), m(1000).

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

Все целые числа (до 5000) записываются с помощью повторения вышеприведенных цифр. При этом, если большая цифра стоит перед меньшей, то они складываются, если же меньшая стоит перед большей (в этом случае она не может повторяться), то меньшая вычитается из большей. Подряд одна и та же цифра ставится не более трех раз. Например, III(3), LIX(59), DLV(555), MCMXCVIII (1998).

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

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

Шестидесятиричная запись целых чисел не получила распространения за пределами ассиро-вавилонского царства, но шестидесятиричные дроби проникли далеко за эти пределы: в страны Среднего Востока, Средней Азии, в Северную Африку и Западную Европу. Они широко применялись, особенно в астрономии, вплоть до изобретения десятичных дробей. Следы шестидесятиричных дробей сохраняются и поныне в делении углового и дугового градуса (а также часа) на 60 минут и минуты на 60 секунд.

Позиционные системы счисления обладают большими преимуществами в наглядности представления чисел и в простоте выполнения арифметических операций. В позиционной системе счисления значение числа определяется не только набором входящих в него цифр, но и их местом (позицией) в последовательности цифр, изображающих это число. Примером позиционной системой счисления является десятичная система. Помимо десятичной существуют другие позиционные системы счисления, для записи чисел в различных системах счисления используется некоторое количество отличных друг от друга символов. Число таких символов в позиционной системе счисления называется основанием системы счисления и обозначается буквой q . В десятичной системе используется десять символов (цифр): 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, и основанием системы является число 10. В таблице 3.1 приведены наименования некоторых позиционных систем счисления и перечень цифр, из которых образуются в них числа.

Таблица 3.1.

Основание	Система счисления	Символы
	Двоичная
	Троичная
	Восьмиричная	0, 1, 2, 3, 4, 5, 6, 7
	Десятичная	0, 1, 2, 3, 4, 5, 6, 7, 8, 9
	Шестнадцатиричная	0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F

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

В общем случае в такой позиционной системе счисления с основанием q любое число X может быть представлено в виде полинома разложения (суммы произведений коэффициентов на степени основания системы счисления):

здесь q – основание системы счисления;
– запись числа в системе счисления по основаниюq ; – целые числа, меньшиеq ; n – число разрядов в целой части числа; m – число разрядов в дробной части числа.

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

В информатике применяют позиционные системы счисления с недесятичным основанием: двоичную, восьмиричную и шестнадцатиричную, т.е. системы счисления с основанием
, гдеk = 1, 3, 4.

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

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

Наиболее удобной для построения ЭВМ оказалась двоичная система счисления, т.е. система счисления, в которой используются только две цифры: 0 и 1, т.к. с технической точки зрения создать устройство с двумя состояниями проще, также упрощается различение этих состояний.

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