гда n S -43rf + {d-l) или n < -43d + d . Для отрицательного делителя первый бит частного будет равен 1 тогда и только тогда, когда п > -43d (при модульном делении г О). Таким образом, первый бит частного равен 1 тогда и только тогда, когда

{d>0&-,{n-43d + d))\{d<0&n>-43d). Игнорируя возможное нулевое значение d, можем записать это выражение как

d >0®п>с,

где с = -43d + d при положительном da с = -43d при d отрицательном.

Так выглядит логика определения бита частного для нечетной позиции. Для четной позиции логика обратная. Из-за этого условие в операторе if включает проверку (i&l) ==0 (напомним, что символ * в языке С означает операцию исключающее или).

При каждой итерации с устанавливается равным наименьшему (наиболее близкому к 0) целому числу с единичным битом в позиции i после деления на d. Если текущий остаток г превышает это значение, бит i числа q устанавливается равным 1, а г корректируется путем вычитания числа, представляющего собой 1 в этой позиции, умноженного на делитель d. Реальное умножение при этом не требуется - d просто соответствующим образом позиционируется, после чего выполняется вычитание.

Алгоритм трудно назвать элегантным. Его очень трудно реализовать из-за ряда сложений, вычитаний, сравнений и даже умножения (на константу), которые должны быть выполнены в начале. Надеяться на существование "однородного" алгоритма, т.е. алгоритма, в котором действия одинаковы вне зависимости от знаков аргументов, для системы счисления по основанию -2, по-видимому, не приходится. Причина в том, что деление представляет собой, по сути, неоднородный процесс. Рассмотрим простейший алгоритм на основе сдвигов и вычитаний. Такой алгоритм может вовсе не использовать сдвиги и для положительных аргументов использовать только итеративное вычитание делителя из делимого с подсчетом количества вычи-J таний до тех пор, пока остаток не окажется меньше делителя. Однако, если делимое отрицательно (а делитель положителен), процесс будет состоять в итеративном прибавлении делителя к делимому, пока остаток не станет неотрицательным (частное при этом будет представлять собой количество сложений с обратным знаком). Процесс будет иным, если делитель отрицателен.

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

Алгоритм, приведеншлй выше, можно сделать в определенном смысле более однородным, дополняя делитель, если он отрицателен, а затем выполняя упрощенные для случая d>0 шаги. В конце алгоритма выполняется окончательная коррекция. Для модульного деления коррекция изменяет знак частного и оставляет неизменным остаток. Такое изменение алгоритма выносит некоторые проверки за пределы цикла, но особой красоты алгоритму в целом не прибавляет.

Интересно сравнить распространенные представления чисел и числа в системе счисления по основанию -2 в аспекте однородности при выполнении четырех арифметических

операций. Точного определения понятия "однородность" нет, но можно понимать под этим наличие или отсутствие операций, вьшолняемых в зависимости от знака аргументов. Мы считаем операцию однородной, если знаковый бит результата равен исключающему или от знаковых битов аргументов операции. В табл. 12.2 показано, какие из операций и при работе с какими представлениями чисел рассматривают свои аргументы однородно.

Таблица 12.2. Однородность операций при использовании разных представлений чисел

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

В случае умножения чисел в дополнительном к 2 представлении запись "Да" справедлива только в случае, если нас интересует только правая половина двойного слова произведения.

Завершим это рассмотрение системы счисления по основанию -2 некоторыми наблюдениями, касающимися вьшолнения преобразований между числами в этой системе счисления и обычными двоичными числами.

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

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

Двоичное из системы счисления по основанию -2

110111 (-13) - 1 о 1 (двоичное

--------- вычитание)

...111110011 (-13)

В систему счисления по по основанию -2 из двоичного

110111 (55) +10 1 (сложение по

--------- основанию -2)

1001011 (55)

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

Приведенный выше алгоритм преобразования в число в системе счисления по основанию -2 не поддается легкой программной реализации на двоичном компьютере, поскольку требует выполнения сложения в соответствии с правилами сложения чисел в системе счисления по основанию -2. Шреппель (Schroeppel) [25, item 128] преодолел эго препятствие, разработав более ясный и практичный метод выполнения преобразований в обоих направлениях. Для преобразования в двоичное число его метод вьп-лядит следующим образом:

В<г-(ЛГФОЫО. .1010)-0Ы0...1010.

Чтобы убедиться, что этот метод работает, рассмотрим число, которое в системе счисления по основанию -2 имеет вид abed. Тогда, если (некорректно) рассматривать его как обычное двоичное число, его значение равно 8a + 4b + 2c + d . После выполнения операции исключающее или это число, рассматриваемое как двоичное, равно 8(1 - а) + 4fe + 2(1 - с) + rf . После

(двоичного) вычитания получаем значение -8а + - 2с + rf, которое представляет собой значение числа abed в системе счисления по основанию -2.

Формула Шреппеля может быть легко разрешена для выполнения обратного преобразования, давая нам метод преобразования в обратном направлении, требующий выполнения трех команд. Ниже приведены формулы для преобразования в двоичное число на 32-битовой машине.

В <г- (ЛГ & 0x55555555)-(ЛГ &х55555555), B<r-N-{{N& ОхАААААААА)«1), B<r-{N® ОхАААААААА) - ОхАААААААА.

Для преобразования числа в систему счисления по основанию -2 используется следующая формула:

N<r-{B+ ОхАААААААА) Ф ОхАААААААА .

12.2. Основание -1+/

Используя в качестве основания системы счисления -1 +1, где i обозначает -J-i, все комплексные целые числа (т.е. комплексные числа, действительная и мнимая части которых целые) можно выразить в виде одного "числа" без явного использования знака или других вспомогательных средств. Приятной неожиданностью оказывается то, что это можно осуществить только при помощи цифр О и 1, причем все целые числа имеют при этом однозначное представление. Не будем здесь доказывать этот факт, как и многие другие, только опишем вкратце свойства данной системы счисления.

Не так уж тривиально оказывается выяснение того, как следует записать целое число 2 в этой системе счисления. Однако эта задача вполне разрешима путем последовательного деления 2 на основание системы счисления и записи остатков. Но что такое остаток от деления в данном контексте? Мы хотим, чтобы остаток после деления на -l + i был

Попробуйте сделать это самостоятельно, отложив на время книгу. 12.2 ОСНОВАНИЕ-1+1 221