Мелкие задачки для крупных мозгов 2

Тема в разделе "WASM.ZEN", создана пользователем The Svin, 4 мар 2005.

  1. The Svin

    The Svin New Member

    Публикаций:
    0
    Регистрация:
    6 июл 2003
    Сообщения:
    665
    Адрес:
    Russia
    Посчитать количество бинарных строк в dword

    Под бинарной строкой понимается непрерывные единички или нули.

    Пример в DWORD = FFFFFFFFh - одна бинарная строка

    столько же в 00000000h

    В 0000FFFF таких строк две

    столько же в 80000000h

    а вот в 10000000h - их 3
     
  2. masquer

    masquer wasm.ru

    Публикаций:
    0
    Регистрация:
    13 сен 2002
    Сообщения:
    890
    Адрес:
    Николаев
    может можно и проще, но лень и позднее время мешают:
    Код (Text):
    1. mov eax, 10000000h ; sample value
    2.     mov edx, 1
    3.     mov ebx, eax
    4.     and ebx, 1
    5.     mov ecx, 32
    6.     xor edi, edi
    7. @@:
    8.     shr eax, 1
    9.     adc edi, 0
    10.     xor ebx, edi
    11.     add edx, ebx
    12.     mov ebx, edi
    13.     xor edi, edi
    14.     dec ecx
    15.     jnz @B
    16.     mov eax, edx
     
  3. The Svin

    The Svin New Member

    Публикаций:
    0
    Регистрация:
    6 июл 2003
    Сообщения:
    665
    Адрес:
    Russia
    Первые крупные мозги подключились. Это радует.

    Один из вариантов "ответного" кода
    Код (Text):
    1.  
    2. SignalCountsDword proc DwIn
    3.    
    4.     mov eax,DwIn
    5.     sub ecx,ecx
    6.     test eax,eax
    7.     jne @F
    8.     lea eax,[ecx][1]
    9. @r:
    10.     ret
    11. @@: lea edx,[eax-1]
    12.     add ecx,1
    13.     or eax,edx
    14.     lea edx,[eax+1]
    15.     and eax,edx
    16.     jne @B
    17.     mov eax,DwIn
    18.     shr eax,1
    19.     sbb edx,edx
    20.     shr eax,30
    21.     sbb eax,eax
    22.     lea eax,[eax][edx][1]
    23.     lea eax,[eax][ecx*2]
    24.     jmp @r
    25.  
    26. SignalCountsDword endp
    27.  
     
  4. masquer

    masquer wasm.ru

    Публикаций:
    0
    Регистрация:
    13 сен 2002
    Сообщения:
    890
    Адрес:
    Николаев
    Да, мой код очень легко адаптируется для непрерывного массива (задача №7(?)), а не только одного значения
     
  5. _BC_

    _BC_ БЦ

    Публикаций:
    0
    Регистрация:
    20 янв 2005
    Сообщения:
    759
    Такой вариант... Вход - EDX, выход - EBX (можно любые написать).
    Код (Text):
    1.  
    2.     xor  ebx, ebx
    3.     shr  edx, 1
    4.     salc
    5.     mov  ah, al
    6.     mov  ecx, 31  ;(
    7. l1: shr  edx, 1
    8.     salc
    9.     cmp  al, ah
    10.     jz  l2
    11.     inc  ebx
    12.     mov  ah, al
    13. l2: loop l1
     
  6. Black_mirror

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.035
    Код (Text):
    1.  mov eax,num
    2.   mov ecx,eax
    3.   sar ecx,1
    4.   xor ecx,eax;число строк=числу единичных бит +1
    5.   sub eax,eax
    6. .l0:
    7.   inc eax
    8. .l1:
    9.   add ecx,ecx
    10.   ja .l1
    11.   jc .l0
     
  7. ava

    ava New Member

    Публикаций:
    0
    Регистрация:
    11 окт 2003
    Сообщения:
    169
    Код (Text):
    1.  
    2. mov eax,DwIn
    3. xor ecx,ecx
    4. xor edx,edx
    5. shr eax,1
    6. sbb ebx,ebx
    7. mov cl,31
    8. inc edx
    9. xor eax,ebx
    10.  
    11. @MLoop:
    12.  
    13. shr eax,1
    14. sbb ebx,ebx
    15. adc dl,dh
    16. xor eax,ebx
    17. loop    @MLoop
    18.  
    19. xchg    eax,edx ; EAX - результат
    20.  
     
  8. Tupo

    Tupo New Member

    Публикаций:
    0
    Регистрация:
    21 янв 2005
    Сообщения:
    69
    Адрес:
    Moscow
    Код (Text):
    1.  
    2.     mov eax, inDWORD
    3.  
    4.     mov ebx, eax
    5.     not eax
    6.     ror ebx, 1
    7.     xor eax, ebx
    8.  
    9.     xor edx, edx
    10.     mov ecx, 32
    11.     inc edx
    12. M0:
    13.     shr eax, 1
    14.     jc  M1
    15.     inc edx
    16. M1:
    17.     loop    M0
    18.  
    19.     mov Result, edx
    20.  
     
  9. Tupo

    Tupo New Member

    Публикаций:
    0
    Регистрация:
    21 янв 2005
    Сообщения:
    69
    Адрес:
    Moscow
    Удалил нафиг второй вариант :)
     
  10. bogrus

    bogrus Active Member

    Публикаций:
    0
    Регистрация:
    24 окт 2003
    Сообщения:
    1.338
    Адрес:
    ukraine
    С подсчетом бит по Уоррену
    Код (Text):
    1. mov   eax,dword
    2.  
    3. mov   ecx,eax
    4. sar   ecx,1
    5. xor   eax,ecx
    6.  
    7. mov   ecx,eax
    8. shr   ecx,1
    9. and   ecx,55555555h
    10. sub   eax,ecx
    11. mov   edx,eax
    12. and   edx,33333333h
    13. shr   eax,2
    14. and   eax,33333333h
    15. add   edx,eax
    16. mov   ecx,edx
    17. shr   ecx,4
    18. add   ecx,edx
    19. and   ecx,0F0F0F0Fh
    20. mov   edx,ecx
    21. shr   edx,8
    22. add   edx,ecx
    23. mov   eax,edx
    24. shr   eax,16
    25. lea   eax,[eax+edx+1]
    26. and   eax,03Fh
     
  11. Tupo

    Tupo New Member

    Публикаций:
    0
    Регистрация:
    21 янв 2005
    Сообщения:
    69
    Адрес:
    Moscow
    bogrus





    Идея со сдвигом и последующим исключением хороша, но имеет недостаток!



    Если последний бит - это "битовая строка" длиной в 1 бит, то он выпадает и результат становится неверным.

    Пример: 00000002



    В моём случае, ror также не спасает, так как если первый и последний биты dword не равны, а последняя битовая строка длиной более 1 бита, то получается лишняя битовая строка.

    Пример: 00000003



    Так что - надо думать :\



    Пока что самое оптимальное решение у _BC_
     
  12. The Svin

    The Svin New Member

    Публикаций:
    0
    Регистрация:
    6 июл 2003
    Сообщения:
    665
    Адрес:
    Russia


    ? Это как это низкоуровневый программист Tupo инетересно оценивает алгоритмы?



    В числе типа FFF0FFFF0 мой алгоритм вычисляет количество строк всего за два цикла. Кто-то анализировал как он работает? Он выполняется за <= x\2 циклов. Где x - количество строк (не бит, - строк).

    bogrus

    А биты то нам зачем считать? Нам строки посчитать нужно.



    Уоррена мы с Яном любим. Но по сравнению с нашей эльфийской книжкой "Кольца и стрелы" - его труд детский ;)
     
  13. _BC_

    _BC_ БЦ

    Публикаций:
    0
    Регистрация:
    20 янв 2005
    Сообщения:
    759




    У Black_mirror'a лучше ;) Я даже не стал посылать улучшенный вариант, а сразу переключился на задачу №4. Вот там мой вариант элегантен как рояль (по крайней мере по размеру)
     
  14. The Svin

    The Svin New Member

    Публикаций:
    0
    Регистрация:
    6 июл 2003
    Сообщения:
    665
    Адрес:
    Russia
    Нужно постараться избежать циклов в алгоритмах где количество циклов = количеству бит во входных данных.
     
  15. bogrus

    bogrus Active Member

    Публикаций:
    0
    Регистрация:
    24 окт 2003
    Сообщения:
    1.338
    Адрес:
    ukraine
    The Svin




    Так смысл, выделить границы битовых строк, а потом посчитать кол-во границ (еденичных битов)



    Tupo




    0x00000002=00000000000000000000000000000010b=3 строки

    0x00000003=00000000000000000000000000000011b=2 строки



    Ты не согласен, с результатом? Может есть ещё примеры?



    Имхо, если нужна скорость, я бы использовал подсчет по Уоррену (это примерно в десять раз быстрее большинства предложенных циклов, даже в 1,5 раза быстрее чем 2 прохода цикла The Svin при числе 0FFF0FFF0h), конечно при условии, что это работает правильно на всех числах, я позже обязательно перепроверю, пусть появится чуть больше свободного времени
     
  16. Tupo

    Tupo New Member

    Публикаций:
    0
    Регистрация:
    21 янв 2005
    Сообщения:
    69
    Адрес:
    Moscow
    bogrus



    Конечно не согласен ;)



    А в этом примере: 55555555h сколько строк? 33? ;)



    The Svin



    Производительность!

    Но твой вариант - не смотрел, каюсь :)
     
  17. Tupo

    Tupo New Member

    Публикаций:
    0
    Регистрация:
    21 янв 2005
    Сообщения:
    69
    Адрес:
    Moscow
    Упс, мессага задупилась - сорри.
     
  18. The Svin

    The Svin New Member

    Публикаций:
    0
    Регистрация:
    6 июл 2003
    Сообщения:
    665
    Адрес:
    Russia


    Ладно, проехали.

    Но всё же под производительностью можно разное понимать - эмпирику по тестам, оценку циклов и тп.



    Кстати я дал не самый быстрый из возможных. Только чтоб подтолкнуть в направлении. Мне интересней Ваши идеи - свои я и так знаю ;)
     
  19. bogrus

    bogrus Active Member

    Публикаций:
    0
    Регистрация:
    24 окт 2003
    Сообщения:
    1.338
    Адрес:
    ukraine
    Tupo


    Где 33?
    Код (Text):
    1. MOV EAX,55555555    ; EAX=55555555        ; 1010101010101010101010101010101b
    2.  
    3. MOV ECX,EAX         ; ECX=55555555
    4. SAR ECX,1           ; FL=CP, ECX=2AAAAAAA ; 0101010101010101010101010101010b
    5. XOR EAX,ECX         ; FL=P, EAX=7FFFFFFF  ; 1111111111111111111111111111111b
    6.  
    7. MOV ECX,EAX         ; ECX=7FFFFFFF
    8. SHR ECX,1           ; FL=CP, ECX=3FFFFFFF
    9. AND ECX,55555555    ; FL=P, ECX=15555555
    10. SUB EAX,ECX         ; EAX=6AAAAAAA
    11. MOV EDX,EAX         ; EDX=6AAAAAAA
    12. AND EDX,33333333    ; EDX=22222222
    13. SHR EAX,2           ; FL=CP, EAX=1AAAAAAA
    14. AND EAX,33333333    ; FL=P, EAX=12222222
    15. ADD EDX,EAX         ; EDX=34444444
    16. MOV ECX,EDX         ; ECX=34444444
    17. SHR ECX,4           ; ECX=03444444
    18. ADD ECX,EDX         ; ECX=37888888
    19. AND ECX,0F0F0F0F    ; FL=0, ECX=07080808
    20. MOV EDX,ECX         ; EDX=07080808
    21. SHR EDX,8           ; EDX=00070808
    22. ADD EDX,ECX         ; FL=A, EDX=070F1010
    23. MOV EAX,EDX         ; EAX=070F1010
    24. SHR EAX,10          ; FL=PA, EAX=0000070F
    25. LEA EAX,[EAX+EDX+1] ; EAX=070F1720
    26. AND EAX,3F          ; FL=0, EAX=00000020   ; 32d
     
  20. Tupo

    Tupo New Member

    Публикаций:
    0
    Регистрация:
    21 янв 2005
    Сообщения:
    69
    Адрес:
    Moscow
    bogrus





    Еще раз но медленнее...



    00000002 = 00000000000000000000000000000010 = 3 строки

    результат сдвига + xor = ...011 - 2 единицы, значит количество строк = количество "1" + 1. Так? Так!



    00000003 = 00000000000000000000000000000011 = 2 строки

    результат сдвига + xor = ...010 - 1 единица, значит количество строк = количество "1" + 1. Так? Так!



    55555555 = 1010101010101010101010101010101

    результат сдвига + xor = 11111111111111111111111111111111 - 32 единицы, и как же количество строк = 32 получилось? Я что-то не пойму :\