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

Конспект

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

Система счисления — знаковая система, позволяющая по определённым правилам записывать числа при помощи символов некоторого алфавита (цифр).

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

Непозиционные системы счисления: значение числа получается путём суммирования (и вычитания) количественных значений цифр, не зависящих от их местоположения в числе. Пример: римская система счисления.

Римская цифра	М	D	С	L	X	V	I
Значение	1000	500	100	50	10	5	1

При расшифровке римской записи числа:

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

— если меньшая по значению цифра располагается справа от большей, то значение меньшей цифры прибавляется к значению большей;

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

Римская запись	Десятичное число
CDXXXVII

Основание позиционной системы счисления:

— определяет изменение количественного значения (“во сколько раз”) при изменении положения цифры в числе на один разряд правее/левее;

— равно количеству цифр в алфавите системы счисления.

Теоретически возможно любое значение основания системы счисления, начиная с 2. Для систем счисления с основанием р, меньшим 10, в качестве знаков алфавита системы счисления используются десятичные цифры от 0 до (р — 1); для систем с основанием р, большим 10, используются все 10 десятичных цифр плюс дополнительные символы (обычно — латинские заглавные буквы, начиная с “А”). На практике системы счисления с основанием больше 16 практически не используются (за исключением измерения времени и градусной меры углов, основанных на системе счисления с основанием 60).

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

Примеры наиболее часто используемых систем счисления:

Система счисления	Основание (р)	Алфавит системы счисления	Пример записи числа
Двоичная	2	0, 1	1011012
Восьмеричная	8	0, 1, 2, 3, 4, 5, 6, 7	123458
Десятичная	10	0, 1, 2, 3, 4, 5, 6, 7, 8, 9	123410
Шестнадцатеричная	16	0, 1, 2, 3, 4, 5, 6, 7, 8, 9, А (=10), В (=11), С (=12), D (=13), Е (=14), F (=15)	F4D916

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

Свёрнутая (“обычная”) форма записи числа — привычная запись числа как последовательности цифр, стоящих на своих разрядах.

Развёрнутая форма записи числа — запись числа в виде суммы произведений его цифр на основание системы счисления в степени, равной значению разряда той или иной цифры числа (для целого числа нумерация разрядов ведётся с нуля справа налево; для дробного числа нумерация разрядов ведётся от десятичной запятой влево по возрастанию, а вправо — по убыванию, при этом разряду единиц присваивается нулевой номер).

Форма (схема) Горнера — преобразованная запись развёрнутой формы, при которой за счёт использования скобок удается избавиться от возведения основания счисления в степени. Схема Горнера предполагает рекуррентные вычисления.

Примеры: а) для целых чисел:

Формы записи	Примеры чисел
	двоичное	восьмеричное	десятичное	шестнадцатеричное
Свёрнутая	101101	12345	1234	F4D9
Развёрнутая
Схема Горнера

б) для дробных чисел:

Формы записи	Примеры чисел
	двоичное	десятичное
Свёрнутая	1001,11	123,45
Развёрнутая

Перевод числа из недесятичной системы счисления в десятичную осуществляется путём выполнения вычислений по развернутой записи исходного числа.

Примеры:

— перевести в десятичную систему счисления число 101110,101₂:

— перевести в десятичную систему счисления число F4D9,7₁₆:

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

Пример: требуется перевести число 12345₁₀ в троичную систему счисления:

В результате: 12345₁₀ = 121221020₃.

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

Пример: требуется перевести число ОД23₁₀ в пятеричную систему счисления с точностью до 5 значащих цифр после запятой:

В результате: 0,123₁₀ ≈ 0,03030₅ = 0,(03)₅.

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

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

1) отдельно осуществляется перевод целой части числа путём последовательности делений на основание системы счисления;

2) отдельно выполняется перевод дробной части числа путём последовательности умножений на основание системы счисления.

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

Пример: требуется перевести число 15,12₁₀ в пятеричную систему счисления с точностью до 5 значащих цифр после запятой:

1) 15₁₀ = 30₅;

2) 0,12₁₀ = 0,03₅.

В результате: 15,12₁₀ = 30,03₅.

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

1) перевести исходное число в десятичную систему счисления;

2) перевести полученное десятичное число в требуемую систему счисления.

Перевод чисел между системами счисления с кратными основаниями. Если основания исходной и конечной системы кратны друг другу, то перевод чисел между этими системами счисления можно выполнять по упрощённой схеме.

1. Перевод двоичного числа в восьмеричную систему счисления производится по триадам цифр:

— исходное двоичное число разбивается на группы по три цифры (“триады”) справа налево; при необходимости крайняя слева группа цифр дополняется незначащими нулями слева;

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

Двоичная триада	000	001	010	011	100	101	110	111
Восьмеричное значение	0	1	2	3	4	5	6	7

Пример: требуется перевести число 1011010₂ в восьмеричную систему счисления:

В результате: 1011010₂ = 132₈.

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

— исходное восьмеричное число разбивается на отдельные цифры;

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

— искомое двоичное число составляется из полученных триад; незначащие нули слева отбрасываются.

Пример: требуется перевести число 12345₈ в двоичную систему счисления:

В результате: 12345₈ = 1010011100101₂.

3. Перевод двоичного числа в шестнадцатеричную систему счисления производится по тетрадам цифр:

— исходное двоичное число разбивается на группы по четыре цифры (“тетрады”) справа налево; при необходимости крайняя слева группа цифр дополняется незначащими нулями слева;

— каждая тетрада двоичных цифр заменяется соответствующим ей шестнадцатеричным значением согласно таблице:

Двоичная триада	0000	0001	0010	0011	0100	0101	0110	0111
Шестнадцатеричное значение	0	1	2	3	4	5	6	7
Двоичная триада	1000	1001	1010	1011	1100	1101	1110	1111
Шестнадцатеричное значение	8	9	А	В	С	D	Е	F

Пример: требуется перевести число 1011010₂ в шестнадцатеричную систему счисления:

В результате: 1011010₂ = 5А₁₆.

4. Перевод шестнадцатеричного числа в двоичную систему счисления также производится по тетрадам цифр:

— исходное шестнадцатеричное число разбивается на отдельные цифры;

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

— искомое двоичное число составляется из полученных тетрад; незначащие нули слева отбрасываются.

Пример: требуется перевести число 1ADA₁₆ в двоичную систему счисления:

В результате: 1ADA₁₆ = 1101011011010₂.

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

Таблицы степеней

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

n	0	1	2	3	4	5	6	7
2n	20	21	22	23	24	25	26	27
Значение	1	2	4	8	16	32	64	128

n	8	9	10	20	30
2n	28	29	210	220	230
Значение	256	516	1024	1048576	1073741824

Арифметика в недесятичных системах счисления (на примере двоичной арифметики)

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

1. Сложение одноразрядных двоичных чисел:

Запись ⁽¹⁾ обозначает перенос единицы в старший разряд.

2. Умножение одноразрядных двоичных чисел:

3. Сложение многоразрядных двоичных чисел выполняется в столбик.

Пример: требуется вычислить значение выражения 111101₂ + 1001₂:

В результате: 111101₂ + 1001₂ = 1000110₂.

4. Вычитание многоразрядных двоичных чисел также выполняется в столбик, при этом возможен заём 1 из старшего разряда.

Пример: требуется вычислить значение выражения 110101₂ - 1001₂:

В результате: 110101₂ - 1001₂ = 101100₂.

5. Умножение многоразрядных двоичных чисел выполняется в столбик аналогично умножению десятичных чисел. Однако при этом для двоичной системы счисления можно воспользоваться следующими простыми правилами:

— всегда умножать большее число на меньшее;

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

Пример: требуется вычислить значение выражения 110101₂ х 1101₂:

110101 ^х 1101 110101 + 110101 + 110101 1010110001

В результате: 110101₂ х 1101₂ = 1010110001₂.

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

Пример: требуется вычислить значение выражения 1001011₂ / 101₂:

В результате: 1001011₂ / 101₂ = 1111₂.

Арифметические операции в других системах счисления выполняются аналогично.

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

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

Разбор типовых задач

Задача 1.

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

Решение

1) Значащие нули не могут располагаться в самом начале числа, — значит, число должно начинаться хотя бы с одной единицы.

2) Вспомним формулу перевода двоичного числа в десятичное: чем левее в двоичном числе единица, тем большая степень двойки входит в качестве слагаемого в эту запись. Следовательно, максимальное значение двоичного числа получится, если все единицы будут “собраны” в старших разрядах.

3) Требуется, чтобы в записи числа было ровно три значащих нуля и две единицы. Следовательно, число — 5-разрядное. Если все единицы размещаются в старших разрядах, то это число 11000₂.

4) Ответ требуется записать в десятичной форме. Переведем полученное двоичное число в десятичное:

11000₂ = 2⁴ + 2³ = 16 + 8 = 24₁₀.

Ответ: 24₁₀.

Задача 2.

Известно, что для целого числа х выполнено:

Определите значение х. Ответ запишите в десятичной системе счисления.

Решение

По сути, это задание на поиск основания системы счисления.

1) Запишем “каноническое” преобразование обоих недесятичных чисел в десятичную систему счисления (согласно формуле вида ):

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

15 + 3х - 15 = 33,

откуда 3x = 33, тогда х = 11.

Ответ: 11.

Задача 3.

Определите наименьшее пятизначное восьмеричное число, двоичная запись которого содержит 3 единицы. (В ответе записать только само число, без индекса системы счисления.)

Решение

На первый взгляд, кажется, что всё просто: чем правее в двоичном числе записаны единицы, тем это число меньше¹. Значит, наименьшим является число 111₂.

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

Как найти наименьшее пятизначное восьмеричное число? Нужно, оставляя как можно больше единиц справа, “отодвигать” только одну единицу влево, записывая после нее нули до тех пор, пока не получится такое двоичное число, которое после перевода в восьмеричную систему счисления будет иметь 5 цифр. Это число будет наименьшим из возможных, потому что если бы мы перемещали хоть одну из оставшихся справа единиц левее, то только увеличивали бы наше число.

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

Ответ: 10003

Наиболее распространенная ошибка при верной общей идее решения — сместить левую единицу так, чтобы получить слева целую триаду из трёх двоичных разрядов (“100”), забыв, что можно дополнить триаду незначащими нулями слева. В результате получилось бы восьмеричное число 40003, которое не является минимально возможным.

Задача 4.

Сколько единиц в двоичной записи числа

Решение

1. Все числа, кроме последнего, представим как степени двоек (учитывая, что 8 = 2³, а 4 = 2²). Последнее число 3 можно было бы разложить на слагаемые (2 + 1), но поскольку в его двоичном представлении (3₁₀ = 11₂) ограниченное количество разрядов, с ним можно справиться и так.

Получаем запись: 2³⁰⁰⁰ + 2¹⁰⁰⁰ - 2²⁵⁰ + 11₂.

2. Двоичное число 2³⁰⁰⁰ можно представить так:

3. Прибавляя к этому числу двоичное число 2¹⁰⁰⁰, мы фактически добавляем единицу в разряд, номер которого равен 1000:

4. Вычитание двоичной единицы из двоичного нуля производится с заёмом из предыдущих разрядов. Причем заём распространяется влево, пока не дойдёт до первой же встреченной единицы. Эта единица уходит в очередной заём, а далее вправо в числе уже ничего не меняется. Например:

Этим свойством мы и воспользуемся. При вычитании числа 2²⁵⁰ нам даже не потребуется выполнять вычитание — достаточно под единицей в 250-м разряде тоже подписать единицу, потом “тянуть” эту единицу влево по всем нулевым разрядам, а дойдя до первой встреченной единицы (в 1000-м разряде), заменить её на нуль. Всё, что правее 250-го разряда, и всё, что левее замененной на нуль единицы в 1000-м разряде, просто переписывается из уменьшаемого числа:

5. Остается прибавить к полученному на предыдущем шаге числу последнее число 11₂ — достаточно записать в два последних разряда эти единицы:

6. Наконец, подсчитаем интересующее нас количество единиц.

• Одна единица в 3000-м разряде.

• Две единицы в разрядах с номерами 0 и 1.

• Наконец, группа единиц в разрядах с 250 по 999 включительно, — их

999 - 250 + 1 = 750 штук.

Чтобы быстро вспомнить, что нужно прибавлять к разности номеров разрядов единицу, можно рассмотреть простой пример. Пусть единицы “лежат” в разрядах с 2 по 4 включительно. Легко подсчитать, что этих единиц три: в разрядах 2, 3 и 4. А разность номеров разрядов равна 4 - 2 = 2. Значит, нужно прибавлять единицу.

Итого в полученном числе единиц: 1 + 2 + 750 = 753.

Ответ: 753.

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

---

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