Сдвиг битов O (1) или O (n)?
Операции сдвига O (1) или O (n) ?
Есть ли смысл в том, что компьютеры обычно требуется больше операций для сдвига 31 разряда вместо сдвига на 1 место?
Или имеет смысл количество операций , необходимых для сдвига, является константой независимо от того, сколько мест нам нужно сделать shift?
PS: интересно, подходит ли hardware тег ..
4 ответа
Некоторые наборы команд ограничены одним битовым сдвигом на инструкцию. А некоторые наборы команд позволяют указывать любое количество битов для сдвига в одной инструкции, что обычно занимает один тактовый цикл на современных процессорах (современный - намеренно расплывчатое слово). См. ответ dan04 о бочкообразном сдвиге, схеме, которая сдвигает более одного бита за одну операцию.
Все сводится к логическому алгоритму. Каждый бит в результате является логической функцией, основанной на вводе. Для одного сдвига вправо алгоритм будет выглядеть примерно так:
- Если инструкция [сдвиг вправо] и бит 1 ввода равен 1, то бит 0 результата равен 1, иначе бит 0 равно 0.
- Если инструкция [сдвиг вправо], то бит 1 = бит 2.
- и т.д..
Но логическое уравнение может быть таким же простым:
- Если инструкция [сдвиг вправо] и операнд количества равен 1, то бит результата 0 = сдвинутый вход бит 1.
- если значение равно 2, то бит 0 = бит 2.
- и т. Д.
Логические вентили, будучи асинхронными, могут делать все это за один такт. Тем не менее, это правда, что единственная смена позволяет ускорить цикл и сократить количество гейтов, если вы сравниваете только эти два варианта инструкции. Или же альтернатива заключается в том, что для выполнения процедуры требуется больше времени, поэтому инструкция занимает 2 или 3 такта или что-то в этом роде, а логика считает 3, а затем фиксирует результат.
Например, MSP430 имеет только однобитовые команды поворота вправо (потому что вы можете выполнить однобитовый сдвиг или поворот влево с помощью другой инструкции, которую я оставлю читателю для выяснения).
Набор команд ARM допускает как немедленное, так и регистровое многобитовое вращение, арифметические сдвиги и логические сдвиги. Я думаю, что есть только одна действительная команда поворота, а другая является псевдонимом, потому что поворот влево 1 аналогичен повороту вправо 32, вам нужен только однонаправленный сдвиг барреля для реализации многобитового поворота.
SHL в x86 допускает более одного бита на инструкцию, но раньше занимало более одного такта.
и так далее, вы можете легко изучить любую из инструкций, изложенных там.
Ответ на ваш вопрос в том, что он не является фиксированным. Иногда это одна операция, один цикл, одна инструкция. Иногда это одна инструкция нескольких тактов. Иногда это несколько инструкций, несколько тактов.
Компиляторы часто оптимизируют для такого рода вещей. Скажем, у вас есть набор 16-битных регистров с байт-инструкцией подкачки и инструкция AND с немедленным, но только однобитовым сдвигом. Вы можете подумать, что для сдвига 8 битов потребуется 8 циклов смены команд, но вы можете просто поменять местами байты (одну инструкцию), а затем И нижнюю половину на нули (что может занять две инструкции или может быть инструкция переменной длины слова из двух слов, или он может быть закодирован в одну инструкцию), поэтому он занимает всего 2 или 3 цикла команд / тактов вместо 8. Для сдвига в 9 битов вы можете сделать то же самое и добавить сдвиг, сделав его 9 тактов против 3 или 4 Кроме того, на некоторых архитектурах умножение на 256 быстрее, чем сдвиг на 8 и т. Д. И т. Д. Каждый набор инструкций имеет свои ограничения и приемы.
Это даже не тот случай, когда либо большинство наборов инструкций предоставляют многобитовые, либо большинство ограничивается одним битом. Процессоры, относящиеся к категории «компьютер», такие как X86, ARM, PowerPC и MIPS, склоняются к одной операции на смену. Расширение на все процессоры, но не обязательно на «компьютеры», обычно используемые сегодня, и это сдвигает другой путь, я бы сказал, что большинство из них являются однобитными, а не многобитными, поэтому для выполнения многобитового сдвига требуется несколько операций.
Сдвиг битов - это O (1) практически на каждом текущем процессоре.
Взгляните, например, на инструкцию x86 "shrw". Первый операнд (в синтаксисе AT & amp; T) - это количество бит для сдвига. То, как компилятор реализует сдвиг, зависит от компилятора, но было бы глупо помещать сдвиги в цикл, когда процессор может сдвигать N бит за один раз.
Приложение: Re: «Требуется ли больше операций для смещения влево на 31?» Существуют различные виды сдвигов (если вам интересно, почему, подумайте, что делать с битами, которые сдвинуты из регистра), но большинство процессоров могут выполнять сдвиг одной команды на столько бит, сколько может сохранить GPR. Для выполнения 40-разрядного сдвига в 32-разрядном регистре потребуется переключение между несколькими регистрами (это предполагает, что 64-разрядное число хранится в 2 32-разрядных регистрах), что на каждом из известных мне процессоров потребует большего количества инструкций. Это все равно будет O (1), просто, вероятно, не 1 час. Интересно отметить, что процессор Pentium IV удивительно медленен в битовых сменах. Это иронично, потому что Intel исторически рекомендовала оптимизацию ^ 2 делит и умножает путем сдвига битов. См. этот PDF и Google для получения дополнительной информации.
Гм, проверил это из любопытства в c # и получил забавные результаты.
var sw = Stopwatch.StartNew();
long l = 1;
for (long i = 0; i < 20000000; i++) {
l = l << 60; l = l >> 60;
l = l << 60; l = l >> 60;
l = l << 60; l = l >> 60;
//...
// 50 of ^them^ total
}
Console.WriteLine(l + " " + sw.Elapsed);
Это занимает 1,2 секунды на моем ПК. Но если я заменю
l = l << 60; l = l >> 60;
на
l = l << 1; l = l >> 1;
, то время увеличивается до 2,0 секунд. Понятия не имею, какие здесь оптимизации, но это выглядит странно.
В качестве конкретного примера, согласно Таблица С-17. Общие инструкции из Справочного руководства по оптимизации архитектур Intel® 64 и IA-32 :
SAL/SAR/SHL/SHR reg, imm 1 cycle latency
SAL/SAR/SHL/SHR reg, cl 1.5 cycles latency
Так что это постоянный коэффициент, а O (1,5) = O (1 ). Могут быть более простые микроархитектуры как выбросы, но в целом O (1).