2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 Re: Кто знает задачки по ассемблеру (x86)?
Сообщение20.10.2010, 13:38 
Заслуженный участник


04/05/09
4546
Вот теперь хорошо. Разве что вместо последнего and лучше использовать movzx или movsx.

 Профиль  
                  
 
 Re: Кто знает задачки по ассемблеру (x86)?
Сообщение15.11.2010, 20:11 
Аватара пользователя


01/04/10
910
Вот моё решение. Использовал AT&T синтаксис.

(Оффтоп)

код: [ скачать ] [ спрятать ]
  1. .data 
  2. fmt: 
  3.     .string "%d" 
  4.  
  5. .text 
  6. func: 
  7.     pushl   %ebp 
  8.     movl    %esp, %ebp 
  9.  
  10.     movl    8(%ebp), %edx               # save arg (number N) in %edx 
  11.  
  12.     movl    $1, %esi                          # prepare flip counter C 
  13.  
  14. func_loop_start: 
  15.     cmpl    $1, %edx 
  16.     jbe     func_loop_end                  # repeat until N > 1 
  17.  
  18.     incl    %esi                                  # C++ 
  19.  
  20.     movl    %edx, %ebx                   # get max 2^k <= N 
  21.     bsrl    %ebx, %ecx                     #  
  22.     movl    $1, %ebx                        #  
  23.     shll    %cl, %ebx                        #  
  24.  
  25.     movl    %ebx, %eax                  # get mask = 2^k - 1 
  26.     decl    %eax                              #  
  27.  
  28.     andl    %eax, %edx                  # N <- (N % 2^k) ? N % 2^k : 2^k; 
  29.     cmpl    $0, %edx                      #  
  30.     jne     func_goto_loop_start     #  
  31.     movl    %eax, %edx                 #  
  32.  
  33. func_goto_loop_start:                   # end of loop 
  34.     jmp     func_loop_start              #  
  35. func_loop_end:                            #  
  36.  
  37.     notl    %esi                               # answer = ~(C % 2) 
  38.     andl    $1, %esi                       #  
  39.     movl    %esi, %eax                 #  
  40.  
  41.     leave 
  42.     ret 
  43.  
  44. .globl main 
  45. main: 
  46.     pushl   %ebp 
  47.     movl    %esp, %ebp 
  48.  
  49.     subl    $4, %esp 
  50.     movl    $1, -4(%ebp) 
  51.  
  52. main_loop_start: 
  53.     pushl   -4(%ebp) 
  54.     call    func 
  55.  
  56.     pushl   %eax 
  57.     pushl   $fmt 
  58.     call    printf 
  59.  
  60.     incl    -4(%ebp) 
  61.  
  62.     cmpl    $16, -4(%ebp)             # for example print out first 16 bits 
  63.     jbe     main_loop_start 
  64.  
  65.     pushl   $10 
  66.     call    putchar 
  67.  
  68.     movl    $0, %eax 
  69.     leave 
  70.     ret 


Теперь надо понять почему Ваши решения такие короткие.

 Профиль  
                  
 
 Re: Кто знает задачки по ассемблеру (x86)?
Сообщение15.11.2010, 21:21 
Аватара пользователя


01/04/10
910
есть ошибочка (хотя и с ней работает), я имел ввиду вот так:

(Оффтоп)

Код:
    andl    %eax, %edx                  # N <- (N % 2^k) ? N % 2^k : 2^k/2;
    cmpl    $0, %edx                      #
    jne     func_goto_loop_start     #
    movl    %ebx, %edx                  #
    shrl    %edx

 Профиль  
                  
 
 Re: Кто знает задачки по ассемблеру (x86)?
Сообщение15.11.2010, 21:46 
Заслуженный участник


04/05/09
4546
creative в сообщении #375555 писал(а):
Теперь надо понять почему Ваши решения такие короткие.
Потому что не считаем синус рядом Тейлора. ;-)

 Профиль  
                  
 
 Re: Кто знает задачки по ассемблеру (x86)?
Сообщение16.11.2010, 18:19 
Аватара пользователя


01/04/10
910

(Оффтоп)

Да, все действительно просто, надо было мне с самого начала на бумажке выписать первые номера $n$ в двоичном виде, а напротив их $a_n$, где даже зрительно заметно, что результат зависит от четности/нечетности количества единичных битов в $n$. Далее xor'им отлавливая пары битов, а после, когда остается один байт просто спрашиваем результат у машины (setnp).

 Профиль  
                  
 
 Re: Кто знает задачки по ассемблеру (x86)?
Сообщение16.11.2010, 22:28 
Аватара пользователя


01/04/10
910
Есть ещё задачи?

 Профиль  
                  
 
 Re: Кто знает задачки по ассемблеру (x86)?
Сообщение16.11.2010, 23:38 
Заслуженный участник


04/05/09
4546
Попробуйте посчитать количество единичных бит в 32-битном числе максимально быстрым позиционно-независимым кодом.
Вход и выход через eax.

 Профиль  
                  
 
 Re: Кто знает задачки по ассемблеру (x86)?
Сообщение17.11.2010, 06:31 


26/01/10
959
creative в сообщении #376233 писал(а):
Есть ещё задачи?

1. Перевернуть 32-битовое число без знака "задом наперёд". То есть сделать биты в обратном порядке.
2. Найти абсолютное значение 32-битового числа без использования ветвлений.

Вообще, можно открыть книжку Генри Уоррена мл. "Алгоритмические трюки для программистов" и решать там все задачи на ассемблере, потом сверить с его решениями на C.

(Оффтоп)

Цитата:
Попробуйте посчитать количество единичных бит в 32-битном числе максимально быстрым позиционно-независимым кодом.

Вот такая полезная операция, а появилась только недавно в виде POPCNT в SSE 4.2

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 23 ]  На страницу Пред.  1, 2

Модераторы: maxal, Toucan, PAV, Karan, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group