Информатика и технология программирования
Машинная арифметика - целые произвольной точности - часть 2
in[i] >>= 1; // Сдвинуть вправо и установить
in[i] |= carry << 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<n; i++) out[i]=0;
for (i=0; i< n* 8; i++)
{ // Цикл по количеству битов
if (bb[0] & 1 ) // Разряд множителя равен 1
add(out,out,aa,n); // Добавить множимое к произведению
lshift(aa,n); // Множимое - влево
rshift(bb,n); // Множитель - вправо
}}