Все разработчики ОС знают, что существуют операции сдвига: логические и арифметические. Назначений у логических сдвигов много, их рассматривать не буду. Но вот задался я вопросом:
зачем нужен арифметический сдвиг?
Вопрос отнюдь не простой, попробуем рассмотреть ситуацию. Если мы сдвигаем влево, то арифметический сдвиг ничем не отличается от логического. При сдвиге вправо при нулевом бите знака также нет отличий. Единственная ситуация, где возникает отличие – это сдвиг вправо при единичном бите знака, в таком случае он размножается, сохраняя знак всего числа. Очевидный ответ на вопрос о необходимости такого сдвига – это деление числа со знаком на степени двойки, однако...
Если мы сдвигаем числа, кратные той степени двойки, на которую делим, то нет проблем (для простоты рассмотрим просто деление на два). Так, -4/2 должно быть -2. Проверим (на нибблах для простоты). Для деления на два нужно сдвинуть на один разряд. Было -4 = 1100, стало -2 = 1110. Всё сходится. Теперь поделим -3/2. И здесь возникают первые неприятности. Очевидно, -3 на 2 не делится, необходимо округлять. В какую сторону? У математиков принято так называемое "евклидово деление". При делении числа A на B должны получить частное Q и остаток R. Для всех видов деления результат должен удовлетворять следующему тождеству: A = B*Q+R. В данном случае при делении мы не рассматривали остаток, он виртуален – математически присутствует, но нигде не сохраняется. Однако при различении, куда надо округлять частное, важно рассматривать остаток. Итак, евклидово деление. При нём постулируется, что независимо от знаков делителя и делимого остаток всегда положителен (тривиальности про размер модуля остатка опустим). Что мы должны иметь при делении -3/2? Если мы сочтём, что результат должен быть -1, то остаток равен A-B*Q или -3-2*(-1) = -1. То есть, это не евклидово деление. Правильный результат должен быть -2! То есть, при делении отрицательного числа на положительное для евклидова деления надо округлять в сторону минус бесконечности. Посмотрим, что у нас со сдвигом. -3 = 1101. После сдвига 1110 = -2. Ура, всё сходится? Давайте проверим.
Код:
#include <stdio.h>
int main (void) {
printf ("%d %d\n", -3/2, -3%2);
}
-1 -1
Оба-на! Выходит, язык С подразумевает не евклидово деление? А какое тогда? Как мы видим из приведённых соотношений, тип деления целиком зависит от знака остатка. Евклидово - это всегда положительный остаток. Маленько поправив код выше узнаём, что знак остатка в С совпадает со знаком делимого. А что другие языки? Оказывается, из сотни языков программирования евклидово деление принято только в 8 языках: ABAP, Algol 68, Dart, Maple, Pascal, Scheme R6RS, Stata и Z3 theorem prover. Более того, даже в математических пакетах Matlab, R, Scheme деление неевклидово! Семь языков толком не определились, в 42 остаток имеет знак делителя и в 67 знак делимого (сумма больше ста т.к. некоторые языки имеют более одного оператора). То есть, почти весь компьютерный код (и даже некоторые математические пакеты) делят неевклидово, и из них большинство придерживается соглашения, принятого в С! Получается, арифметический сдвиг, давая теоретически правильный результат, практически бесполезен? Давайте посмотрим, какой код генерируют компиляторы. Скомпилируем функцию
Код:
int fun (int a) {
return a/64;
}
Опуская загрузку аргумента в регистр EAX получим следующее.
MS Visual Studio:
Код:
cdq
and edx, 63
add eax, edx
sar eax, 6
Арифметический сдвиг используется, но предваряется бит-хаком для получения корректного результата. Всего четыре инструкции.
Intel Parallel Studio:
Код:
mov ecx, eax
sar eax, 5
shr eax, 26
add eax, ecx
sar eax, 6
Прелестно! Пять инструкций, вместо одного аж три сдвига и одно сложение!
GCC:
Код:
lea edx, [eax+63]
test eax, eax
cmovs eax, edx
sar eax, 6
Ситуация как и в студии, только бит-хак выглядит по-другому.
Итак, выходит, что сам по себе арифметический сдвиг для деления на 2 почти бесполезен. И действительно, ведь при помощи сходных бит-хаков арифметический сдвиг можно эмулировать логическим сдвигом:
Код:
cdq
shr eax, 6
and edx, 0FC000000h
or eax, edx
Деление же выглядит не сильно сложней.
Для красоты картины покажу, как делит Clang, этот перл достойно повесить на "доску по
зорачёта":
Код:
mov ecx, 64
mov [ebp-4], eax
mov eax, [ebp-4]
cdq
idiv ecx
Мало того, что он пренебрёг любыми сдвигами, так он даже не стал оптимизировать деление на константу (специалисты знают, что вместо деления на константу лучше умножать на другую константу). Он просто поделил в лоб тяжеловесной инструкцией idiv! К тому же сгенерировал двойную зеркальную пересылку данных – зачем?? Вот вам и хвалёная оптимизация LLVM.
Ну и что мы имеем в итоге? Почти во всех процессорах есть инструкция арифметического сдвига, она довольно просто реализуется аппаратно. Практика показывает, что для реального деления она подходит плохо, фактически, незначительно отличаясь от реализации на логическом сдвиге. А некоторые компиляторы (не будем показывать пальцем), вообще пренебрегают ей для деления. Поэтому возвращаемся к исходно поставленному вопросу: зачем процессоры реализуют арифметический сдвиг? Лично я вижу две возможные причины:
1. Дань традиции и архитекторы не задумываются над связью инструкции с алгоритмом, где она будет использоваться. Логичней было бы, например, сделать специализированную готовую инструкцию деления целого числа со знаком на степень двойки. Возможно даже менять поведение "евклидово/неевклидово" этой инструкции, управляя флагами или используя их для коррекции результата (с приоритетом неевклидового деления).
2. Существует какое-то иное неизвестное мне применение, более часто используемое, чем традиционное деление на степень двойки. Если да, то какое?
Прошу высказать ваше мнение.
Вход
Регистрация
FAQ
Поиск
