Деление двоичных чисел

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

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

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

В машинах вместо сдвига делителя вправо осуществляется сдвиг остатка влево, что, по сути, ничего не изменяет.

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

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

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

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

2. Из делимого вычесть делитель. Если остаток отрицательный, перейти к пункту 3. В противном случае вычисление закончить (произошло переполнение).

3. Запомнить знак остатка.

4. Сдвинуть остаток на один разряд влево.

5. Присвоить делителю знак, обратный знаку остатка, запомненному в п.2.

6. Сложить сдвинутый остаток и делитель (с учетом знака).

7. Присвоить цифре частного значение, противоположное коду знака остатка.

8. Повторять выполнение пунктов 3—7 до тех пор, пока не будет обеспечена требуемая точность вычисления частного.

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

Деление целых ненулевых n-разрядных (не считая знаковых разрядов) чисел А:В, представленных в прямом я простоты) коде, приводит к получению целого частоты С и целого остатка 0, которому присваивается знак делимого; знак частного вычисляется как сумма по модулю 1 операндов А и В.

Деление выполняется в следующей последовательности.

1. Делитель В сдвигается влево (нормализуется), так чтобы в старшем информационном разряде оказалась 1; подсчитывается количество сдвигов S; частное от деления может быть не более (S + 1) разрядов, не равных нулю.

2. Выполняется (S + 1) цикл деления модулей |А| на ||, где — нормализованное В, в результате находится (S + 1) разряд частного, начиная со старшего из (S +1) младших.

3. Полученный в последнем цикле деления остаток , если он положительный, сдвигается вправо на S разрядов; если же (отрицательный), то остаток восстанавливается: к нему добавляется ||, т.е.

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

4. Частному и остатку присваиваются знаки.

Основные логические операции выполняют логическое отрицание (!), логическое И (&&) и логическое ИЛИ (||). Операнды логических операций могут быть целого, плавающего или адресного типа. Типы первого и второго операндов могут быть различными. Операнды логических выражений вычисляются слева направо. Преобразования типов не производится, каждый операнд оценивается с точки зрения его эквивалентности нулю (операнд, равный 0, рассматривается как false, не равный нулю – как true).

Результатом логической операции является true и false. Результат операции логическое И имеет значение true только если оба операнда имеют значение true. Результат операции логическое ИЛИ имеет значение true, если хотя бы один из операндов имеет значение true. Если значения первого операнда достаточно, чтобы определить результат операции, второй операнд не вычисляется. Результатом логической операции является 0 или 1. Тип результата есть int.

Логическое отрицание даёт в результате значение 0, если операнд есть истина ( не нуль ), и значение 1, если операнд равен 0.

Информация хранится в памяти машины и обрабатывается процессором в двоичном виде. Формат записи данных в памяти называется внутренним представлением информации в ЭВМ. Применение двоичной системы счисления позволяет использовать для хранения информации элементы, имеющие всего два устойчивых состояния. Одно состояние служит для изображения единицы в соответствующем разряде числа, а другое – для изображения нуля. По такому же принципу изображают знак числа: 0- для знака “+”, 1-для знака “-”.

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

Прямой код используется для представления целого двоичного числа в виде: X_пр=a*a_n-1*a_n-2*…*a₁*a_0, где a- знаковый разряд; a_i- двоичные разряды числа.

Обратный код используется для представления отрицательных чисел путём постановки в знаковый разряд единицы и замены во всех других разрядах числа единиц нулями, а нулей единицами. Например, число X=-11011001 в обратном коде будет иметь вид X_обр=100100110.

Дополнительный код числа получают из обратного путём привлечения единицы к младшему разряду. Например, для числа X=-10100101: X_обр=101011010; X_доп=101011011.

Обратный и дополнительный коды положительного числа совпадают с представлением самого числа.

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

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

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

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

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

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

Например, число 137 в четыре байта будет записано так:

00000000 00000000 00000000 10001001

1-й байт 2-й байт 3-й байт 4-й байт

Из записи видно, что в младшем разряде записывается коэффициент при 2⁰, а в следующем – 2¹ и т.д.

Если во всех битах с 0-го по 30-й поместить 1, то мы получим максимальное целое положительное число, которое можно записать в слово.

01111111 11111111 11111111 11111111=2³¹-1

1-й байт 2-й байт 3-й байт 4-й байт

Представим число 95 как двоичное данное с фиксированной точкой.

-95=-1011111₂

Записываем двоичное число без знака в 4 байта:00000000 00000000 00000000 01011111;

Инвертируем:111111111 11111111 111111111 10100000;

Прибавляем 1 к младшему биту:11111111 111111111 11111111 10100001.

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

В общем виде любое число А может быть представлено в виде A=m*N^p, где m- мантисса числа, N- основание системы счисления; P- порядок числа, указывающий положение точки в изображении числа.

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

В зависимости от типа данных числа с плавающей точкой в памяти хранятся в одном из следующих форматов:

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

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

С целью упрощения аппаратной реализации арифметических операций в представлении числа знак порядка явно не сохраняется. В записи числа от порядка переходят к характеристике, которая получается из порядка путём прибавления поправочного коэффициента, для чисел типа float – 127, double – 1023, long double – 16383.

Представим число -18.2 с плавающей точкой: двоичное представление числа: -10010.001100110011; нормализованное представление числа: -1.0010001100110011…2¹⁰⁰; переходим от порядка к характеристике: 4+127=131=10000011₂.

Число 18.2 в формате float имеет вид:

В 16 с/с это число записывается так: С191999.

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

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

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

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

Институт стандартизации США (ANSI) ввёл в действие систему кодирования ASCII(American Standard Cord for Information Interchange). В системе ASCII закреплены две таблицы кодирования – базовая и расширенная. Базовая таблица закрепляет значение кодов от 0 до 127, а расширенная относится к символам с номерами от 128 до 255.

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

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

Аналогичные системы кодирования текстовых данных были разработаны и в других странах. Так, в СССР действовала система кодирования КОИ-7. Однако поддержка производителей оборудования и программ вывела американский код ASCII на уровень международного стандарта, и национальным системам кодирования пришлось «отступить» в расширенную часть системы кодирования, определяющую значения кодов со 128 по 255.

В России можно указать три действующих стандарта кодировки и ещё два устаревших. Кодировка символов русского языка Windows-1251 была введена компанией Microsoft. Она глубоко закрепилась и используется на большинстве локальных компьютеров, работающих на плотформе Windows.

Другая распространённая кодировка носит название КОИ-8. Сегодня эта кодировка имеет широкое распространение в компьютерных сетях на территории России и в российском секторе Интернета.

Международный стандарт, в котором предусмотрена кодировка символов русского алфавита, носит название кодировки ISO. На практике эта кодировка используется редко.