Делимость на 7

Типа микроупражнения. Надеюсь такого не было.



Необходимо проверить делится ли число n на 7

не используя операций деления и умножения.



Вход: eax = n, 0 < n < 4294967296.

Выход: zf = 1, если (n mod 7) = 0. Иначе zf = 0.



P.S. Деление в столбик будет не лучшим решением

 

А своих вариантов нет?

 

Код (Text):

1. test7:
2.         mov edx,eax
3.         and edx,7
4.         shr eax,3
5.         add eax,edx
6.         cmp eax,7
7.         ja test7
8.         jz .exit
9.         xor eax,7
10.     .exit:
11.         ret

 

cresta

Если бы не было, то я бы и не запостил.

Этож не практическая задача. Сама собой в голову пришло.

Может кому-то еще интересно найти решение.

 

Black_mirror

шустро!

но у меня на одну инструкцию меньше получилось

 

Black_mirror

метод работает, если бинарное представление делителя состоит из одних единиц. (1,3,7,15,31...).

А если взять другие числа из известной "тройки" 7-11-13: например 11?

 

_G3

Ну раз n>0, тогда так

Код (Text):

1. test7:
2.         mov edx,eax
3.         and eax,7
4.         shr edx,3
5.         add eax,edx
6.         sub eax,7
7.         ja test7
8.         ret

 

cresta

Если я ничего не напутал, тогда

Код (Text):

1. test11:
2.         mov edx,eax
3.         shr eax,5
4.         and edx,31
5.         sub eax,edx
6.         jg test11
7.         sub eax,11
8.     .l:
9.         add eax,11
10.         js .l
11.         ret
12.  
13. test13:
14.         mov edx,eax
15.         shr eax,6
16.         and edx,63
17.         sub eax,edx
18.         jg test13
19.         sub eax,13
20.     .l:
21.         add eax,13
22.         js .l
23.         ret
24.  
25. test17:
26.         mov edx,eax
27.         shr eax,4
28.         and edx,15
29.         sub eax,edx
30.         jg test17
31.         sub eax,17
32.     .l:
33.         add eax,17
34.         js .l
35.         ret

 

Black_mirror

Супер! Я до такого не допер. Вот мое решение:

Код (Text):

1.  
2.     xor ebx,ebx
3. L10:
4.     add eax,ebx
5.     mov ebx,eax
6.     and ebx,7
7.     shr eax,3
8.     jnz L10
9.     cmp ebx,7
10.  

 

Black_mirror



Здорово. Я пытался как-то применить этот метод к 11 и 13, но нифига не получалось. Оказывается решение есть

 

n>0? Тогда самый короткий (но не самый быстрый) вариант такой:

Код (Text):

1. l1: sub eax, 7
2.     ja  l1

...но это брутфорс.

 

Можно воспользоваться арифметикой остатков.

Например, частный случай (трехзначное число):

(a₂*10²+a₁*10+a₀)mod 7

сравнимо с

(a₂+a₁*3+a₀)mod 7

и всё это должно быть сравнимо с 0 по модулю 7.

Итак,

a₂+a₁*3+a₀ должно быть кратно 7-ми.

Аналогично для чисел более высоких порядков.



Ну а разделить вышеприведенную сумму на 7 можно и брутфорсом

 

Dimson

Но проц считает не в 10-й системе счисления. Сначала число туда перевести надо.

Лучше распиши свой алгоритм для 8-й системы и получишь такое же решение как приводились выше.

 

_G3

Да, согласен

 

Продолжаем проверять делимость:

Код (Text):

1. test19:
2.         mov edx,eax
3.         and edx,15
4.         shr eax,4
5.         lea eax,[eax*3]
6.         sub eax,edx
7.         jg test19
8.         sub eax,19
9.     .l:
10.         add eax,19
11.         js .l
12.         ret
13.  
14. test23:
15.         mov edx,eax
16.         and edx,15
17.         shr eax,4
18.         imul eax,7; лень сдвигами делать
19.         sub eax,edx
20.         jg test23
21.         sub eax,23
22.     .l:
23.         add eax,23
24.         js .l
25.         ret

Что-то мне цикл с меткой .l совсем не нравится, вернее не нравится что перед ним нужно корректировать регистр, чтобы не пропустить случай, когда регистр уже равен нулю. Есть идеи как от этого избавиться?

 

Black_mirror

Проверить на 19 можно также как ты для 11,13,17 предложил:

Код (Text):

1.  
2. test19:
3.         mov edx,eax
4.         shr eax,9
5.         and edx,511
6.         sub eax,edx
7.         jg test19
8.         sub eax,19
9.     .l:
10.         add eax,19
11.         js .l

 

Если слегка изменить требования:

1)public mul

2)Выход: cf

Код (Text):

1.  
2.     cmp eax, 05555555Ah
3.     jbe @F
4.     sub eax, 055555554h
5.     cmp eax, 05555555Ah
6.     jbe @F
7.     sub eax, 055555554h
8. @@:
9.     imul eax,024924925h
10.     cmp eax,024924925h
11.  

Работает от одного до пяти раз быстрее, в зависимости от размера источника