Сдвиг бит O (1) или O (n)?

Question

Операции смены O(1) или O(n)?

Имеет ли смысл, что компьютерам обычно требуется больше операций, чтобы сместить 31 место вместо смещения на 1 место?

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

PS: интересно, является ли аппаратное обеспечение подходящим тегом ..

Answer 1

A бочкообразный переключатель позволяет выполнять смещение за O(log n) проходов - что можно сделать за один и тот же тактовый цикл, что делает переключение операцией O(1).

Answer 2

Некоторые наборы команд ограничены одним битовым сдвигом на инструкцию. А некоторые наборы команд позволяют указывать любое количество битов для сдвига в одной инструкции, что обычно занимает один тактовый цикл на современных процессорах (современный - намеренно расплывчатое слово). См. ответ 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, склоняются к одной операции на смену. Расширение на все процессоры, но не обязательно на «компьютеры», обычно используемые сегодня, и оно сдвигается в другую сторону, я бы сказал, что большинство из них являются однобитными, а не многобитными, поэтому для выполнения многобитового сдвига требуется несколько операций.

Answer 3

Как уже отмечалось, бочкообразный сдвиг может сдвигать операнд на произвольное расстояние за постоянное время. Сдвиг ствола, однако, занимает довольно много места на кристалле ЦП, поэтому они не включены во все конструкции ЦП.

Только для одного довольно известного примера, Intel Pentium III включал переключатель ствола - но Pentium IV сделал не . Код, написанный для Pentium III, предполагающий наличие бочкообразного рычага, иногда немного замедляется на Pentium IV. У меня был некоторый код шифрования (который включает в себя множество смещений и поворотов), который работал примерно в 4 раза быстрее на Pentium III с частотой 1,2 ГГц, чем на Pentium IV с частотой 2,8 ГГц.

Answer 4

Сдвиг битов - это O (1) практически на каждом текущем процессоре.

Взгляните, например, на инструкцию x86 "shrw". Первый операнд (в синтаксисе AT & T) - это количество бит для сдвига. То, как компилятор реализует сдвиг, зависит от компилятора, но было бы глупо помещать сдвиги в цикл, когда процессор может сдвигать N бит за один раз.

Добавление: Re: «Они требуют больше операций, чтобы сместить влево 31?» Существуют различные виды сдвигов (если вам интересно, почему, подумайте, что делать с битами, которые сдвинуты из регистра), но большинство процессоров могут выполнять сдвиг одной команды на столько бит, сколько может сохранить GPR. Для выполнения 40-разрядного сдвига в 32-разрядном регистре потребуется переключение между несколькими регистрами (это предполагает, что 64-разрядное число хранится в 2 32-разрядных регистрах), что на каждом из известных мне процессоров потребует большего количества инструкций. Это все равно будет O (1), просто, вероятно, не 1 час. Интересно отметить, что процессор Pentium IV удивительно медленен в битовых сменах. Это иронично, потому что Intel исторически рекомендовала оптимизацию ^ 2 делит и умножает путем сдвига битов. См. этот PDF и Google для получения дополнительной информации, если вы заинтересованы.

Answer 5

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

Также обратите внимание, что использование обозначения O здесь довольно странно, вы обычно используете его для обозначения алгоритмической сложности, основанной на числе для смещения, а не на количестве мест для смещения.

Answer 6

Гм, проверил это из любопытства в 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 сек. Понятия не имею, какие здесь оптимизации, но выглядит странно.

Answer 7

В качестве конкретного примера, согласно Таблица 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).