Потопахин Виталий Валерьевич
Двоичная арифметика
Дорогие читатели. В данной статье излагается материал по информатике. Вам необходимо внимательно изучить этот материал, решить задачи, предложенные для самостоятельного решения, оформить их в отдельной тетради и выслать на адрес, указанный во вступительной статье.
Числа, которыми мы привыкли пользоваться, называются десятичными и арифметика, которой мы пользуемся, также называется десятичной. Называются они так потому, что каждое число можно составить из набора цифр содержащего 10 символов - цифр - "0123456789".
Так исторически сложилось, что именно этот набор стал основным в записи чисел, но десятичная арифметика не единственная. Если мы возьмём только пять цифр, то на их основе можно построить пятеричную арифметику, из семи цифр - семеричную. В областях знаний, связанных с компьютерной техникой часто используют арифметику, в которой числа составляются из шестнадцати цифр, соответственно эта арифметика называется шестнадцатеричной. Чтобы понять, что такое число в не десятичной арифметике сначала вспомним, что такое число в десятичной арифметике.
Возьмём, к примеру, число 246. Его запись означает, что в числе две сотни, четыре десятка и шесть единиц. Следовательно, можно записать следующее равенство:
246 = 200 + 40 + 6 = 2 * 102 + 4 * 101 + 6 * 100
Здесь знаками равенства отделены три способа записи одного и того же числа. Для нас наиболее интересна третья форма записи: 2 * 102 + 4 * 101 + 6 * 100 . Она построена следующим образом:
В нашем числе три цифры. Старшая цифра "2" имеет номер 3. Так вот она умножается на 10 во второй степени. Следующая цифра "4" имеет порядковый номер 2 и умножается на 10 в первой степени. Уже видно, что цифры умножаются на десять в степени на единицу меньше порядкового номера цифры. Уяснив сказанное, мы можем записать общую формулу представления десятичного числа. Пусть дано число, в котором N цифр. Будем обозначать i-ю цифру через ai. Тогда число можно записать в следующем виде: anan-1….a2a1. Это первая форма, а третья форма записи будет выглядеть так:
anan-1….a2a1 = an * 10n-1 + an-1 * 10n-2 + …. + a2 * 101 + a1 * 100
где ai это символ из набора "0123456789"
В этой записи очень хорошо видна роль десятки. Десятка является основой образования числа. И, кстати, она так и называется "основание системы счисления", а сама система счисления называется "десятичной". Конечно, никакими особыми свойствами число десять не обладает. Мы вполне можем заменить десять на любое другое число. Например, число в пятеричной системе счисления можно записать так:
anan-1….a2a1 = an * 5n-1 + an-1 * 5n-2 + …. + a2 * 51 + a1 * 50
где ai это символ из набора "012345"
В общем, заменяем 10 на любое другое число и получаем совершенно другую систему счисления и другую арифметику. Наиболее простая арифметика получается, если заменить 10 на 2. Полученная система счисления называется двоичной и число в ней определяется следующим образом:
anan-1….a2a1 = an * 2n-1 + an-1 * 2n-2 + …. + a2 * 21 + a1 * 20
где ai это символ из набора "01"
Эта система - самая простая из всех возможных, так как в ней любое число образуется только из двух цифр 0 и 1.
Примеры двоичных чисел: 10, 111, 101.
Очень важный вопрос. Можно ли двоичное число представить в виде десятичного числа и наоборот, можно ли десятичное число представить в виде двоичного.
Двоичное в десятичное. Это очень просто. Возьмём, к примеру, следующее двоичное число 1011. Разложим его по степеням двойки. Получим:
1001 = 1 * 23 + 0 * 22 + 0 * 21 + 1 * 20
Выполним все записанные действия и получим:
1 * 23 + 0 * 22 + 0 * 21 + 1 * 20 = 8 + 0+ 0 + 1 = 9.
Таким образом, получаем, что 1011(двоичное) = 9 (десятичное). Сразу видно и небольшое неудобство двоичной системы. То число, которое, в десятичной системе записано одним знаком в двоичной системе, для своей записи требует четырех знаков. Но это плата за простоту в других вещах (бесплатно ничего не бывает). Двоичная система даёт огромный выигрыш в арифметических действиях. Ниже мы подробно рассмотрим этот вопрос.
Упражнение. Представьте в виде десятичного числа следующие двоичные числа: а) 10010 б) 11101 с) 1010 в) 1110 г) 100011 д) 1100111 е) 1001110
Сложение двоичных чисел
Рассмотрим способ сложения “столбиком” (такой же, как и для десятичного числа).
Сложение в десятичной системе выполняется поразрядно, начиная с младшей цифры. Если при сложении двух цифр получается СУММА больше десяти, то записывается цифра 9, а СУММА МИНУС ДЕВЯТЬ, добавляется к следующему старшему разряду. (Сложите пару чисел столбиком, вспомните, как это делается.)
Аналогично выполняется сложение двоичных чисел.
Складываем числа поразрядно, начиная с младшей цифры (она стоит крайней справа).
- Если сумма равна 0 или 1 – она записывается в данный разряд числа - суммы,
- если сумма разрядов равна 2, то в соответствующий разряд числа - суммы записывается 0, а к сумме следующих разрядов прибавляется 1,
- если сумма разрядов оказалась равной 3 (а это может быть в случае, если у обоих слагаемых в данном разряде единицы и еще одна единица пришла после сложения в предыдущем разряде), то в соответствующем разряде числа - суммы записывается 1 и еще одна единица прибавляется к сумме следующих разрядов).
Рассмотрим пример: 10011 + 10001.
Первый разряд: 1+1 = 2. Записываем 0 и 1 “на ум пошло”.
Второй разряд: 1+0+1 (запомненная единица) =2. Записываем 0 и “1 на ум пошло”.
Третий разряд: 0+0+1(запомненная единица) = 1. Записываем 1.
Четвертый разряд: 0+0=0. Записываем 0.
Пятый разряд: 1+1=2. Записываем 0 и добавляем шестым разрядом 1.
Переведём все три числа в десятичную систему и проверим правильность сложения.
10011 = 1*24 + 0*23 + 0*22 + 1*21 + 1*20 = 16 + 2 + 1 =19
10001 = 1*24 + 0*23 + 0*22 + 0*21 + 1*20 = 16 + 1 = 17
100100 = 1*25 + 0*24 + 0*23 + 1*22 + 0*21 + 0*20 =32+4=36
17 + 19 = 36 - верное равенство
Упражнения для самостоятельного решения:
Вычислить в двоичной системе
а) 11001 +101 =
б) 11001 +11001 =
с) 1001 + 111 =
д) 10011 + 101 =
е) 11011 + 1111 =
д) 11111 + 10011 =
Как десятичное число перевести в двоичное. Сейчас на очереди следующая операция - вычитание. Но этой операцией мы займёмся немного позже, а сейчас рассмотрим метод преобразования десятичного числа в двоичное.
Для того чтобы преобразовать десятичное число в двоичное, его нужно разложить по степеням двойки. Для начала рассмотрим, как это делается методом подбора. Возьмём десятичное число 12.
Шаг первый. 22 = 4, этого мало. Также мало и 23 = 8, а 24=16 это уже много. Поэтому оставим 23 =8. 12 - 8 = 4. Теперь нужно представить в виде степени двойки 4.
Шаг второй. 4 = 22.
Тогда наше число 12 = 23 + 22. Старшая цифра имеет номер 4, старшая степень = 3, следовательно, должны быть слагаемые со степенями двойки 1 и 0. Но они нам не нужны, поэтому чтобы избавится от ненужных степеней, и оставить нужные запишем число так: 1*23 + 1*22 +0*21 + 0*20 = 1100 - это и есть двоичное представление числа 12. Нетрудно заметить, что каждая очередная степень - это наибольшая степень двойки, которая меньше разлагаемого числа.
Чтобы закрепить метод рассмотрим ещё один пример. Найти двоичную запись числа 23.
Шаг 1. Ближайшая степень двойки 24 = 16. 23 -16= 7.
Шаг 2. Ближайшая степень двойки 22 = 4. 7 - 4 = 3
Шаг 3. Ближайшая степень двойки 21 = 2. 3 - 2 = 1
Шаг 4. Ближайшая степень двойки 20=1 1 - 1 =0
Получаем следующее разложение: 1*24 + 0*23 +1*22 +1*21 +1*20
Искомое двоичное число 10111
Рассмотренный выше метод дает хорошее решение поставленной задачи, но существует способ, который значительно лучше алгоритмизируется. Алгоритм этого метода записан ниже:
Пока ЧИСЛО больше нуля делать
Начало
ОЧЕРЕДНАЯ ЦИФРА = остаток от деления ЧИСЛА на 2
ЧИСЛО = целая часть от деления ЧИСЛА на 2
Конец
Когда этот алгоритм завершит свою работу, последовательность вычисленных ОЧЕРЕДНЫХ ЦИФР и будет представлять двоичное число. Для примера поработаем с числом 19.
Начало алгоритма ЧИСЛО = 19
Шаг 1
ОЧЕРЕДНАЯ ЦИФРА = 1
ЧИСЛО = 9
Шаг 2
ОЧЕРЕДНАЯ ЦИФРА = 1
ЧИСЛО = 4
Шаг 3
ОЧЕРЕДНАЯ ЦИФРА = 0
ЧИСЛО = 2
Шаг 4
ОЧЕРЕДНАЯ ЦИФРА = 0
ЧИСЛО = 1
Шаг 5
ОЧЕРЕДНАЯ ЦИФРА = 1
ЧИСЛО = 0
В результате получено число 10011. Заметьте, что два рассмотренных метода отличаются порядком получения очередных цифр. В первом методе первая полученная цифра - это старшая цифра двоичного числа, а во втором первая полученная цифра наоборот младшая.
Преобразуйте десятичные числа в двоичные двумя способами
а) 14 б) 29 в) 134 г) 158 е) 1190 ж) 2019
Как преобразовать в десятичное число дробную часть.
Известно, что любое рациональное число можно представить в виде десятичной и обыкновенной дроби. Обыкновенная дробь, то есть дробь вида А/В может быть правильной и неправильной. Дробь называется правильной если А<В и неправильной если А>В.
Если рациональное число представлено неправильной дробью, и при этом числитель дроби делится на знаменатель нацело, то данное рациональное число - число целое, во всех иных случаях возникает дробная часть. Дробная часть зачастую бывает очень длинным числом и даже бесконечным (бесконечная периодическая дробь, например 20/6), поэтому в случае с дробной частью у нас возникает не просто задача перевода одного представления в другое, а перевод с определённой точностью.
Правило точности. Предположим, дано десятичное число, которое в виде десятичной дроби представимо с точностью до N знаков. Для того чтобы соответствующее двоичное число было той же точности, в нём необходимо записать M - знаков, так что бы
2m > 10N
А теперь попробуем получить правило перевода, и для начала рассмотрим пример 5,401
Решение:
Целую часть мы получим по уже известным нам правилам, и она равна двоичному числу 101. А дробную часть разложим по степеням 2.
Шаг 1: 2-2 = 0,25; 0,401 - 0,25 = 0,151. - это остаток.
Шаг 2: Сейчас необходимо степенью двойки представить 0,151. Сделаем это: 2-3 = 0,125; 0,151 - 0,125 = 0,026
Таким образом, исходную дробную, часть можно представить в виде 2-2 +2-3 . То же самое можно записать таким двоичным числом: 0,011. В первом дробном разряде стоит ноль, это потому, что в нашем разложении степень 2-1 отсутствует.
Из первого и второго шагов ясно, что это представление не точное и может быть разложение желательно продолжить. Обратимся к правилу. Оно говорит, что нам нужно столько знаков М чтобы 103 было меньше чем 2М. То есть 1000<2M. То есть в двоичном разложении у нас должно быть не менее десяти знаков, так как 29 = 512 и только 210 = 1024. Продолжим процесс.
Шаг 3: Сейчас работаем с числом 0,026. Ближайшая к этому числу степень двойки 2-6 = 0,015625; 0,026 - 0,015625 = 0,010375 теперь наше более точное двоичное число имеет вид: 0,011001. После запятой уже шесть знаков, но этого пока недостаточно, поэтому выполняем ещё один шаг.
Шаг 4: Сейчас работаем с числом 0,010375. Ближайшая к этому числу степень двойки 27 = 0,0078125;
0,010375 - 0,0078125 = 0,0025625
Шаг 5: Сейчас работаем с числом 0,0025625. Ближайшая к этому числу степень двойки 2-9 = 0,001953125;
0,0025625 - 0,001953125 = 0,000609375
Последний получившийся остаток меньше чем 2-10 и если бы мы желали продолжать приближение к исходному числу, то нам бы понадобилось 2-11, но это уже превосходит требуемую точность, а, следовательно, расчёты можно прекратить и записать окончательное двоичное представление дробной части.
0,401 = 0,011001101
Как видно, преобразование дробной части десятичного числа в двоичное представление несколько сложнее, чем преобразование целой части. Для удобства пересчета в конце лекции приводится таблица степеней двойки.
Запишем алгоритм преобразования:
Исходные данные алгоритма: Буквой А будем обозначать исходную правильную десятичную дробь записанную в десятичной форме. Пусть эта дробь содержит N знаков.
Алгоритм
Действие 1. Определим количество необходимых двоичных знаков М из неравенства 10N < 2M
Действие 2: Цикл вычисления цифр двоичного представления (цифры после нуля). Номер цифры будем обозначать символом К.
1. Номер цифры = 1
2. Если 2-К > А
То в запись двоичного числа добавляем ноль
Иначе
§ в запись двоичного числа добавляем 1
§ А = А - 2-К
3. К = К + 1
4. Если К > М
§ то работа алгоритма завершена
§ Иначе переходим на пункт 2.
Переведите десятичные числа в двоичные
а) 3,6 б) 12,0112 в) 0,231 г) 0,121 д) 23, 0091
Вычитание двоичных чисел
Вычитать числа, будем столбиком, как и в десятичной записи. Общее правило тоже, что и для десятичных чисел, вычитание выполняется поразрядно и если в разряде не хватает единицы, то она занимается в старшем разряде. Рассмотрим следующий пример:
| - | ||||
| = |
Первый разряд. 1 - 0 =1. Записываем 1.
Второй разряд 0 -1. Не хватает единицы. Занимаем её в старшем разряде. Единица из старшего разряда переходит в младший, как две единицы (потому что старший разряд представляется двойкой большей степени) 2-1 =1. Записываем 1.
Третий разряд. Единицу этого разряда мы занимали, поэтому сейчас в разряде 0 и есть необходимость занять единицу старшего разряда. 2-1 =1. Записываем 1.
Проверим результат в десятичной системе
1101 - 110 = 13 - 6 = 7 (111) Верное равенство.
Еще один интересный способ выполнения вычитания связан с понятием дополнительного кода, который позволяет свести вычитание к сложению. Получается число в дополнительном коде исключительно просто, берём исходное число и заменяем в нем нули на единицы, единицы наоборот заменяем на нули и к младшему разряду добавляем единицу. Например, для числа 10010 дополнительный код будет 011011.
Правило вычитания через дополнительный код утверждает, что вычитание можно заменить на сложение если вычитаемое заменить на число в дополнительном коде.
Пример: 34 - 22 = 12
Запишем этот пример в двоичном виде. 100010 - 10110 = 1100
Дополнительный код числа 10110 будет такой:
01001 + 00001 = 01010.
Тогда исходный пример можно заменить сложением так:
100010 + 01010 = 101100.
Далее необходимо отбросить одну единицу в старшем разряде. Если это сделать то, получим 001100. Отбросим незначащие нули и получим 1100, то есть пример решён правильно
