Rozwiązanie firmowe zawiera 8 instrukcji.
suma: mov ecx, [esp + 4] mov eax, ecx ; Zamiast tych dwóch instrukcji można neg eax ; użyć instrukcji imul eax, ecx, -1 .petla: lea edx, [ecx + 2*ecx] ; trik edx := 3 * ecx bsr edx, edx add eax, edx loop .petla ret
Konrad Lipiński jako pierwszy podał krótsze rozwiązanie, zawierające 7 instrukcji.
suma: imul eax, [esp + 4], -1 imul ecx, eax, -3 .iter: bsr edx, ecx add eax, edx sub ecx, 3 jnz .iter ret
Konrad Lipiński podał też rozwiązanie z 6 instrukcjami. Zaoszczędzenie jednej instrukcji polega na przekazywaniu argumentu w rejestrze eax zamiast na stosie.
suma: lea ecx, [eax + 2*eax] .iter: bsr edx, ecx lea eax, [eax + edx - 2] sub ecx, 3 jnz .iter ret
W powyższych rozwiązaniach pętla wykonywana jest liniową liczbę razy w stosunku do wartości argumentu wejściowego. Piotr Stańczyk jako pierwszy podał rozwiązanie, w którym pętla wykonywana jest logarytmiczną liczbę razy.
suma: dec dword [esp + 4] mov eax, 0 mov edx, 1 mov ecx, 1 .petla: add eax, [esp + 4] sub [esp + 4], edx add edx, edx add edx, ecx imul ecx, -1 cmp [esp + 4], dword 0 jg .petla ret
Powyższe rozwiązanie można zoptymalizować z 12 do 9 instrukcji.
suma: imul eax, [esp + 4], -1 mov ecx, -1 xor edx, edx .petla: neg ecx lea edx, [ecx + 2*edx] add eax, [esp + 4] sub [esp + 4], edx jg .petla ret
Po kilku miesiącach Karol Środecki nadesłał rozwiązanie zawierające upragnione 12 instrukcji i działające w czasie stałym. Argument przekazujemy w rejestrze eax.
suma: lea ecx, [eax + 2*eax] ; ecx := 3*n bsr ecx, ecx ; ecx := h = floor(log2 3*n) mov edx, 0xAAAAAAAA ; edx := c = 101010...10 dec ecx imul eax, ecx ; eax := n*(h - 1) not ecx shr edx, cl ; edx := c >>= (32 - h) sub eax, edx ; eax := n*(h - 1) - c bsr edx, edx shr edx, 1 ; edx := q = number of 1's in c - 1 lea eax, [eax + edx + 1] ; eax := n*(h - 1) - c + q + 1 ret
Brawo, lepiej się już chyba nie da.