Сергей-4030: Все сообщения за 3 Июня 2004 года

Он, наверно, хотел написать "запоминаешь остаток". Остаток потом нужно сдвинуть на четыре бита вместе с младшим байтом, опять поделить. И еще раз сдвинуть и еще раз поделить. Итого три деления, и два сдвига по четыре бита.

 

Ммм.... а поподробнее можно - с примером?




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

Возьмем число x. У него есть старший байт (u = x/256) и младший (l=x%256)

Тогда:

x= u*256 + l
x= u*250 + u*6 + l

x/10 = u*250/10+(6u+l)/10

x/10 = u*25 + (6u+l)/10

То есть алгоритм такой:

int division(int num) {
byte u=num/256; byte l=num%256;
int rem=6*u+l;
return u*25+(rem>256)?division(rem):rem/10;
}


Совершенно понятно, что ни рекурсивность ни "верхнеуровневость" не мешают - можно вполне реализовать на ассемблере без никаких проблем.

•  инфо
•  инструменты
• Ответить на сообщение

Очевидно, что идти дальше:

x/10 = u*25 + (6u+l)/10 = u*25 +6u/10 + l/10 мы не можем ибо тогда будут ошибки округления

•  инфо
•  инструменты
• Ответить на сообщение

Редактирования почему-то иногда не отражаются... Страничка в кэше?

•  инфо
•  инструменты
• Ответить на сообщение

Итого, R=6*r2+R3. Получили, что два деления 8-и битных, одно умножение - 8 битное, одно сложение. Если R>10, то рекурсивно

 

Причем максимальная глубина рекурсивного вложения, насколько я понимаю, равна единице.

•  инфо
•  инструменты
• Ответить на сообщение