А чего там находить? Просто немного подумать...
Ну вот, например, в детстве когда-то писал функцию для получения остатка от деления на 3.

int Rest_3(int k)
{k=(k&63)+(k>>6);
k=(k&15)+(k>>4);
k=(k&3)+(k>>2);
k=(k&3)+(k>>2);
k=(k&3)+(k>>2);
if(k==3)return(0); else return(k);
}

Это работало вроде бы для 13-битового слова.
А если для произвольной разрядности числа, то, видимо, можно так записать тело функции,
хоть это будет и не оптимально по числу операций:

while (k>3) k=(k&3)+(k>>2);
if(k==3)return(0); else return(k);

Для остатка от деления на 7 тоже легко.
Если, конечно, подумать.
Сами догадаетесь?

кажется, для 7 будет:
while (k>7) k=(k&7)+(k>>3);
if(k==7)return(0); else return(k);

Сообщение отредактировал Gabe - May 28 2009, 16:38

Да, похоже. Надо бы поискать числа вида 2**n-1 , делящиеся на 7.
Тогда для многобитовых чисел первые шаги можно сделать более эффективно.
Как это было сделано в моем первом примере в первых строчках.

Забавно получается. Можно обобщить...
Проверка делимости (получение остатка от деления) числа К на M= 2^N - 1

P.S. Можно и дальше обобщить, но, наверное будет не так забавно
Проверка делимости (получение остатка от деления) числа К на M= 2^N - L

P.P.S. Ай-ай! Соврал!

Да, обычно так никто не делает. Умножение убивает идею.
Попробуйте сделать вычислитель остатка для числа 5. Без умножения или его имитации.
А я пока поищу в архиве )

Сообщение отредактировал SKov - May 29 2009, 08:30

Вспомнил - http://graphics.stanford.edu/~seander/bith...ModulusDivision

Вообще, рекомендую ознакомиться со всем документом - неплохая подборка чудных идей. Некоторые - за гранью моего понимания

Да, но вычислителя остатка при делении на 5 там нет.

Вот черт. Действительно... Хотя - это не вопрос. Умножаем вход на 3 и делим на 15

Ну, в своём посте я честно указал, что уж для любого случая получается, мягко говоря - некрасиво. Но, при L = степень двойки - "очень даже и нечего"!
Почему же - "без"? Почему имитацию умножения не применить? L= 3= 2 + 1 Оба слогаемых - степени двойки, получаем

P.S. Вот - чёрт! Опять поспешил... Правильно будет так:
или так

Все прально, только умножать не надо
А делить можно и на 255..

int Rest_5(int k)
{
k=(k&255)+(k>>8);
k=(k&15)+(k>>4);
k=(k&15)+(k>>4);
if(k>=10)k=k-10;
if(k>=5)k=k-5;
return(k);
}
Это я писал для 13-битового числа.
В общем виде можно поставить while в одном-двух местах
Правда, смысл первых строчек уже не помню...
Вот! Вспомнил наконец!
Общая идея, которой я руководствовался в детстве при написании этих программ, заключается в том,
что из числа можно вычесть любое число, кратное делителю, и при этом остаток от деления не изменится.

Смысл первых строчек немного в другом...

Для остатка от деления справедливо следующее
(А + В) % С = (А % С + В % С) % С
(А * В) % С = (А * (В % С)) % С

Число k можно представить как k= A*256 + B. Легко увидеть, что А= k >> 8; B= k & 255;
тогда искомый остаток от деления на 5 (назовём его R)
R= k % 5 = (A*256 + В) % 5 = ((A*256) % 5 + В % 5) % 5
Остаток от деления 256 на 5 равен 1 (это важно, т.к. результат умножения числа на единицу - есть само число, то есть, можно избавиться от умножения), тогда
(А*256) % 5 = (А * (256 % 5)) % 5 = (А * 1) % 5 = А % 5
Итак R= (A % 5 + В % 5) % 5 = (А + В) % 5, т.е. искомый остаток равен остатку от деления на 5 уже меньшего числа.
Из этих преобразований появилась строка в функции k=(k&255)+(k>>8);

Аналогично со строкой k=(k&15)+(k>>4); Все рассуждения - похожие, но число k представляется уже как k= А*16 + В

Ну вы тут и накрутили на ровном месте
Все намного проще:
R= k % 5 = (A*255 + В) % 5 = B%5
В первой строчке делается первый шаг поиска остатка от деления на 255.
В результате получаем некое B, которое значительно меньше исходного числа. И т.д.
Идея в том, что можно сначала искать модуль для бОльшего делителя, а затем работать с маленьким остатком дальше.
Главное условие в том, чтобы этот бОльший делитель был кратным маленькому делителю, для которого нас интересует конечный результат.
Нам подходят числа 15 и 255 в качестве бОльших делителей потому что
а) Для них легко искать остаток от деления
б) Они делятся на 5 нацело.
Ч.т.д.

Ну, тогда уж так:
R= k % 5= (А*256 + В) % 5= (А*255 + А + В) % 5= ((А*255)%5 + А + В) % 5= (А + В) % 5, поскольку (А*255) % 5= 0

Ну, осталось только замену переменных сделать A+B=b и получится ровно то,
что у меня записано, только заметно короче.

Согласен. Только помните, что спорим мы в разделе для начинающих, и не каждый дружен с математикой настолько, чтобы представить двоичное число в виде k= A*255+b, ведь 255 - это не степень двойки