9.1. Биты. Байты. Машинные слова
Основы внутреннего представления данных в компьютере мы уже проходили (см. 1.3). Единство этого представления состоит в том, что все они строятся на основе машинных слов (или байтов). Пока мы используем определенные в языке операции, присущие этим типам данных (например, операцию сложения целых переменных или косвенное обращение по указателю), внутренние представление данных нам безразлично. Но иногда нам приходится «лезть внутрь» и работать с ними на уровне отдельных двоичных разрядов. Примеры такого программирования:
упаковка данных, архивирование. Естественно уплотнение данных производить с точностью не до байта, а до бита;
алгоритмы сортировок и структуры данных, использующие элементы внутреннего представления хранимых данных: поразрядные сортировки, кодовые деревья;
моделирование машинной арифметики. Если нас не устраивает точность представления данных, принятая в компьютере, мы сможем программно смоделировать данные более высокой точности. При этом можно пользоваться разными формами их представления, в том числе принятыми двоичными форматами данных;
работа с растрами, битовыми картами (bitmap). Например, для контроля свободного пространства на диске файловая система часто использует карту памяти – массив байтов, каждый разряд которого определяется состояние отдельного блока: 0 – свободен, 1 – занят.
Машинные слова в Си. Базовые типы данных целых чисел реализованы в машинных словах различной размерности, поэтому для задания в программе машинных слов нужно просто определить ту или иную целую переменную. Тип данных char всегда соответствует байту, int – стандартной размерности машинного слова, обрабатываемого процессором, long – машинному слову увеличенной размерности по отношению к стандартному (обычно двойной). Операция sizeof, определяющая размерность любого типа данных в байтах, может быть использована и для «измерения» машинных слов, количество двоичных разрядов в машинном слове определяется выражением 8*sizeof(тип данных).
long vv; // Машинное слово двойной длины
for (int i = 0; i < 8*sizeof(long); i++) // Количество разрядов в long
{ … vv … } // Цикл поразрядной обработки словаПоразрядные операции и их интерпретация
Операции, которые выполняют различные операции (в основном, логические) над отдельными разрядами машинного слова, называются поразрядными. В стандартной классификации операций по приоритетам они относятся к различным группам. В качестве операндов у них часто используются константы, именуемые масками. Маска – это константа, с определенной расстановкой единичных и нулевых разрядов. Естественно, коль скоро речь идет о двоичном представлении, то наиболее удобным является использование эквивалента в виде шестнадцатеричных констант.
Прежде всего, необходимо вспомнить основные отношения размерностей (1.3): одна шестнадцатеричная цифра кодирует значения четырех двоичных разрядов (тетрада), байт представляется двумя цифрами. Как правило, в маске устанавливаются в 1 отдельные разряды, либо группы рядом стоящих разрядов (битовые поля):
0x1F - 0000 0000 0001 1111 (разряды 0..5 в 1)
0x3C0 - 0000 0011 1100 0000 (разряды 6..9 в 1)
0x1 - 0000 0000 0000 0001 (младший разряд)
Часто требуется, чтобы маска была программируемой, задаваемой во время работы программы. В этом случае нужно организовать процесс «пробегания» единичного бита по заданному полю.
Образно говоря, машинное слово – это массив двоичных разрядов, и алгоритмы работы с машинными словами в первом приближении аналогичны алгоритмам, работающим с массивами. Но с точки зрения возможных операций все обстоит с точностью до «наоборот». В «джентльменском наборе» команд процессора отсутствую команды прямой адресации битов. Взамен их используются поразрядные операции, выполняющие одну и ту же логическую операцию или операцию перемещения над всеми разрядами машинного слова одновременно. Другое их название – машинно-ориентированные операции – отражает тот факт, что они поддерживаются в любой системе команд и любом языке Ассемблера. К ним относятся:
"|" - поразрядная операция ИЛИ
"&" - поразрядная операция И;
"^" - поразрядная операция исключающее ИЛИ;
"~" - поразрядная операция инверсия;
">>" - операция сдвига вправо;
"<<" - операция сдвига влево.
Рис.91-1. Схема выполнения поразрядных операций
Формальная сторона логических операций всем известна. Однако программиста интересует содержательная интерпретация поразрядных операций, которая позволяет выполнять различные действия с отдельными разрядами и их диапазонами – битовыми полями – устанавливать, очищать, выделять, инвертировать. Для этого используют поразрядные операции, в которых первый операнд является обрабатываемым машинным словом. Второй операнд, как правило, определяет те разряды в первом операнде, которые изменяются при выполнении операции и в этом случае называется маской. Если маска жестко задана в программе, то является просто битовой константой, представленной в шестнадцатеричной системе.
Поразрядная операция И. По отношению ко второму операнду – маске логическая операция И сохраняет (выделяет) те разряды первого операнда, которые соответствуют единичным разрядам маски, и безусловно сбрасывает в 0 разряды результата, которые соответствуют в маске заполнены нулями. Операция так и называется - выделение разрядов по маске.
x x x x x x x x - операнд
0 0 1 1 1 0 0 0 - маска
0 0 x x x 0 0 0 - результат
b = a & 0x0861; // Выделить разряды 0,5,6,11
b = a & 0x00F0; // Выделить разряды с 4 по 7
// (разряды второй цифры справа)Выделение разрядов по маске может сопровождаться проверкой их значений.
if ((a & 0x100)!=0) … // Установлен ли 8-ой разряд –
// (младший разряд второго по счету байта)Поразрядная операция ИЛИ. По отношению ко второму операнду – маске логическая операция ИЛИ сохраняет те разряды первого операнда, которые соответствуют нулевым разрядам маски, и безусловно устанавливает в 1 разряды результата, которые соответствуют единичным разряды маски. Операция так и называется - установка разрядов по маске.
x x x x x x x x - операнд
0 0 1 1 1 0 0 0 - маска
x x 1 1 1 x x x - результат
a |= 0x0861; // Установить в 1 разряды 0,5,6,11
a |= 0x00F0; // Установить в 1 разряды с 4 по 7
// (разряды второй цифры справа)Операция ИЛИ используется также для объединения значений непересекающихся битовых полей (логическое сложение), которые предварительно выделяются с помощью операции И.
int a=0x5555,b=0x4444,c;
c = a & 0xFFF0 | b & 0xF; // c = «aaab»В переменной c объединяются битовые поля, выделенные из a – три старшие шестнадцатеричные цифры (12 разрядов) и из b – младшая шестнадцатеричная цифра (4 разряда).
c <<=1; c |= b & 1; b >>=1;Содержимое слова с сдвигается влево, в результате чего «освобождается место» в самом правом его разряде. Затем операция И выделяет младший разряд из машинного слова b, который затем переносится в освободившийся разряд b с помощью операции ИЛИ.
Операция поразрядной ИНВЕРСИИ. Поразрядная инверсия меняет значение каждого разряда машинного слова на противоположное (инвертирует). Операция И в сочетании с инвертированной маской-константой производит очистку разрядов по маске.
a &= ~0x0861; // Очистить разряды 0,5,6,11, остальные сохранить
a &= ~0x00F0; // Очистить разряды с 4 по 7, остальные сохранить
// (разряды второй цифры справа)Поразрядная операция «исключающее ИЛИ». Поразрядная операция «исключающее ИЛИ» выполняет над парами разрядов в операндах логическую операцию исключающее или, называемую также неравнозначность или сложение по модулю 2 - результат равен 1 при несовпадении значений битов. По отношению ко второму операнду – маске логическая операция «исключающее ИЛИ» сохраняет те разряды первого операнда, которые соответствуют нулевым разрядам маски, и инвертирует те разряды результата, которые соответствуют единичным. Операция так и называется - инвертирование разрядов по маске.
a ^= 0x0861; // Инвертировать разряды 0,5,6,11
a ^= 0x00F0; // Инвертировать разряды с 4 по 7
// (разряды второй цифры справа)Операция СДВИГ ВЛЕВО. Поразрядная операция «сдвиг влево» переносит содержимое каждого разряда первого операнда на то количество разрядов влево, которое задано вторым операндом, освобождающиеся разряды справа заполняются нулями. Результат операции содержит сдвинутое машинное слово, а сами операнды не изменяется. Естественно, что от программиста не требуется вручную интерпретировать перемещение разрядов машинного слова. Каждое перемещение имеет свою содержательную интерпретацию.
a <<= 4; // сдвиг влево на одну шестнадцатеричную цифру;
a = 1<<n; // установить 1 в n-й разряд машинного слова.Операции сдвига часто используются для «подгонки» групп двоичных разрядов к требуемому их местоположению в машинном слове. После чего в дело вступают операции И, ИЛИ для выделения и изменения значений полей.
long a=0x12345678; // Поменять местами две младшие цифры
long b = a & ~0xFF | (a >>4) & 0xF | (a <<4) & 0xF0;Первая операция И очищает две младшие шестнадцатеричные цифры (8 разрядов), вторая операция перемещает первую цифру на место нулевой (и выделяет), третья операция перемещает нулевую цифру на место первой, после чего все поля объединяются по ИЛИ.
У операции сдвига влево есть еще одна интерпретация. Если рассматривать машинное слово как целое без знака, то однократный сдвиг увеличивает его значение в 2 раза, двукратный - в 4 раза, n-кратный - в 2n. В таком виде, например, умножение числа на 10 можно представить так:
a10 ... a(8+2) ... 8a + 2a ... (a<<3) + (a<<1)
Операция СДВИГ ВПРАВО. Поразрядная операция «сдвиг вправо» имеет некоторые особенности выполнения. По аналогии со сдвигом влево операция сдвига вправо на n разрядов интерпретируется как целочисленное деление на 2n. При этом заполнение освобождающихся старших разрядов производится таким образом, чтобы сдвиг соответствовал операции деления с учетом формы представления целого. Для беззнакового целого заполнение должно производиться нулями (логический сдвиг), а для целого со знаком - сопровождаться дублированием значения старшего знакового разряда (арифметический сдвиг). В последнем случае отрицательное число при сдвиге останется отрицательным:
int n=0xFF00; n>>=4; // n=0xFFF0;
unsigned u=0xFF00; u>>=4; // u=0x0FF0;Формирование маски в заданном диапазоне разрядов. Функция возвращает машинное слово - маску, в котором разряды в заданном диапазоне установлены в 1 (динамическая маска). Для этого она прогоняет маску единичного разряда по всему диапазону и выполняет операцию установки разряда по маске (ИЛИ).
//----------------------------------------------------------------91-01.cpp
//--- Формирование маски в заданном диапазоне разрядов
long set_mask(int r0, int dn) {
long m,v; // m - " бегущий" единичный разряд, v - маска
m = 1 << r0; // Сдвинуть единичный разряд на r0 разрядов влево
for (v=0; dn!=0; dn--) { // Повторять dn раз
v |= m; // Установить очередной разряд из m в v
m <<=1;} // Переместить единичный бит в следу ющий разряд
return v;
}Определение разрядности целого числа. Простейший способ – сдвигать беззнаковое целое вправо, пока оно не станет равным 0. Количество сдвигов – и есть его разрядность.
//------------------------------------------------------91-02.cpp
//----- Определение разрядности числа
int wordlen(unsigned long vv) {
for (int i=0; vv!=0; i++, vv>>=1);
return i;
}Подсчет количества единичных разрядов. При сдвиге вправо все биты числа будут последовательно находиться в младшем разряде, из которого их нужно выделять с использованием операции И с единичной маской.
//------------------------------------------------------91-03.cpp
//------ Подсчет количества единичных разрядов
int what_is_1(unsigned long n) {
int i,s;
for (i=0,s=0; i < sizeof(long) * 8; i++) {
if (n & 1) s++; n >>=1; // Проверить младший разряд и сдвинуть слово
}
return s;
}Алгоритмы поразрядной сортировки
В смысле идей поразрядные сортировки не несут ничего нового, они базируются на известных алгоритмах, основанных на разделении (распределении). Только вот само разделение основано на использовании двоичного представления целых чисел.
Поразрядная сортировка разделением. В идее рекурсивного разделения центральным является понятие медианы – границы разделения на части «больше-меньше» (см.7.2). Если сортируется множество положительных (или беззнаковых) целых, то таким «водоразделом» может выступать очередной разряд машинного слова (разряды берутся в порядке убывания весов, т.е. от старшего к младшему). На первом шаге массив делится на две части по значению старшего разряда: в левую часть попадаю значения, содержащие в этом разряде 0 , в правую – содержащие 1. Затем алгоритм выполняется рекурсивно по отношению к полученным частям, но уже по следующему разряду и т.д. до самого младшего. Сама идея разделения полностью скопирована из 7.2: индексы i,j движутся с двух концов интервала к центру, оставляя после себя значения с разрядом, равным 0 слева, и равным 1 – справа. Когда оба движка «упираются» в элементы с противоположными значениями разрядов, они меняют их местами.
//----------------------------------------------------------91-04.cpp
//--------------- Поразрядная сортировка разделением
void bitsort(int A[],int a,int b, unsigned m) {
int i;
if (a >= b) return; // Интервал сжался в точку
if (m == 0) return; // Проверяемые разряды закончились
// Разделить массив на две части по значению разряда,
// установленного в маске m
int j,vv; // Цикл разделения массива
for (i=a, j=b; i<=j; ){
if ((A[i] & m) ==0) // Слева с разрядом =0
{ i++; continue; } // пропустить
if ((A[j] & m) !=0) // Справа с разрядом =1
{ j--; continue; } // пропустить
vv = A[i]; A[i]=A[j]; A[j]=vv;
i++, j--; // Обмен и сдвиг границ
}
bitsort(A,a,j,m >>1); // Рекурсивный вызов
bitsort(A,i,b,m >>1); } // для следующего разрядаДля самого первого вызова рекурсивной функции для всего исходного массива необходимо определить старший значащий разряд в его элементах. Для этого ищется максимальный элемент и для него определяется маска единичного разряда m, пробегающая последовательно все разряды справа налево до тех пор, пока она не превысит значение этого максимума.
void mainsort(int B[], int n){
int max,i; unsigned m;
for(max = 0, i=0; i< n; i++)
if (B[i] > max) max = B[i];
for (m=1; m < max; m <<= 1); // Единичная маска, превышающая максимум
m >>=1; // Старший разряд разделения
bitsort(B,0,n-1,m); }Замечание: отрицательные значения вносят свои коррективы в связи с особенностью их форм представления. Ведь поразрядная сортировка фактически работает в формате беззнакового представления. Дополнительный код (см.1.3) отображает отрицательные числа в область больших беззнаковых (положительных), переворачивая диапазон представления. В соответствии с этим отрицательные числа будут располагаться после положительных, причем отсортированными в обратном порядке. И, наконец, в качестве первого разряда разделения нужно брать старший (знаковый) разряд.
for (m=1,i=0; i<8*sizeof(int)-1; i++; m <<= 1); // Двигать до старшего (знакового) разрядаЛексикографическая поразрядная сортировка. Любое распределение при использовании внутреннего (двоичного) представления целых приводит к разделению данных по двум направлениями в соответствии со значением очередного разряда. Поэтому идея лексикографического распределения (по символам, по цифрам или другим составляющим) может быть применена к разрядам числа: они ведь тоже являются двоичными цифрами (см. 7.7). Соответствующий алгоритм можно переписать «один в один».
//------------------------------------------------------------------91-05.cpp
//----- Поразрядная лексикографическая сортировка
void sort(int in[], int n)
{int m,i,max,i0,i1;
int *v0=new int[n]; // Создать 2 «кармана»
int *v1=new int[n];
for (i=0, max=0; i<n; i++)
if (in[i] > max) max=in[i];
for (m=1; m<=max; m <<=1){ // для каждого разряда, начиная с младшего
for (i=i0=i1=0;i<n;i++) // распределить в 2 кармана по значению
if ((in[i] & m)==0)
v0[i0++]=in[i]; // очередного разряда (двоичной цифры)
else v1[i1++]=in[i];
for(i=0;i<i0;i++) // соединить карманы первый - второй
in[i]=v0[i];
for(i0=0;i<n;i++,i0++) // соединить карманы первый - второй
in[i]=v1[i0];
}
delete []v0; delete []v1;}Поразрядная распределяющая сортировка. Рецепт: возьмите идеи распределения по карманам, использования на каждом шаге очередного двоичного разряда, но от старшего к младшему и слияния последовательностей, то получите поразрядную распределяющую сортировку. Парадокс в том, что получаемые в карманах последовательности не являются упорядоченными, тем не менее, к ним применяется классическое слияние как для упорядоченных последовательностей. Интуитивное объяснение всего происходящего: при слиянии меньшие значения постепенно перемещаются вперед.
//---------------------------------------------------------------------91-06.cpp
//----- Поразрядная распределяющая сортировка
void sort(int in[], int n)
{int m,i,max,i0,i1;
int *v0=new int[n]; // Создать 2 "кармана"
int *v1=new int[n];
for (i=0, max=0; i<n; i++)
if (in[i] > max) max=in[i]; // Определение максимального
for (m=1; m <=max; m <<=1); // значащего разряда
for (m >>=1; m !=0; m >>=1){ // По всем разрядам от старшего
for (i0=i1=0; i0+i1 < n; ) // Распределение по значению
if ((in[i0+i1] & m) ==0) // очередного разряда
v0[i0] = in[i0+i1], i0++;
else // по карманам
v1[i1] = in[i0+i1], i1++;
v0[i0] = v1[i1] = max+1; // В каждый карман - "затычка"
for (i0=i1=0; i0+i1 < n; ) // Обычное слияние
if (v0[i0] < v1[i1]) // по сравнению значений
in[i0+i1] = v0[i0], i0++; // в последовательности
else
in[i0+i1] = v1[i1], i1++; // max+1 играет роль ограничителя
} delete []v0; delete []v1;}Упаковка данных полями переменной длины Наибольшую плотность упаковки можно достичь, если сделать границы слов (байтов) «прозрачными», представив упакованные данные в виде неограниченной последовательности разрядов, «плотно» уложенных в массиве машинных слов (байтов). Для того, чтобы вынести за скобки часть программы, работающую с отдельными двоичными разрядами и их группами (полями), и, учитывая тот факт, что разряды записываются и извлекаются только последовательно, разработаем две функции добавления и выделения очередного разряда по заданному номеру. Он будет передаваться ссылкой на переменную – счетчик, которая увеличивается при каждом вызове функции.
//------------------------------------------------------------------------91-07.cpp
//-------- Извлечение и запись разряда (бита)
long getbit(char c[], int &n) { // c[] - массив байтов, n - номер разряда
int nb = n/8; // номер байта
int ni = n%8; // номер разряда в байте
n++;
return (c[nb]>>ni) & 1; } //сдвинуть к младшему и выделить
void putbit(char c[], int &n, int v ){
int nb = n/8; // Сформировать маску разряда ni
int ni = n%8; // очистить старое по маске и установить
n++; // новый разряд, сдвинув его в позицию ni
c[nb] = c[nb] & ~(1<<ni) | ( (v&1) << ni);}Функция, извлекающая последовательность разрядов числа (младшими вперед), производит повторную сборку их в машинное слово заданной размерности с использованием операций сдвига и поразрядного ИЛИ. Функция упаковки слова выделяет последовательность битов, начиная с младшего, используя операцию сдвига, и вызывает функцию записи разряда.
//------------------------------------------------------------------------91-07.cpp
//------- Извлечение слова заданной размерности
unsigned long getword(char c[], int &n, int sz) {
unsigned long v = 0; // int sz - количество разрядов
for(int i = 0; i<sz; i++) v |= getbit(c, n)<<i;
return v; }
void putword(char c[], int &n, int sz, long v){
while(sz--!=0)
{ putbit(c, n, v&1); v>>=1;}}Последующие действия связаны уже с форматом представления данных – наличием управляющих полей и полей данных взаимосвязанной размерности. В них поразрядные операции могут вообще отсутствовать. Это видно на примере функций упаковки и распаковки целых переменных различной размерности – 8, 16 и 32 разряда. перед каждым числом размещаются 2 бита, определяющие размерность числа - 00 - конец последовательности, 01 - char, 10 - int, 11 – long. После них размещаются разряды самого числа.
//------------------------------------------------------------------------91-07.cpp
//---- Упаковка и распаковка переменных различной размерности
void unpack(char c[]){
int n=0; int vv;
while(1){
int mode=getword(c,n,2); // Извлечение 2-разрядного кода
switch(mode){ // переключение по значению кода
case 0: return; // 00 – конец последовательности
case 1: vv=getword(c,n,8); break; // 01 извлечь 8-разрядное (байт)
case 2: vv=getword(c,n,16);break; // 10 извлечь 16-разрядное
case 3: vv=getword(c,n,32);break; // 11 извлечь 32-разрядное
} printf("%d\n",vv);
}}
void pack(char c[]){
int n=0; int vv;
do { scanf("%d",&vv);
if(vv==0) putword(c,n,2,0); // запись 2-разрядного кода 00
else if (vv < 256) {
putword(c,n,2,1); // запись 2-разрядного кода 01
putword(c,n,8,vv);} // запись 8-разрядного кода числа
else if (vv < 32768) {
putword(c,n,2,2); // запись 2-разрядного кода 10
putword(c,n,16,vv);} // запись 16-разрядного кода числа
else {
putword(c,n,2,3); // запись 2-разрядного кода 11
putword(c,n,32,vv);} // запись 32-разрядного кода числа
} while (vv!=0); }Машинная арифметика произвольной точности
Для понимания ниже изложенного материала необходимо детально проработать п. «1.3. Описание данных. Типы данных и переменные» в той его части, которая касается двоичной и шестнадцатеричной систем счисления, машинных слов и основ внутреннего представления данных.
Поразрядные операции более примитивными, чем арифметические. Именно потому на их основе можно запрограммировать алгоритмы выполнения арифметических операций, использующих форматы внутреннего (двоичного) представления данных. Естественно, это имеет смысл не для воспроизведения уже имеющегося, а, например, для создания арифметики произвольной точности. В предлагаемом примере программно моделируются целые (со знаком) произвольной размерности, представленные массивами беззнаковых байтов в форме, соответствующей их внутреннему представлению в памяти (дополнительный код).
Операция сложения выполняется побайтно. Возникающий при сложении двух байтов перенос (8-й разряд, выделяемый маской 0x0100) используется в операции сложения следующих двух байтов.
//-------------------------------------------------------------91-08.cpp
//------Сложение целых произвольной разрядности
typedef unsigned char uchar;
void add(uchar out[], uchar in1[], uchar in2[], int n)
{int i, carry; // Разряд переноса
unsigned w; // Рабочая переменная для сложения двух байтов
for (i=0, carry=0; i<n; i++){
out [i] = w = in1[i]+in2[i]+carry;
carry = (w & 0x0100) >>8; // Разряд переноса сдвинуть вправо на 8
}}Для того, чтобы продемонстрировать работоспособность алгоритма и соответствие его принятым форматам представления данным, необходимо взять в качестве параметров функции любой базовый тип (например, long), сформировать на него указатель как на область памяти, заполненную беззнаковыми байтами.
void main(){
long a=125000, b=30000, c;
add((uchar*)&c, (uchar*)&a, (uchar*)&b,sizeof(long));
printf("c=%ld\n",c);}Для моделирования операции вычитания необходимо сформировать дополнительный код числа: произвести побайтную инверсию и добавить 1 к результату. Последнее можно сделать, установив первоначально в 1 перенос и распространив его по массиву байтов, аналогично сложению.
//------------------------------------------------------91-09.cpp
//------ Получение отрицательного числа в дополнительном коде
typedef unsigned char uchar;
void neg(uchar in[], int n)
{int i, carry; // Разряд переноса
unsigned w; // Рабочая переменная для сложения двух байтов
for (i=0; i<n; i++) in[i]=~in[i]; // Инвертированин всех разрядов
for (i=0, carry=1; i<n; i++){ // Добавление 1 (инкремент) с первоначальной
in [i] = w = in[i]+carry; // установкой переноса в 1
carry = (w & 0x0100) >>8;
}}Для моделирования операции умножения необходимо реализовать операции сдвига на 1 разряд влево и вправо.
//------------------------------------------------------91-10.cpp
//------Сдвиг целых произвольной разрядности
void lshift(uchar in[], int n)
{ int 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=((in[n-1]&0x80)!=0); // Разряд переноса = копия знакового
int i,z;
for (i=n-1; i>=0; i--){
z = in[i] & 1; // Выделить младший разряд (перенос)
in[i] >>= 1; // Сдвинуть вправо и установить
in[i] |= carry <<7; // старый перенос в старший разряд
carry = z; // Запомнить новый перенос
}}В переменной carry запоминается значение старшего (младшего) разряда, который переносится в следующий байт на место младшего (старшего). Сдвиг влево происходит от младшего байта к старшему, вправо – наоборот. Сдвиг вправо – арифметический, освобождающийся старший разряд старшего байта устанавливается как копия сдвигаемого (начальное значение переноса carry). Это обеспечивает сохранение знака отрицательного числа при сдвиге вправо (аналог деления на 2).
В операции умножения реализован самый простой алгоритм сложения и сдвига. Он, как и все алгоритмы машинной арифметики для внутреннего представления данных, использует свойства двоичной системы.
cc = aabb = aa Σ bbi 2i = Σ bbi (aa * 2i)
В произведении множитель bb раскладывается как сумма произведений двоичных разрядов на степени 2, т.е. bbi * 2i. Известно, что степень 2 эквивалентна сдвигу влево на n разрядов. Тогда при наличии 1 в n-ом разряде множителя bb к произведению должен быть добавлен множитель аа, сдвинутый на n разрядов влево. При наличии 0 добавление не производится.
//------------------------------------------------------91-11.cpp
//------Умножение целых произвольной разрядности
void mul(uchar out[], uchar aa[], uchar bb[], int n)
{int i,s1=0,s2=0; // Отрицательные числа - прямой код
if (aa[n-1] & 0x80) { neg(aa,n); s1=1; }
if (bb[n-1] & 0x80) { neg(bb,n); s2=1; }
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); // Множитель - вправо
}
if (s1!=s2) neg(out,n); // Знаки не совпадают - доп. код
}В множителе bb подряд просматриваются все разряды, начиная с младшего (путем одноразрядного сдвига его вправо). Множитель при этом каждый раз сдвигается на 1 разряд влево (умножается на 2). Если очередной разряд множителя равен 1, то текущее сдвинутое значение множимого добавляется к произведению. Чтобы не усложнять программу, значения множимого и множителя не сохраняются. Поскольку перемножаются положительные значения (абсолютные величины), то дополнительный код отрицательных множителей переводится в прямой, а результат при необходимости – обратно в дополнительный.
Арифметика в других формах представления данных
В арифметике произвольной точности совсем не обязательно придерживаться форматов внутреннего представления даже двоичной системы. Данные могут быть представлены десятичной системе счисления, при этом операции производятся над каждой цифрой числа отдельно с учетом взаимного влияния десятичных разрядов через переносы, заемы, то есть так, как «учат в школе». Возможны два варианта представления десятичных цифр:
отдельная цифра представлена 4 битами (тетрадой, шестнадцатеричной цифрой, так называемый BDC-код);
цифра задана символом во внешней форме представления, а само число - текстовой строкой.
Например, число 17665 выглядит в этих формах представления следующим образом:
long ss=0x00017655; // или
char s[]={0x55,0x76,0x10,0x00};
char s[]="17665";В качестве иллюстрации технологии работы с отдельными цифрами числа в десятичной системе счисления рассмотрим пример функции, добавляющей 1 к числу во внешней форме представления, то есть в виде текстовой строки. Добавление 1 состоит в поиске первой цифры, отличной от 9, к которой добавляется 1. Все встречающиеся «на пути» цифры 9 превращаются в 0. Если процесс «превращения девяток» доходит до конца строки, то производится расширение строки следующей цифрой 1.
//--------------------------------------------------------------------91-12.cpp
//------ Инкремент числа во внешней форме представления
void inc(char s[]){
for (int i=0; s[i]!=0; i++); // Поиск конца строки
for (int n=i-1; n>=0; n--){ // Младшая цифра - в конце
if (s[n]=='9' ) // 9 превращается в 0
s[n]='0';
else { s[n]++; return; }} // добавить 1 к цифре и выйти
for (s[i+1]=0; i>0; i--) s[i]='0' ; // Записать в строку 1000...
s[0]='1';}Другие арифметические операции также моделируются по принципу «цифра за цифрой». Так, при сложении суммируется очередная пара цифр, переведенных во внутреннее представление, и при получении результирующей суммы, превышающей 9, формируется перенос в следующий разряд. Вычитание производится, соответственно, с учетом заема.
//------------------------------------------------------------------91-13.cpp
//------ Сложение чисел во внешней форме представления
void add(char out[],char c1[],char c2[]){
int l1=strlen(c1)-1; // Определение разрядности суммы
int l2=strlen(c2)-1; // и индексов младших цифр слагаемых
int l=l1; if (l2>l1) l=l2;
l++; out[l+1]=0; // В сумме на 1 цифру больше
int v,v1,v2,carry; // Цифры и перенос
for (carry=0;l>=0;l--,l1--,l2--){ // Цикл от младших цифр к старшим
if (l1<0) v1=0; else v1=c1[l1]-'0';
if (l2<0) v2=0; else v2=c2[l2]-'0';
v=v1+v2+carry; // Сложение с учетом входного
if (v>=10) {carry=1; v-=10;} // и формированием выходного
else carry=0; // переноса (во внутренней форме)
out[l]=v+'0'; // Запись цифры результата
}}Лабораторный практикум
Программа деления целых чисел произвольной длины во внутреннем представлении с использованием операций вычитания, инкремента и проверки на знак результата. Частное определяется как количество вычитаний делителя из делимого до появления отрицательного результата (проверить на переменных типа long).
Программа деления целых чисел произвольной длины во внутреннем представлении с восстановлением остатка. Очередной разряд частного определяется вычитанием делителя из делимого. Если результат положителен, то разряд равен 1, если отрицателен, то делитель добавляется к делимому (восстановление остатка) и разряд частного считается равным 0. После каждого вычитания делимое и частное сдвигаются на 1 разряд влево. Перед началом операции делитель выравнивается с делимым путем сдвига на n/2 разрядов влево.
Умножение чисел произвольной длины, представленных непосредственно строками цифр. Первоначально формируется строка символов произведения с необходимым количеством нулей. Далее для каждой пары цифр сомножителей к нему добавляется частичное произведение: значения цифр переводятся во внутреннюю форму и перемножаются, после чего выделяется младшая и старшая цифры результата, которые суммируются с соответствующими цифрами произведения с учетом переноса и его распространения в старшие цифры.
Вариант 3 для двоично-десятичного представления исходных данных – в одном байте – 2 тетрады, хранящие десятичные цифры числа. Последовательность цифр размещена, начиная с младшей, и ограничена тетрадой с кодом 0xF.
Умножение чисел произвольной длины, представленных непосредственно строками цифр. Произведение формируется через многократное сложение одного из множителей с накапливаемым произведением, количество сложений определяется вторым сомножителем.
Вариант 5 для двоично-десятичного представления исходных данных – в одном байте – 2 тетрады, хранящие десятичные цифры числа. Последовательность цифр размещена, начиная с младшей, и ограничена тетрадой с кодом 0xF.
Вычитание чисел произвольной длины, представленных непосредственно строками цифр с использованием дополнительного кода вычитаемого (в десятичной системе счисления).
Вариант 7 для двоично-десятичного представления исходных данных – в одном байте – 2 тетрады, хранящие десятичные цифры числа. Последовательность цифр размещена, начиная с младшей, и ограничена тетрадой с кодом 0xF.
Кодирование и декодирование строки символов, содержащих цифры, в последовательность битов. Десятичная цифра кодируется 4 битами - одной шестнадцатеричной цифрой. Цифра F обозначает, что за ней следует байт (2 цифры) с кодом символа, отличного от цифры. Разработать функции кодирования и декодирования с определением процента уплотнения.
Последовательность целых переменных различной размерности кодируется следующим образом: перед каждым числом размещаются 5 битов, определяющие количество битов в следующем за ним целом числе. 00000 - конец последовательности. Разработать функции упаковки и распаковки массива переменных типа long с учетом количества значащих битов и с определением коэффициента уплотнения. Пример: 01000 xxxxxxxx 00011 xxx 10000 xxxxxxxxxxxxxxxx 00000
Кодирование массива, содержащего последовательности одинаковых битов. При обнаружении изменения значения очередного бита по сравнению с предыдущим в последовательность записывается 6 разрядное значение счетчика (n<6) длины последовательности одинаковых битов. n=0 обозначает конец последовательности. Пример (исходная последовательность битов задана справа налево): 000000001111111000000000000 - 001100 000111 001000 000000
Большие латинские буквы упаковываются в виде 5-битных кодов по 3 символа в одну целую переменную типа int. При этом старший бит устанавливается в 1. Остальные символы упаковываются по одному в целую переменную со значением старшего бита - 0. Разработать функции упаковки и распаковки строки с определением коэффициента уплотнения.
Первые 15 наиболее часто встречающихся символов кодируются 4-битными кодами от 0000 до 1110. Код 1111 обозначает, что следующие за ним 8 бит кодируют один из остальных символов. Разработать функции упаковки и распаковки строки с определением наиболее часто встречающихся символов и коэффициента уплотнения.
Если в последовательности встречается бит 0, то за ним идет 3-битовый код первых 8 наиболее часто встречающихся символов (000 ... 111). За битом 1 - следует обычный 8-битный код остальных символов. Разработать функции упаковки и распаковки строки с определением наиболее часто встречающихся символов и коэффициента уплотнения.
Первый наиболее часто встречающийся символ кодируется битом 0. Бит 1 кодирует группу из всех остальных символов. Код 10 кодирует второй по частоте символ, 11 - группу всех остальных и т.д.. Разработать функции упаковки и распаковки строки с определением наиболее часто встречающихся символов и коэффициента уплотнения.
Вопросы без ответов Содержательно сформулируйте результат функции, определите, какие свойства машинного слова и какие действия над ним она производит. Вызов функции оформите с формальным параметром – шестнадцатеричной константой и прокомментируйте полученный результат.
Пример оформления задания.
//------------------------------------------------------91-14.cpp
unsigned long F(unsigned long v, int k){
int i; unsigned long s;
for (s=1, i=0; i<k; s<<=1, i++) v = v & ~s;
return v;}
void main(){ printf("F(0x1FFF,7)=%lx\n",F(0x1FFF,7)); }В данном примере необходимо представить процессы перемещения битов по машинному слову. Единственный цикл в программе организует перемещение единичного бита последовательно по разрядам машинного слова s справа налево. Число повторений цикла k ограничивает этот процесс k разрядами. Таким образом, в s находится единичная маска, которая пробегает по первым k разрядам машинного слова. В теле цикла имеет место поразрядная операция И с инвертированной маской, что, как мы знаем, интерпретируется как очистка соответствующего бита. Результат функции – очистка k младших разрядов входной переменной. Для приведенного примера вызова можно легко определить результат, естественно, в шестнадцатеричной системе счисления (с раскладкой по битам) - 0x1D20 . Очищаются первые 5 разрядов – младшая тетрада и еще младший бит второй тетрады.
//--------------------------------------------------------------91-15.cpp
//------------------------------------------------ 1
int F1(){
int i; long l;
for (l=1,i=0; l >0; l<<=1, i++);
return i;}
//------------------------------------------------ 2
int F2(){
int i; long l;
for (l=1,i=0; l !=0; l<<=1, i++);
return i;}
//------------------------------------------------ 3
int F3(long n)
{ int i,s;
for (i=0,s=0; i < sizeof(long) * 8; i++, n >>=1)
if (n & 0x7==5) { s++; i+=2; }
return s; }
//------------------------------------------------ 4
long F4(long n)
{ int i; long s;
for (i=s=0; i < sizeof(long) * 8; i++)
{ s <<=1; s |= n & 1; n >>=1; }
return s; }
//------------------------------------------------ 5
long F5(long n, int m1, int m2)
{ long s,x; int i;
for (i=0,x=1,s=n; i < sizeof(long)*8; i++)
{ if (i >=m1 && i <=m2) s |= x; x <<=1; }
return s; }
//------------------------------------------------ 6
int F6(char c[])
{ int i,s;
for (i=0; c[i] !='\0'; i++)
if (c[i] >='0' && c[i] <='7') break;
for (s=0; c[i] >='0' && c[i] <='7'; i++)
{ s <<=3; s |= c[i] & 0x7; }
return s; }
//------------------------------------------------ 7
void F7(char c[],long n)
{ int i=sizeof(long)*8/3 +1;
for (c[i--]='\0'; i>=0; i--)
{ c[i] = (n & 0x7) + '0'; n >>=3; }}
//------------------------------------------------ 8
// Операция "^" - ИСКЛЮЧАЮЩЕЕ ИЛИ
int F8(long n)
{ int i,m,k;
for (i=m=k=0; i < sizeof(long) * 8; i++, n >>= 1)
if ((n & 1) ^ m)
{ k++; m =!m; }
return k; }
//------------------------------------------------ 9
int F9(long n)
{ int i,m,k;
for (i=m=k=0; i < sizeof(long) * 8; i++, n >>= 1)
if (n & 1) k++;
else { if (k > m) m=k; k=0; }
return m; }
//------------------------------------------------ 10
int F10(long v){
for (int i=0; v!=0; i++, v>>=1);
return v;}