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

[Gabe]

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

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

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

[Gabe]

С элементами, кратными 2,4,8 понятно. Как найти числа, кратные 3 и 7?
не могу найти соответствующие признаки...

[SKov]

С элементами, кратными 2,4,8 понятно. Как найти числа, кратные 3 и 7?
не могу найти соответствующие признаки...

А чего там находить? Просто немного подумать...
Ну вот, например, в детстве когда-то писал функцию для получения остатка от деления на 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 тоже легко.
Если, конечно, подумать.
Сами догадаетесь?

[Палыч]

А чего там находить? Просто немного подумать...

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

Код

while (K > M) K= (K & M) + (K >> N);
if(K == M) return 0;
else return K;

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

Код

while (K > M) K= (K & M) + L * (K >> N);
if(K == M) return 0;
else return K;

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

Код

while (K > M) K= (K & ((1 << N) - 1)) + L * (K >> N);
if(K == M) return 0;
else return K;