Информатика и технология программирования


Машинная арифметика - целые произвольной точности - часть 2



in[i] &#62&#62= 1; // Сдвинуть вправо и установить


in[i] |= carry &#60&#60 7; // старый перенос в старший бит


carry = z; // Запомнить новый перенос


}}

В переменной carry запоминается значение старшего (младшего) бита, который переносится в следующий байт на место младшего (старшего).

В операции умножения реализован самый простой алгоритм сложения и сдвига. В множителе bb подряд просматриваются все разряды, начиная с младшего (путем одноразрядного сдвига его вправо). Множитель при этом каждый раз сдвигается на 1 разряд влево (умножается на 2). Если очередной разряд множителя равен 1, то текущее сдвинутое значение множимого добавляется к произведению. Чтобы не усложнять программу, значения множимого и множителя не сохраняются:


//------------------------------------------------------bk48-04.cpp


//------Умножение целых произвольной разрядности


void mul(unsigned char out[], unsigned char aa[],
unsigned char bb[], int n)
{
int i;
for (i=0; i&#60n; i++) out[i]=0;
for (i=0; i&#60 n* 8; i++)
{ // Цикл по количеству битов


if (bb[0] &#38 1 ) // Разряд множителя равен 1


add(out,out,aa,n); // Добавить множимое к произведению


lshift(aa,n); // Множимое - влево


rshift(bb,n); // Множитель - вправо


}}





Начало  Назад  Вперед