Лекция 4. Системы счисления

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

• — возможность представления любого числа в рассматриваемом, заранее назначенном диапазоне величин;
• — единственность представления (любая комбинация символов соответствует одному и только одному числу);
• — простоту операций с числами.

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

В непозиционной системе счисления значения символов не зависят от положения в числе. Для образования таких систем используют, в основном, операции сложения и вычитания. Например, система с одним символом-палочкой встречалась у многих народов. Для изображения числа в этой системе нужно записать определенное множество палочек, равное данному числу. Эта система не эффективна, т.к. запись числа получается длинной. Другим примером непозиционной системы счисления является римская система, использующая набор следующих символов: I, V, X, L, C, D и т. д. В этой системе имеются отклонения от правила независимости значения цифры от положения в числе. В числах IV и VI символ I принимает соответственно значения -1 и +1.

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

903,87=9?10²+0?10¹+3?10⁰+8?10^-1+7?10^-2.

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

Количество различных цифр, применяемых в позиционной системе счисления, называется ее основанием (для десятичной системы — от 0 до 9- десять).

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

A_(p) = a_n-1 a_n-2 … a₁ a₀, a_-1 … a_-m

в р-ичной системе означает число.

где a_i — цифры системы счисления, n и m — число целых и дробных разрядов числа.

Обычно в качестве двух младших цифр во всех системах счисления используются знаки 0 и 1. При этом основание системы счисления р записывается в виде последовательности цифр 10 (это не десять, а один ноль!). В скобках указывают систему счисления, в которой записывается число, т. е 10_(р).

В вычислительной технике широко используются двоичная, восьмеричная и шестнадцатеричная системы счисления. При этом для представления чисел в двоичной системе используются две цифры 0 и 1, в восьмеричной — 0, 1,…, 7 и в шестнадцатеричной — цифры 0, 1,…, 9 и знаки A, B, C, D, E, F (часто вместо этих знаков записывают символы.

).

Пример 3.1. В качестве примера возьмем двоичное число 1001,1101₍₂₎. В соответствии с равенством (3.1) двоичное число можно определить следующим образом:

1001,1101₍₂₎=1?2³+0?2²+0?2¹+1?2⁰+1?2^-1+1?2^-2 + 0?2^-3 + 1?2^-4.

Если по правилам десятичной арифметики выполнить действия в правой части приведенного равенства, то можно получить значение этого числа в десятичной системе счисления (десятичный эквивалент двоичного числа):

1001, 1001₍₂₎=9,8125₍₁₀₎ .

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

Таблица 3.1.

Для записи одного и того же значения в различных системах счисления требуется разное число позиций или разрядов. Например, 96₍₁₀₎=140₍₈₎=1 100 000₍₂₎. Чем меньше основание системы счисления, тем больше длина числа (длина разрядной сетки). Если длина разрядной сетки задана, то это ограничивает максимальное по абсолютному значению число, которое можно записать.

Пусть длина разрядной сетки равна числу N. Тогда.

A _(p)max = p^N — 1.

Если же задано максимальное абсолютное значение числа, то длина разрядной сетки N равна:

N=log_P (A_(P)max+1).

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

— A _(P)max ДП A_(P)max .

В ЭВМ длина обрабатываемых чисел обычно ограничена следующими значениями: 1 байт (8 двоичных разрядов), 2 байта (16 разрядов), 4 байта (32 разряда) и 8 байт (64 разряда). Соответственно ограничены и значения чисел, записываемых с использованием этих разрядных сеток. Так, максимальное целое положительное число, которое можно записать с использованием 16 двоичных разрядов, равно 2¹⁶-1 = =65 535.

Арифметические операции в различных системах счисления

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

Рассмотрим сложение.

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

• 0+0 = 0
• 0+1 = 1
• 1+0 = 1
• 1+1 =10.

Примеры сложения чисел.

Пример 3.2. Пример 3.3.

• 101 011, 1101 ₍₂₎ 245,0 ₍₈₎
• 10 010, 1011 ₍₂₎ 734,7 ₍₈₎
• 111 110, 1000 ₍₂₎. 1201,7 ₍₈₎ .

Правило вычитания чисел в системе счисления основанием р представляется так:

a_k = a_i — a_j при a_i a_j ,.

a_k = p + a_i — a_j при a_i < a_j ,.

е. при a_i < a_j занимается «1» старшего разряда, содержащая р единиц младшего разряда. Таблица вычитания для двоичной системы счисления:

• 0−0=0
• 1−0=1
• 1−1=0
• 10−1=1 .

римеры вычитания чисел:

Пример 3.4. Пример 3.5.

1001,01 ₍₂₎ 1352,2 ₍₈₎

• 110,11 ₍₂₎ 743,5 ₍₈₎
• 0010,10 ₍₂₎. 406,5 ₍₈₎ .

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

.

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

• 0?0=0
• 0?1=0
• 1?0=0
• 1?1=1.

Пример 3.6:

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

Деление выполняется по правилам, аналогичным десятичной системе счисления, но с использованием соответствующих таблиц сложения и умножения. Рассмотрим деление целых чисел в двоичной системе счисления (при дробных числах освобождаются от дробей умножением на одно и то же число). При делении в делимом выделяют минимально возможную группу разрядов, образующих число, равное или большее, делителя. Если такая группа образуется, то в частном записывают 1, если нет — 0. Затем образуется новая группа разрядов путем вычитания из выделенной группы делителя и приписыванием к полученной разности следующей цифры делимого и т. д.

Пример 3.7. Разделить число 111 111,01₍₂₎ на 101,1 ₍₂₎.

Умножим оба числа на 100 ₍₂₎ и будем делить два целых числа:

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

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

Пусть задано число А_(q) в q-ичной системе счисления. Требуется найти запись этого числа в р-ичной системе счисления, т. е. В_(р).

Метод непосредственного замещения

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

— заданное число А_(q) представляется в виде (3.1):

A_(q)=a_n-1?q^n-1+…+a₀?q⁰+a —₁?q^-1+…+a_-m?q^-m ;

— все цифры a_i и основание q в правой части записываются (замещаются) в системе счисления с новым основанием p и выполняются необходимые операции. При этом, если р>q, то изображение цифр в p-ичной системе совпадает с изображением чисел в q-ичной системе. Если же p.

Пример 3.8. Перевести число 357 ₍₈₎ в десятичную систему счисления.

Решение. 357₍₈₎=3?8²+5?8¹+7?8⁰=192+40+7=239₍₁₀₎.

Пример 3.9. Перевести число 13,5₍₁₀₎ в двоичную систему счисления.

Решение. 13,5₍₁₀₎=1?10¹+3?10⁰+5?10^-1=1?1010+11+101/1010=1101,1₍₂₎ .

Метод последовательного деления на основание

Этот метод используется для перевода только целых чисел.

Пусть число A_(q) требуется записать в р-ичной системе. Допустим, что такое представление получено и новое число В_(р) имеет вид:

A_(q) = B_(p) = b_n-1 b_n-2 … b₁ b_{0 (p)} = b_n-1?p^n-1 + b_n-2?p^n-2 + … + b₁ p¹ + b₀.

Разделим число A_(q) на р. Так как b₀

A₁ = b_n-1?p^n-2 + b_n-2?p^n-3 + … + b₁

и остаток b₀. Отсюда следует, что остаток от деления заданного числа на основаниe р равен значению цифры младшего разряда р-ичного числа. При этом, если pq остаток представляет собой число в q-ичной системе счисления, которое соответствует цифре р-ичной системы (заметим, что деление должно выполняться в q-ичной системе счисления, т. е. в системе, в которой задано исходное число).

Чтобы найти цифру b₁ следует отбросить остаток b₀, a А₁ вновь разделить на р. Получим целую часть А₂ = b_n-1?p^n-3 + … b₃?p + b₂

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

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

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

Решение:

Ответ: B₍₂₎=b₅ b₄ b₃ b₂ b₁ b₀₍₂₎=100 110₍₂₎ .

Пример 3.11. Провести обратный перевод числа B (2)=10 0110(2) в десятичную систему счисления.

Решение: Сначала новое основание системы счисления представим в двоичной системе: 10₍₁₀₎=1010₍₂₎. Далее делим число 100 110₍₂₎ на основание 1010₍₂₎.

Ответ: 100 110₍₂₎=b₁b_{0 (10)} = 38₍₁₀₎.

Метод последовательного умножения на основание

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

Пусть правильную дробь A_(q) требуется записать в системе счисления с основанием р. Предположим опять, что эта запись найдена

A_(q)=B_(p)=0, b_-1 b_-2… b_-m(p)=b_-1?p^-1+b_-2?p^-2+…+b_-m ?p^-m.

Если умножить число, А на основание новой системы счисления p, то целая часть произведения будет равна b_-1, а дробная

A₁=b_-2?p^-1+b_-3?p^-2 + … + b_-m?p^-m+1,

причем A₁-правильная дробь, т.к. все a_i < p.

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

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

Пример 3.12. Перевести десятичную дробь A₍₁₀₎=0,6875₍₁₀₎ в двоичную систему счисления.

Решение. Выполним следующие действия:

Ответ: B₍₂₎=0, b_-1 b_-2 b_-3 b_-4=0,1011₍₂₎.

Пример 3.13. Провести обратный перевод двоичного числа 0,1011₍₂₎ в десятичную дробь.

Решение. В данном примере p>q, поэтому сначала переведем р₍₁₀₎ в двоичную систему счисления: р=10₍₁₀₎=1010₍₂₎. Выполним последовательные умножения:

Ответ: B₍₁₀₎=0, b_-1 b_-2 b_-3 b_-4 = 0,6875.

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

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

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

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

Пусть задано число, А в 8-ричной системе:

A=a_n-1 a_n-2…a₁ a₀₍₈₎ = a_n-1?8^n-1+a_n-2?8^n-2+…+a₁?8¹+a₀?8⁰.

Пусть число, А записано в 2-ичной системе счисления:

A=b_l-1 b_l-2…b₂ b₁ b_{0 (2)} = b_l-1?2^l-1+b_l-2?2^l-2+…+b₂?2²+b₁?2¹+b_0.

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

a_n-18^n-1+a_n-28^n-2+…+a₁8¹+a₀8⁰= b_l-1 2^l-1+2_l-2 2^l-2+…+b₂ 2²+b₁ 2¹+b₀ 2⁰ .

Если разделить обе части равенства на 8, то получим одинаковые частные

a_n-1 8^n-2 + a_n-2 8^n-3 +…+ a₁ = b_l-1 2^l-4 + b_l-2^l-5 +…+ b₄ 2¹ + b₃

и одинаковые остатки:

a₀₍₈₎=b₂ 2² + b₁ 2¹ + b₀ 2⁰ = b₂ b₁ b_{0 (2)}.

Следовательно, младшая восьмеричная цифра a₀₍₈₎ выражается трехразрядным двоичным числом b₂ b₁ b_{0 (2)}.

Если частное вновь разделить на 8, то получим а₁₍₈₎=b₅ b₄ b_{3 (2)}.

Аналогично можно получить все остальные разряды.

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

Пример 3.14. Перевести восьмеричное число 571,034 ₍₈₎ в двоичное.

Решение.

.

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

Пример 3.15. Перевести двоичное число 11 011 111 011 001, 1001₍₂₎ в восьмеричное.

Решение.

.

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