Имеют ли операции сдвига O(1) или O(n)?
Имеет ли смысл, что компьютеры обычно требуют больше операций, чтобы переместить 31 место вместо того, чтобы переместить 1 место?
Или имеет смысл количество операций, необходимых для переключения, константа, независимо от того, сколько мест нужно сдвинуть?
PS: интересно, является ли аппаратное обеспечение подходящим тегом.
Некоторые наборы инструкций ограничены одним сдвигом бит на инструкцию. И некоторые наборы инструкций позволяют указывать любое количество бит для переключения в одной инструкции, что обычно занимает один такт на современных процессорах (современный - преднамеренно неопределенное слово). См. dan04 answer о баррель-переключателе, схема, которая сдвигает более одного бита за одну операцию.
Все сводится к логическому алгоритму. Каждый бит в результате представляет собой логическую функцию, основанную на вводе. Для одного сдвига вправо алгоритм будет примерно таким:
Но логическое уравнение было бы так же легко:
Логические ворота, будучи асинхронными, могут делать все это за один такт. Тем не менее, верно, что один сдвиг позволяет ускорить тактовую частоту и уменьшить количество ворот, если все, что вы сравниваете, - эти два варианта команды. Или альтернатива заставляет занять больше времени, поэтому инструкция берет 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, будут склоняться к одной операции для переключения. Разверните все процессоры, но не обязательно "компьютеры", которые обычно используются сегодня, и они меняются другим способом, я бы сказал, что их количество больше одного бита, чем бит бит, поэтому для выполнения многобитового сдвига требуется несколько операций.
A barrel shifter позволяет выполнять сдвиг в O(log n) pass — который может быть выполнен в том же такте, что приводит к сдвигу операции O(1).
Как уже отмечалось, баррель-сдвиг может сдвигать операнд на произвольное расстояние в постоянное время. Тем не менее, баррель-распределитель потребляет значительное количество места на матрице процессора, поэтому они не включены во все конструкции процессора.
Как раз для одного довольно известного примера, Intel Pentium III включал в себя баррель-переключатель, но Pentium IV этого не делал. Код, написанный для Pentium III, предполагающий поворот ствола, иногда немного замедлился на Pentium IV. У меня был некоторый код шифрования (который включает в себя множество сдвигов и поворота), который работал примерно в 4 раза быстрее на Pentium III с тактовой частотой 1,2 ГГц, чем на Pentium IV с тактовой частотой 2,8 ГГц.
Бит-сдвиг - это O (1) практически для каждого текущего процессора.
Посмотрите, например, на инструкцию x86 "shrw". Первый операнд (в синтаксисе AT & T) - это количество бит для сдвига. Как компилятор реализует перенос, зависит от компилятора, но было бы глупо переносить сдвиги в цикл, когда процессор может сдвигать N бит за один раз.
Приложение: Re: "Требуется ли больше операций для сдвига влево 31?" Существуют разные виды сдвигов (если вам интересно, почему, подумайте о том, что делать с битами, которые сдвинуты с регистра), но большинство процессоров могут выполнять сдвиг с одной инструкцией на столько бит, сколько может хранить GPR. Для выполнения 40-битного сдвига в 32-битном регистре потребуется переключение на несколько регистров (это предполагает, что 64-разрядное число сохраняется в двух 32-разрядных регистрах), которые на каждом процессоре, о котором я знаю, потребуют больше инструкций. Это все равно будет O (1), вероятно, не 1 такт. В качестве интересной стороны процессор Pentium IV поразительно медленен при сдвиге бит. Это иронично, потому что Intel исторически рекомендовала оптимизацию ^ 2 делений и умножений путем смещения бит. См. этот PDF и Google для получения дополнительной информации, если вы заинтересованы.
Для обычного оборудования фиксированный размер регистрирует его постоянным независимо от того, сколько мест вы сдвигаете.
Также обратите внимание, что использование нотации O довольно странно здесь, вы обычно использовали бы его, чтобы обозначить алгоритмическую сложность, основанную на числе, чтобы сдвинуть не количество мест, которые нужно сдвинуть.
Ahem, проверил это из любопытства в С# и получил смешные результаты.
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 секунд. Не знаю, какие здесь оптимизации, но выглядит странно.
В качестве конкретного примера, в соответствии с таблицей C-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).