Самый быстрый код для переворота 32-битного целого

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

Задача:
X=0001010111
В результате должно получится
X=1110101000

 

Для твоего конкретного примера подойдет NOT )

 

спасибо!
Но надо ж общую задачу решить.

 

Onix-Studio

Reversing Bits называется общий случай.

 

Код (Text):

1.    mov eax,0001010111
2.    xor ebx,ebx
3.    mov ecx,32
4. @1:
5.    shl ebx,1
6.    shr eax,1
7.    adc ebx,0
8.  
9.    loop @1

Результат в EBX

 

Спасибо!

Нашел вот это:
unsigned int reverse(register unsigned int x)
{
x = (((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1));
x = (((x & 0xcccccccc) >> 2) | ((x & 0x33333333) << 2));
x = (((x & 0xf0f0f0f0) >> 4) | ((x & 0x0f0f0f0f) << 4));
x = (((x & 0xff00ff00) >> 8) | ((x & 0x00ff00ff) << 8));
return((x >> 16) | (x << 16));

}

Оптимизировать тут особо нечего, значит и будет самый быстрый?

P.S. В поисках на любопытную страницу натолкнулся, думаю, многих заинтересует:
http://graphics.stanford.edu/~seander/bithacks.html

 

"Hackers Delight" почитай (Алгоритмические трюки по-нашему). А за ссылку спасибо.

 

А, вообще, такая тема была на форуме flatassembler'а. На неё помойму даже в факе ссылка есть.

 

Кажется это делалось так:

Код (Text):

1.         ; вход al, выход - al
2.         test al, 81h
3.         jp   skip1
4.         xor  al, 81h
5. skip1:  test al, 42h
6.         jp   skip2
7.         xor  al, 42h
8. skip2:  test al, 24h
9.         jp   skip3
10.         xor  al, 24h
11. skip3:  test al, 18h
12.         jp   skip4
13.         xor  al, 18h
14. skip4:

При этом никаких дополнительных регистров или областей памяти не используется.
При желании можно расширить до 32 бит, идея я думаю ясна.

 

Onix-Studio

Код (Text):

1. mov eax, 0001010111b   ; Исходное двоичное число из 10-ти цифр [eax = 00000000 00000000 00000000 01010111b]
2. mov ecx, 32 - 10           ; (кол-во бит в eax) - (кол-во бит исходного числа) [ecx = 22]
3. bswap eax                    ; Переворачиваем (отражаем) число [eax = 11101010 00000000 00000000 00000000b]
4. shr eax, cl                    ; Сдвигаем на 22 [eax = 00000000 00000000 00000011 10101000b]

Пробуй...

 

Блин...
Вместо mov ecx, 32 - 10, лучше mov cl, 32 - 10 - меньше занимает

 

распространнеое заблуждение, только сурс будет весить меньше из-за того, что название регистра ECX больше на байт CL

 

Vasil
bswap меняет порядок байтов, а не битов! Этот код не годится.

dermatolog
mov eax,0001010111
xor ebx,ebx
mov ecx,32
@1:
shr eax,1
adc ebx,ebx
loop @1

 

хм. Или Imm8 или Imm32, что же будет меньше весить
Для mov cl, XX опкод BAXX, для mov ecx, XX на 3 байта больше.

 

dr_dred
Если смотреть по скорости, то первое:
вместо loop @1 лучше использовать sub ecx, 1; jnz @1 - заметно увеличивается скорость

 

Дорогие врачи, dr_dred и dermatolog

xor eax, eax
mov ecx, 32
mov edx, 0001010111
@1:
shr edx, 1
adc eax, eax
sub ecx, 1
jnz @1

)

 

дада, обшибся, сорри

 

При вычислении быстрого преобразования Фурье (БПФ) неоходимо "отзеркалить" индексы массива:
Цитата из WASM.A&O Быстрое преобразование Фурье создал _DEN_:

Код (Text):

1.  
2. static void binrevers( double *a, int n )
3. {
4.   int i, j, k;
5.  
6.   for( j = i = 0; i < n - 1; i++ ){
7.     if( i < j ){
8.       double t  = a[j];
9.       a[j] = a[i];
10.       a[i] = t;
11.     }
12.     for( k = n / 2; k <= j; k /= 2 )
13.       j -= k;
14.     j += k;
15.   }
16. }

Напрямую здесь алгоритм для 32-бит не будет работать.
Как это быстро сделать для данного случая?

 

izebars, Vasil
Обменялись любезностями, грубые невоспитанные личности
В оношении оценок "самый быстрый" или "самый никчемный" код вы оба не правы, т.к. все варианты побитового сканирования дают разные результаты на разных камнях (особенно на "дебильных" P4). Например, не самый удачный вариант rcr+rcl дает ~176 тиков на P4 модель 2 (Northwood) и аж 300 тиков на P4E и Pentium D. Замена rcr+rcl на add eax,eax + rcr edx,1 несколько улучшает ситуацию - 150 и 250 тиков соотв-но. Зато вариант shr+adc на P4 модель 2 получается заметно хуже ~200 тиков, а на P4E гораздо лучше ~150 тиков. Все P4 не любят adc и rcr\rcl, но зато их устраивают совершенно примитивные варианты типа shr+mov+and+lea, которые на P6 и AMD будут явно медленнее

А заметное ускорение на всех процах можно получить только при групповой обработке бит, как в коде, приведенном Onix-Studio

 

респект вам Vasil и leo теперь приведу не просто код, а тот который в 2 раза быстрее всех перечисленных выше.
А если кто сделает быстрее то выложу и реально самый быстрый, состоящий из 8 команд.
Leo, в принципе с большей частью твоих умозаключений, я согласен. Только про битовую груповуху я не понял. Если не трудно приведи код желательно в асме, а пока этот лучший:

mov eax,0001010111b
times 32 dd $d211f8d1

И ваще не кто еще не превосходил меня в логике, потому что я самый умный самый догадливый и самый скромный.