Часть 6 Вопросы 16-18

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

Начнем с некоторых общих замечаний относительно понятия число. Можно считать, что любое число имеет значение (содержание) и форму представления. Значение числа задает его отношение к значениям других чисел («больше», «меньше», «равно») и, следовательно, порядок расположения чисел на числовой оси. Форма представления, как следует из названия, определяет порядок записи числа с помощью предназначенных для этого знаков. При этом значение числа является инвариантом, т.е. не зависит от способа его представления. Это означает также, что число с одним и тем же значением может быть записано по-разному, т.е. отсутствует взаимно однозначное соответствие между представлением числа и его значением. В связи с этим возникают вопросы, во-первых, о формах представления чисел, и, во-вторых, о возможности и способах перехода от одной формы к другой.

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

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

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

Унарная – это система счисления, в которой для записи чисел используется только один знак – I («палочка»). Следующее число получается из предыдущего добавлением новой I; их количество (сумма) равно самому числу. Именно такая система применяется для начального обучения счету детей (можно вспомнить «счетные палочки»); использование унарной системы оказывается важным педагогическим приемом для введения детей в мир чисел и действий с ними. Но, как мы увидим в дальнейшем, унарная система важна также в теоретическом отношении, поскольку в ней число представляется наиболее простым способом и, следовательно, просты операции с ним. Кроме того, именно унарная система определяет значение целого числа количеством содержащихся в нем единиц, которое, как было сказано, не зависит от формы представления. Для записи числа в унарной системе в дальнейшем будем использовать обозначение Z₁.

Из непозиционных наиболее распространенной можно считать римскую систему счисления. В ней некоторые базовые числа обозначены заглавными латинскими буквами: 1 – I, 5 – V, 10 – X, 50 – L, 100 – C, 500 – D, 1000 – M. Все другие числа строятся комбинаций базовых в соответствии со следующими правилами:

ü   если цифра меньшего значения стоит справа от большей цифры, то их значения суммируются; если слева – то меньшее значение вычитается из большего.

ü   цифры I, X, C и M могут следовать подряд не более трех раз каждая;

ü   цифры V, L и D могут использоваться в записи числа не более одного раза.

Например, запись XIX соответствует числу19, MDXLIX – числу 1549. Запись чисел в такой системе громоздка и неудобна, но еще более неудобным оказывается выполнение в ней даже самых простых арифметических операций. Отсутствие нуля и знаков для чисел больше M не позволяют римскими цифрами записать любое число (хотя бы натуральное). По указанным причинам теперь римская система используется лишь для нумерации.

В настоящее время для представления чисел применяют, в основном, позиционные системы счисления.

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

Наиболее распространенной и привычной является система счисления, в которой для записи чисел используется 10 цифр: 0, 1, 2, 3, 4, 5, 6, 7, 8 и 9. Число представляет собой краткую запись многочлена, в который входят степени некоторого другого числа – основания системы счисления. Например,

272,12 = 2·10²+7·10¹+2·10⁰+ 1·10^-1+2·10^-2

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

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

По принципу, положенному в основу десятичной системы счисления, очевидно, можно построить системы с иным основанием. Пусть p – основание системы счисления. Тогда любое число Z (пока ограничимся только целыми числами), удовлетворяющее условию Z < p^k (k 0, целое), может быть представлено в виде многочлена со степенями p (при этом, очевидно, максимальный показатель степени будет равен k – 1):

Из коэффициентов a_j при степенях основания строится сокращенная запись числа:

Z_p = (a_k-1 a_k-1… a₁ a₀)

Индекс p у числа Z указывает, что оно записано в системе счисления с основанием p; общее число цифр числа равно k. Все коэффициенты a_j – целые числа, удовлетворяющие условию:

0 a_j p - 1

Уместно задаться вопросом: каково минимальное значение p? p =1 невозможно, поскольку тогда все a_j = 0 и форма (1) теряет смысл. Первое допустимое значение p=2 – оно и является минимальным для позиционных систем. Система счисления с основанием 2 называется двоичной. Цифрами двоичной системы являются 0 и 1, а форма (1) строится по степеням 2. Интерес именно к этой системе счисления связан с тем, что, как указывалось выше, любая информация в компьютерах представляется с помощью двух состояний – 0 и 1, которые легко реализуются технически. Наряду с двоичной в компьютерах используются 8-ричная и 16-ричная системы счисления – причины будут рассмотрены далее.

Поскольку одно и то же число может быть записано в различных системах счисления, встает вопрос о переводе представления числа из одной системы (p) в другую (q) – будем обозначать такое преобразование Z_p Z_q. Теоретически возможно произвести его при любых q и p. Однако подобный прямой перевод будет затруднен тем, что придется выполнять операции по правилам арифметики недесятичных систем счисления. По этой причине более удобными с практической точки зрения оказываются варианты преобразования с промежуточным переводом Z_p Z_r Z_q с основанием r, для которого арифметические операции выполнить легко. Такими удобными основаниями является r = 10, т.е. перевод осуществляется через десятичную систему счисления.

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

Перевод целых чисел

Преобразование Z_p Z₁₀ Z_q (для целых чисел)

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

Алгоритмы перевода Z₁₀ Z_q вытекают из следующих соображений. Многочлен (1) для Z_q может быть представлен таким образом:

где m – число разрядов в записи Z_q, а b_j (j = 0…m–1) – цифры числа Z_q.

Разделим число Z_q на две части по разряду номер i; число, включающее m–i разрядов с m–1-го по i-й обозначим _i, а число с i разрядами с i–1-го по 0-ой – _i. Очевидно, i  [0,m–1],  ₀ = _m-1 = Z_q. Позаимствуем из языка PASCAL обозначение двух операций: div – результат целочисленного деления двух целых чисел и mod – остаток от целочисленного деления (13 div 4=3; 13 mod 4 = 1). Теперь если принять _m-1 = b_m-1, то в (2) усматривается следующее рекуррентное соотношение: _i = _i+1 · q + b_i, из которого, в свою очередь, получаются выражения:

Аналогично, если принять ₀ = b₀, то для правой части числа будет справедливо другое рекуррентное соотношение: _i = _i-1 + b_i ·qⁱ, из которого следуют:

Из соотношений (3) и (4) непосредственно вытекают два способа перевода целых чисел из 10-ной системы счисления в систему с произвольным основанием q.

Способ 1 является следствием соотношений (3), из которых просматривается следующий алгоритм перевода:

1.         целочисленно разделить исходное число (Z₁₀) на основание новой системы счисления (q) и найти остаток от деления – это будет цифра 0-го разряда числа Z_q;

2.         частное от деления снова целочисленно разделить на q с выделением остатка; процедуру продолжать до тех пор, пока частное от деления не окажется меньше q;

3.         образовавшиеся остатки от деления, поставленные в порядке, обратном порядку их получения, и представляют Z_q.

Пример 2 Выполнить преобразование 123₁₀ Z₅.

Остатки от деления (3, 4) и результат последнего целочисленного деления (4) образуют обратный порядок цифр нового числа. Следовательно, 123₁₀ = 443₅.

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

Алгоритмы перевода Z_p Z₁₀ явно вытекает из представлений (1) или (2): необходимо Z_p представить в форме многочлена и выполнить все операции по правилам десятичной арифметики.

Пример 3 Выполнить преобразование 443₅ Z₁₀

443₅ = 4·5²+4·5¹+3·5⁰ = 4·25+4·5+3·1 = 123₁₀

Необходимо еще раз подчеркнуть, что приведенными алгоритмами удобно пользоваться при переводе числа из десятичной системы в какую-то иную или наоборот. Ситуация, однако, значительно упрощается, если основания исходной и конечной систем счисления оказываются связанными соотношением p = q^r, где r – целое число (естественно, большее 1) или r = 1/n ( n>1, целое)– эти случаи будут рассмотрены ниже.

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

Переводы дробных чисел

Алгоритмы перевода 0,Y₁₀ 0,Y_q (для дробных чисел)

Выводится путем следующих рассуждений. Если основание системы счисления q, простая дробь содержит n цифр и b_k – цифры дроби (1 k n, 0 b_k q–1), то она может быть представлена в виде суммы:

Часть дроби от разряда i до ее конца обозначим _i и примем _n = b_n/q (очевидно, ₁ = 0,Y_q); тогда в (5) легко усматривается рекуррентное соотношение:

Если вновь позаимствовать в PASCAL’е обозначение функции – на этот раз trunc, которая производит округление целого вещественного числа путем отбрасывания его дробной части, то следствием (6) будут соотношения, позволяющие находить цифры новой дроби:

Соотношения (7) задают алгоритм преобразования 0,Y₁₀ 0,Y_q:

ü   умножить исходную дробь в 10-ной системе счисления на q, выделить целую часть – она будет первой цифрой новой дроби; отбросить целую часть;

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

ü   записать дробь в виде последовательности цифр после ноля с разделителем в порядке их появления в п. (1) и (2).

Пример 4: Выполнить преобразование 0,375₁₀ 0,Y₂

Таким образом, 0,375₁₀ = 0,011₂

Перевод 0,Y_p 0,Y₁₀,

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

0,011₂ = 0·2^-1 + 1·2^-2 + 1·2^-3 = 0,25 + 0,125 = 0,375₁₀

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

Пример 5 Выполнить преобразование 5,3(3)₁₀ X₃

Перевод целой части, очевидно, дает: 5₁₀ = 12₃. Перевод дробной части: 0,3(3)₁₀ = 0,1₃. Окончательно: 5,3(3)₁₀ = 12,1₃.

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

Число в системе счисления p с k разрядами, очевидно, будет иметь наибольшее значение в том случае, если все цифры числа окажутся максимальными, т.е. равными p – 1. Тогда

Количество разрядов числа при переходе от одной системы счисления к другой в общем случае меняется. Очевидно, если p =q ( – не обязательно целое), то (Z_p)^max = p^k – 1 =q ^k – 1. Т.е. количество разрядов числа в системах счисления p и q будут различаться в раз. Очевидно соотношение:

При этом основание логарифма никакого значения не имеет, поскольку определяется отношением логарифмов. Сравним количество цифр в числе 99₁₀ и его представлении в двоичной системе счисления: 99₁₀ = 1100011₂; т.е. двоичная запись требует 7 цифр вместо 2 в десятичной. = ln(10)/ln(2) = 3,322; следовательно, количество цифр в десятичном представлении нужно умножить на 3,322 и округлить в большую сторону: 2·3,322 = 6,644 7 .