Помогите с алгоритмом!, проверка элементов массива на кратность 2^k Опции

[Gabe]

Помогите с алгоритмом, пожалуйста!
Нужно организовать проверку элементов массива на кратность 2^k, где k=1...4 unsure.gif

Делаю на ассемблере

Сообщение отредактировал Gabe - May 27 2009, 13:31

[Rst7]

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

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

[SKov]

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

Все прально, только умножать не надо
А делить можно и на 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 + В

[SKov]

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

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

Число 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 = (A*255 + В) % 5 = B%5

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

[SKov]

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

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

[Палыч]

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

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

[SKov]

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

А причем здесь двоичное число и способ его представления?
Все что мы писали в наших постах справедливо для десятичных чисел,
вполне доступных для понимания даже начинающих.
И в моих функциях используются исключительно десятичные числа.
Или я не понял замечания?