Есть ли инструкция для инверсии порядка битов в целочисленном регистре
То есть чтобы, например, 00011001 стал 10011000.
Если нет, есть ли O(1) алгоритм, который бы это делал?

ЗЫ: про предварительно обсчитанный массив знаю, но это, ИМХО, крайняя мера.

цикл с командами и промежуточным регистром
RCL
RCR

Такой инструкции нет, но есть команда BSWAP, которая изменяет порядок следования байтов в 32-разрядных регистрах, конвертируя значения из вида машинного представления (младшая часть, старшая часть) в обычное представление (старшая часть, младшая часть) и наоборот В вашем случае можно использовать инструкции BSF(Побитное сканирование вперед) и BTS или инструкции сдвига и логического ИЛИ

Это сообщение отредактировал(а) Mikl_ - 12.11.2008, 10:58

Всем спасибо. Видимо, лучше всего таблицей :(

     

Kallikanzarid, если тебе так ненавистен цикл -- не обязательно переворачивать все 32 разряда. Достаточно выявить те байты, которые содержат ненулевые значения -- пример зеркалирования одного байтаА вообще по бинарным операциям рекомендую, Генри Уорен "Алгоритмические трюки для программистов" (Henry Warren "Hacker's Delight")

Это сообщение отредактировал(а) Mikl_ - 12.11.2008, 11:59

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

Это сообщение отредактировал(а) Kallikanzarid - 12.11.2008, 12:02

Kallikanzarid, вот поправка на 32-разрядные регистры (а можно и 64-х и 128 разрядные) Можно проверять также на "зеркальные" байты -- их тоже не нужно переворачивать 0000.0000 1000.0001 1100.0011 1110.0111 1111.1111 0100.0010 0110.0110 и т.д.

Это сообщение отредактировал(а) Mikl_ - 12.11.2008, 12:24

За книгу спасибо, обязательно почитаю.

Добавлено через 3 минуты и 31 секунду
Кстати, только что пришло в голову таблично преобразовывать каждый байт по отдельности (таблица всего 255 байт), а затем инвертировать уже порядок байт с помощью BSWAP. Вижу, ты тоже что-то такое придумал. 8)

Добавлено через 10 минут и 43 секунды
Что еще лучше, такой алгоритмический подход дает возможность писать код на С++, что менее головоломно.
А вот проверять зеркальные байты - ИМХО, не лучшая идея, так как это сделать не так то просто - уж точно дольше, чем тупо извлечь из таблицы.

Kallikanzarid, для табличного преобразования содержимого регистра AL в ассемблере есть специальная инструкция XLAT 

Буду иметь это ввиду, посмотрим, что скажет профилировщик.

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

Я делаю контрол, строящий график непрерывной функции одного аргумента. Поскольку я использую его для демонстрации алгоритмов интерполяции, было бы хорошо сделать кэш. Я решил использовать бинарное дерево на массиве, в котором реверз индекса элемента соответствует положению точки на отрезке [1, ~0], а его легко отобразить на требуемый мне. То есть, обходя дерево до определенной, тривиально вычисляемой глубины, и применяя реверз, я получаю набор точек, расположенных достаточно близко, чтобы ломаная по ним хорошо приближала кривую при данном масштабе.

Я еще не проверял алгоритм на деле, так что я вполне могу ошибаться. Так, может оказаться, что я вообще не прав и все это никогда не будет работать, или что преобразование индекса в абсциссу сложнее, чем я думал, но все еще практично. Поживем - увидим.