2017-12-14
1450
Другим важным приложением поразрядных операций является моделирование программными средствами процессов аппаратной обработки данных на уровне отдельных битов, полей, слов различной размерности. Прежде всего это относится к моделированию (эмуляции) машинных операций с различными формами представления данных (машиннойарифметики).
Рассмотрим пример программы, в котором программно моделируются переменные произвольной размерности, представленные массивами беззнаковых байтов в форме, соответствующей их внутреннему представлению в памяти. В такой форме можно реализовать все арифметические операции по аналогичным алгоритмам, которые имеют место на аппаратном уровне в компьютере для базовых типов данных.
Операция сложения выполняется побайтно. Возникающий при сложении двух байтов перенос (8-й бит, выделяемый маской 0x0100) используется в операции сложения следующих двух байтов. Функция add осуществляет сложение целых произвольной разрядности.
Для эмуляции операции вычитания необходимо сформировать дополнительный код числа, произвести побайтную инверсию и добавить 1 к результату. Последнее можно сделать, установив первоначально в 1 перенос и распространив его по массиву байтов, аналогично сложению. Функция neg формирует дополнительный код отрицательного числа.
|
|
|
Для моделирования операции умножения необходимо реализовать операции сдвига на один разряд влево и вправо.
Операции сдвига на один разряд влево и вправо выполняют функции lshift и rshift соответственно.
В переменной carry запоминается значение старшего (младшего) бита, который переносится в следующий байт на место младшего (старшего).
В операции умножения реализован самый простой алгоритм сложения и сдвига. Он, как и все алгоритмы машинной арифметики для внутреннего представления данных, использует свойства двоичной системы
В произведении множитель bb раскладывается как сумма произведений двоичных разрядов на степени двойки. Известно, что n -я степень двойки эквивалентна сдвигу влево на n разрядов. Тогда при наличии 1 в n -м разряде множителя bb к произведению должен быть добавлен множитель аа, сдвинутый на n разрядов влево. При наличии 0 добавление не производится. Операцию умножения целых произвольной размерности выполняет функция mul.
В множителе bb подряд просматриваются все разряды, начиная с младшего (путем одноразрядного сдвига его вправо). Множимое аа при этом каждый раз сдвигается на один разряд влево (умножается на 2). Если очередной разряд множителя bb равен 1, то текущее сдвинутое значение множимого добавляется к произведению. Чтобы не усложнять программу, значения множимого и множителя не сохраняются.
|
|
|
В функции main демонстрируется работоспособность алгоритмов и соответствие их принятым формам представления данных. В качестве параметров функции взят базовый тип int, сформирован на него указатель как на область памяти, заполненную беззнаковыми байтами.
//Листинг 12.5
#include <iostream>
using namespace std;
typedef unsigned char uchar;
//Сложение целых произвольной разрядности
void add(uchar out[],uchar in1[],uchar in2[],int n)
{ int i, carry; // carry - бит переноса
//w-рабочая переменная для сложения двух байтов
unsigned w;
for (i=0, carry = 0; i<n; i++) {
out[i] = w =in1[i] + in2[i]+carry;
carry = (w & 0x0100)>>8;}
}
//Получение отрицательного числа в
//дополнительном коде
void neg(uchar in[], int n)
{ int i, carry; //carry - бит переноса
//w-рабочая переменная для сложения двух байтов
unsigned w;
for (i=0; i<n; i++) in[i]=~in[i];
for (i=0, carry=1; i<n; i++){
in[i] = w = in[i]+carry;
carry = (w & 0x0100)>>8;}
}
//Сдвиг влево целых произвольной разрядности
void lshift(uchar in[], int n)
{ int carry; //carry - бит переноса
int i,z;
for (carry=0, i=0; i<n; i++){
// Выделить старший бит (перенос)
z=(in[i] & 0x80)>>7;
// Сдвинуть влево и установить
in[i]<<= 1;
// старый перенос в младший бит
in[i] |=carry;
// Запомнить новый перенос
carry = z;
}
}
//Сдвиг вправо целых произвольной разрядности
void rshift(uchar in[], int n)
{ int carry; //carry - бит переноса
int i,z;
for (carry=0, i = n-1; i>=0; i--) {
// Выделить младший бит (перенос)
z = in[i] & 1;
// Сдвинуть вправо и установить
in[i] >>= 1;
// старый перенос в старший бит
in[i] |= carry<<7;
// Запомнить новый перенос
carry = z;
}
}
//Умножение целых произвольной разрядности
void mul(uchar out[],uchar aa[],uchar bb[],int n)
{ int i;
for (i=0; i<n; i++) out[i]=0;
// Цикл по количеству битов
for (i=0; i< n*8; i++){
// Разряд множителя равен 1
if (bb[0] & 1)
// Добавить множимое к произведению
add(out,out,aa,n);
// Множимое - влево
lshift(aa,n);
// Множитель - вправо
rshift(bb,n);
}
}
int main(){
setlocale(LC_CTYPE,"Russian");
int a=125000, b=30000, c;
int d=2,m=200,p=1000;
add((uchar*)&c, (uchar*)&a,
(uchar*)&b,sizeof(int));
cout<<"125000+30000 = "<<c<<'\n';
neg((uchar*)&d,sizeof(int));
add((uchar*)&c, (uchar*)&a,
(uchar*)&d,sizeof(int));
cout<<"125000-2 = "<<c<<'\n';
neg((uchar*)&b,sizeof(int));
add((uchar*)&c, (uchar*)&b,
(uchar*)&d,sizeof(int));
cout<<"-30000-2 = "<<c<<'\n';
neg((uchar*)&m,sizeof(int));
mul((uchar*)&c,(uchar*)&m,
(uchar*)&p,sizeof(int));
cout<<"-200*1000 = "<<c<<'\n';
return 0;}
Результаты выполнения программы:
125000+30000 = 155000
125000-2 = 124998
-30000-2 = -30002
-200*1000 = -200000
Задание.
Вариант 1
Программа деления целых чисел произвольной длины во внутреннем представлении с использованием операций вычитания, инкремента и проверки на знак результата, Частное определяется как количество вычитаний делителя из делимого ли появления отрицательного результата (проверить на переменных типа long).
Вариант 2
Программа деления целых чисел произвольной длины во внутреннем представлении с восстановлением остатка. Очередной разряд частного определяется вычитанием делителя из делимого. Если результат положителен, то разряд равен 1, если отрицателен, то делитель добавляется к делимому (восстановление остатка) и разряд частного считается равным 0. После каждого вычитания делимое и частное сдвигаются на один разряд влево. Перед началом операции делитель выравнивается с делимым путем сдвига на n/2 разрядов влево.
Вариант 3
Умножение чисел произвольной длины, представленных непосредственно строками цифр. Первоначально формируется строка символов произведения с необходимым количеством нулей. Далее для каждой пары цифр сомножителей к нему добавляется частичное произведение; значения цифр переводятся во внутреннюю форму и перемножаются, после чего выделяется младшая и старшая цифры результата, которые суммируются с соответствующими цифрами произведения с учетом переноса и его распространения в старшие цифры.
Вариант 4
Умножение чисел произвольной длины, представленных непосредственно строками цифр. Произведение формируется через многократное сложение одного из множителей с накапливаемым произведением, количество сложений определяется вторым сомножителем.
|
|
|
Вариант 5
Вычитание чисел произвольной длины, представленных непосредственно строками цифр с использованием дополнительного кода вычитаемого (в десятичной системе счисления).
Вариант 6
Кодирование и декодирование строки символов, содержащих цифры, в последовательность битов. Десятичная цифра кодируется четырьмя битами - одной шестнадцатеричной цифрой. Цифра F обозначает, что за ней следует байт (две цифры) с кодом символа, отличного от цифры. Разработать функции кодирования и декодирования с определением процента уплотнения.
Вариант 7
Кодирование и декодирование целых переменных различной размерности. Перед каждым числом размещаются пять битов, определяющие количество битов в следующем за ним целом числе; 00000 - конец последовательности. Разработать функции упаковки и распаковки массива переменных типа long с учетом количества значащих битов и с определением коэффициента уплотнения. Пример:
