Системы исчисления

Цифры в нашей жизни

Современный человек в повседневной жизни постоянно сталкивается с числами и цифрами:

запоминает номера автобусов и телефонов,

в магазине подсчитывает стоимость покупок,

ведет свой семейный бюджет в рублях и копейках и т.д.

Числа и цифры с нами везде!

Интересно, что знал человек о числах две тысячи лет назад? А пять тысяч лет назад?

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

Что же понимается под словом «число»?

Первоначально понятие отвлеченного числа отсутствовало, число было «привязано» к тем предметам, которые пересчитывали. Отвлеченное понятие натурального числ появляется вместе с развитием письменности.

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

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

Сегодня человечество для записи чисел использует в основном десятичную систему счисления.

Что же такое - система счисления?

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

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

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

Чтобы определить число, недостаточно знать тип и алфавит системы исчисления. Для этого необходимо еще использовать правила, которые позволяют по значениям цифр установить значение числа. Простейшим способом записи натурального числа является изображение его с помощью соответствующего количества палочек или черточек. Таким способом можно обозначить небольшие чисел. Следующим шагом было изобретение специальных символов (цифр). В непозиционной системе каждый знак в записи независимо от места означает одно и то же число. Хорошо известным примером непозиционной системы исчисления является римская система, в которой роль цифр играют буквы алфавита: І - один, V - пять, Х - десять, С - сто, L - пятьдесят, D -пятьсот, М - тысяча. Например, 324 = СССХХІ. В непозиционной системе исчисления арифметические операции выполнять неудобно и сложно.

Базис, алфавит, основание

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

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

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

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

При рассмотрении позиционных систем чрезвычайно важным является понятие базиса системы счисления.

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

Выпишем базисы некоторых традиционных систем счисления.

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

1, 10, 102, 103, 104, …, 10n,…

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

1, 2, 22, 23, 24, …, 2n,…

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

1, 8, 82, 83, 84, …, 8n,…

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

…, P-2, P-l, 1, P, P2, P3, …, Pn,..,.

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

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

Выпишем базисы некоторых нетрадиционных систем счисления.

Факториальная система:

1!, 2!, 3!, 4!,..,, (п-1)!, п!, …

Фибоначчиева система:

1, 2, 3, 5, 8, 13, 21, …

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

традиционные Р-ичные;

нетрадиционные;

смешанные Р-Q-ичные.

Традиционные позиционные системы счисления с основанием Р называются Р-ичными.

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

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

Общеупотребительной формой записи числа является сокращенная форма записи разложения по степеням основы системы исчисления, например

130678=1*105+3*104+0*103+6*102+7*101+8

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

Проблема выбора системы исчисления для представления чисел в памяти компьютера имеет большое практическое значение. В случае ее выбора обычно учитываются такие требования, как надежность представления чисел при использовании физических элементов, экономичность (использование таких систем исчисления, в которых количество элементов для представления чисел из некоторого диапазона было бы минимальном). Для изображения целых чисел от 1 до 999 в десятичной системе достаточно трех разрядов, то есть трех элементов. Поскольку каждый элемент может находиться в десяти состояниях, то общее количество состояний - 30, в двоичной системе исчисления: 99910=11111002, необходимое количество состояний - 20 (индекс внизу числа - основа системы исчисления).

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

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

Таблица 1

Для отладки программ и в других ситуациях в программировании актуальной является проблема перевода чисел из одной позиционной системы исчисления в другую. Если основа новой системы исчисления равняется некоторой степени старой системы исчисления, то алгоритм перевода очень простой: нужно сгруппировать справа налево разряды в количестве, равном показателю степени и заменить эту группу разрядов соответствующим символом новой системы исчисления. Этим алгоритмом удобно пользоваться при переводе числа из двоичной системы исчисления в восьмиричную или шестнадцатиричную. Например, 101102=10 110=268, 10111002=101 1100=5C8

Перевод чисел из восьмиричной или шестнадцатиричной систем исчисления в двоичную происходит по обратному правилу: один символ старой системы исчисления заменяется группой разрядов новой системы исчисления, в количестве равном показателю степени новой системы исчисления. Например, 4728=100 111 010=1001110102, B516=1011 0101=101101012

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

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

1. Для перевода чисел из системы исчисления с основой p в систему исчисления с основой q, используя арифметику новой системы исчисления с основой q, нужно записать коэффициенты разложения, основы степеней и показатели степеней в системе с основой q и выполнить все действия в этой самой системе. Очевидно, что это правило удобно при переводе в десятичную систему исчисления. Например:

из шестнадцатиричной в десятичную:

92C816=9*10163+2*10162+C*10161+8*10160= 9*16103+2*16102+12*16101+8*16100=37576

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

7358=7*1082+3*1081+5*1080= 7*8102+3*8101+5*8100=47710

из двоичной в десятичную:

1101001012=1*1028+1*1027+ 0*1026+1*1025+0*1024+0*1023+ 1*1022+0*1021+1*1020= 1*2108+1*2107+0*2106+1*2105+ 0*2104+0*2103+1*2102+0*2101+ 1*2100=42110

2. Для перевода чисел из системы исчисления с основой p в систему исчисления с основой q с использованием арифметики старой системы исчисления с основой p нужно:

для перевода целой части:

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

для перевода дробной части:

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

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

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

В древние времена, когда люди начали считать, появилась потребность в записи чисел. Количество предметов, например, изображалось нанесением черточек или засечек на какой-либо твердой поверхности: камне, глине, дереве (до изобретения бумаги было еще очень далеко). Каждому предмету в такой записи соответствовала одна черточка. Археологами найдены такие «записи» при раскопках культурных слоев, относящихся к периоду палеолита (10-11 тысяч лет до н.э.). Ученые назвали этот способ записи чисел единичной (палочной) системой счисления. В ней для записи чисел применялся только один вид знаков - палочка. Каждое число в такой системе счисления обозначалось с помощью строки, составленной из палочек, количество которых равнялось обозначаемому числу.

Неудобства такой системы записи чисел и ограниченность ее применения очевидны: чем большее число надо записать, тем длиннее строка из палочек; при записи большого числа легко ошибиться - нанести лишнее количество палочек или, наоборот, не дописать палочки.

Можно предположить. что для облегчения счета люди стали группировать предметы по 3, 5, 10 штук. И при записи стали использовать знаки, соответствующие группе из нескольких предметов. Поскольку люди, при подсчете использовали пальцы рук, то первыми появились знаки для обозначения групп предметов из 5 и 10 штук (единиц). И таким образом возникли уже более удобные системы записи чисел.

Десятиричная система исчисления

Мы привыкли к десятеричной системе исчисления с последовательностью цифр - 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, и т.д.

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

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

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

В двоичной системе исчисления с последовательностью цифр - 0, 1, 10, 11, 100, 101, 110, 111, и т.д.

правила сложения и вычитания теже самые, только цифр используют для подсчета не десять, а две: "1" и "0"

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

Также легко передавать эти единички и нули по проводам - есть напряжение, нет напряжения - единичка, нуль.

В двоичной системе каждому двоичному числу соответствует привычное для нас десятичное число.

Теорема о единственности представления чисел в позиционных системах

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

В математике доказывается следующий факт: любое действительное число можно представить в виде суммы целых степеней (неотрицательных для целой части и отрицательных для дробной) произвольного натурального числа P > 1. Если потребовать, чтобы количество одинаковых степеней Р (коэффициент при соответствующей степени) не превосходило Р - 1, то для натуральных чисел такое представление окажется единственным.

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

Теорема. Пусть Р - произвольное натуральное число, большее единицы. Существует и единственно представление любого натурального числа Х в виде:

Х = аnPn + an-1Pn-1 + … + a1P + а0,

где

0 &#8804; ai < P, 0 &#8804; i &#8804; n, an &#8800; 0.

Следствия из теоремы единственности

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

Десятичное число 23 можно записать:

в двоичной системе счисления как 101112;

в троичной системе счисления как 2123;

в четверичной системе счисления как 1134;

в шестнадцатеричной системе счисления как 1716;

в 23-ичной системе счисления как 1023;

в системах счисления с основанием большим, чем 23, данное число будет представлено одной цифрой (это будет буква латинского алфавита N или некий другой символ).

В разделе математики «Теория чисел» доказывается, что и любую правильную дробь можно представить в виде конечной или бесконечной суммы отрицательных степеней любого натурального числа Р > 1. То есть конечную десятичную дробь можно представить в виде конечной суммы отрицательных степеней числа 10, а бесконечную десятичную дробь - в виде бесконечной суммы таких степеней.

Например:

0,123 = 1·10 -1 + 2·10 -2 + 3·10 -3 = 0,1 + 0,02 + 0,003;

1/6 = 0,1(6) = 1·10 -1 + 6·10 -2 + 6·10 -3 + … = 0,1 + 0,06 + 0,006 + …;

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

Любое действительное число можно записать в Р-ичной системе счисления с базисом

…, P-2, P-1, P0, P1, P2, …

Представление чисел в Р-ичной системе счисления

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

В любой Р-ичной системе счисления натуральные числа, меньшие ее основания Р, представляются с помощью одной цифры данной системы. Для чисел же, больших или равных Р, требуются уже, по крайней мере, две цифры. Само число Р в системе счисления с основанием Р записывается в виде 10р, что следует из развернутой формы записи числа Р в Р-ичной системе:

Р = 1xР + 0.