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

Другим важным приложением поразрядных операций является моделирование программными средствами процессов аппаратной обработки данных на уровне отдельных битов, полей, слов различной размерности. Прежде всего это относится к моделированию (эмуляции) машинных операций с различными формами представления данных (машинной арифметики). В предлагаемом примере программно моделируются беззнаковые двоичные переменные произвольной размерности, представленные массивами беззнаковых байтов (то есть в форме внутреннего двоичного представления данных в памяти ). В такой форме можно реализовать все арифметические операции по аналогичным алгоритмам, которые имеют место на аппаратном уровне в компьютере для базовых типов данных.

Операция сложения выполняется побайтно. Возникающий при сложении двух байтов перенос (8-й бит с маской 0x0100) используется в операции сложения следующих двух байтов:

//------------------------------------------------------bk48-02.cpp

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

void add(unsigned char out[], unsigned char in1[],
unsigned char in2[], int n)
{int i;
int carry; // Бит переноса

unsigned w; // Рабочая переменная для сложения двух байтов

for (i=0, carry=0; i&#60n; i++)
{
out [i] = w = in1[i]+in2[i]+carry;
carry = (w &#38 0x0100) &#62&#62 8;
}}

Для моделирования операции умножения необходимо реализовать операцию сдвига на 1 разряд влево и вправо:

//------------------------------------------------------bk48-03.cpp

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

void lshift(unsigned char in[], int n)
{ int carry; // Бит переноса

int i,z;
for (carry=0, i=0; i&#60n; i++)
{
z=(in[i] &#38 0x80)&#62&#62 7; // Выделить старший бит (перенос)

in[i] &#60&#60= 1; // Сдвинуть влево и установить

in[i] |=carry; // старый перенос в младший бит

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

}}
void rshift(unsigned char in[], int n)
{
int carry; // Бит переноса

int i,z;
for (carry=0, i=n-1; i&#62=0; i--)
{
z = in[i] &#38 1; // Выделить младший бит (перенос)

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); // Множитель - вправо

}}

Содержание раздела