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

Посчитать количество бинарных строк в dword

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

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

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

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

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

а вот в 10000000h - их 3

 

может можно и проще, но лень и позднее время мешают:

Код (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

 

Первые крупные мозги подключились. Это радует.

Один из вариантов "ответного" кода

Код (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.  

 

Да, мой код очень легко адаптируется для непрерывного массива (задача №7(?)), а не только одного значения

 

Такой вариант... Вход - 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

 

Код (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

 

Код (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.  

 

Код (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.  

 

Удалил нафиг второй вариант

 

С подсчетом бит по Уоррену

Код (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

 

bogrus

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



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

Пример: 00000002



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

Пример: 00000003



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



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

 

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



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

bogrus

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



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

 

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

 

Нужно постараться избежать циклов в алгоритмах где количество циклов = количеству бит во входных данных.

 

The Svin

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



Tupo

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

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



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



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

 

bogrus

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



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



The Svin

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

Но твой вариант - не смотрел, каюсь

 

Упс, мессага задупилась - сорри.

 

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

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



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

 

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

 

bogrus

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



00000002 = 00000000000000000000000000000010 = 3 строки

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



00000003 = 00000000000000000000000000000011 = 2 строки

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



55555555 = 1010101010101010101010101010101

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