Упаковка и распаковка информации

В реальных задачах возникает необходимость работать с числами из определённого диапазона. Например, из условия задачи известно, что числа находятся на промежутке от нуля до трёх. Тогда для их представления в памяти достаточно двух бит, так как 3₁₀=11₂. Для экономии памяти возникает необходимость в одну ячейку поместить несколько чисел.

Пример 11 (упаковка, или сжатие информации). В двухбайтную переменную unsigned short r (16 бит) запишем 16/2=8 чисел из диапазона 0..3.

Существует несколько алгоритмов решения подобной задачи. Предлагается заполнять ячейку r справа налево. Первое число помещаем в последние два бита, сдвигаем его влево на два разряда. На освободившиеся после сдвига два бита засылаем второе число, снова сдвигаем влево на два разряда, записываем третье число, сдвигаем и так далее.

unsigned short P (unsigned short mymax,unsigned short shift, unsigned short n)

{ randomize(); unsigned short num, r=0;

for (int j=1; j<=n; j++)

{ r<<=shift; // или r=r<<shift;

num=random(mymax+1); cout<<num<<" ";

r |= num; // или r+= num;

} return r;

}

void main()

{ unsigned short R= P(3, 2, 8); printf(" \n % x % d",R, R);

getch();

}

Так как после сдвига влево ячейки r два последних бита будут нулевыми, а в переменной num ненулевые только два последних бита, то r |= num и r += num выполняются одинаково. Заметим, что в общем случае эти две операции различаются.

В функции printf формат %x используется для вывода целого числа в шестнадцатеричной системе счисления с малыми латинскими буквами a — f.

В таких задачах важно уметь проанализировать результат. Пусть случайным образом сформированы следующие восемь чисел в таком порядке: 3, 0, 2, 1, 3, 0, 1, 1. Тогда будет выведено c9c5 — шестнадцатеричное представление числа по формату %x. Почему? Каждое число от 0 до 3 в ячейке r занимает два бита. В двоичном виде имеем 1100100111000101. Разбив на тетрады и учитывая, что это положительное число (unsigned), получим c9c5. Затем будет выведено 51653 — это же число в десятичной системе счисления по формату %d.

Пример 12 (распаковка). Как из такого числа r (см функцию в примере 11), в котором хранятся восемь чисел из диапазона 0..3, “взять” каждое из них и, например, вывести?

Алгоритм 1. Выполнить распаковку можно так, как выводили целое число в двоичной системе счисления (пример 10). Будем получать числа справа налево. При этом операция & выполняется с числом 3 (11 в двоичной системе счисления), а сдвигать надо вправо на 2, 4, 6, … разрядов.

Алгоритм 2. Числа будем получать слева направо в том же порядке, как они формировались. Для выделения первой левой цифры (в нашем примере 3)используем операции (r & 0xC000)>>14, так как

С000₁₆ = 1100000000000000₂. Для выделения второй цифры (0) из числа 1100000000000000₂ получаем 0011000000000000₂= 3000₁₆, используя сдвиг на два разряда и выполняем операции (r & 0x3000)>>12.

На каждом последующем шаге, переменную, с которой выполняется операция &, сдвигаем вправо на два разряда (обозначим Maska), а результат этой операции сдвигаем вправо на 10, 8, … разрядов (переменная k).

void UnPark (unsigned short r,

unsigned short shift, unsigned short n)

{ unsigned Maska=0xC000, k=14;

for (int j=1; j<=n; j++,k –=2, Maska>>=shift)

{ short num= (r & Maska)>>k;

cout<<num<<" "; }

}

void main()

{ unsigned short R= P(3, 2, 8); /* Функцию P см. в примере 11 */

printf(" \n % x % d\n",R, R); UnPark(R,2,8);

getch();

}

В результате будут получены и выведены те же числа, которые были сформированы функцией P случайным образом, т. е. 3, 0, 2, 1, 3, 0, 1, 1.

Упаковку эффективно использовать, если в памяти необходимо хранить массив целых чисел из указанного диапазона большой размерности. Например, если надо сохранить 400 чисел из диапазона 0..3, то вместо массива unsigned short a[400] достаточно объявить массив unsigned short a[50 ]. Этим самым память экономим в 8 раз. Эффективность этой методики с точки зрения экономии памяти тем выше, чем меньше диапазон чисел. Но время выполнения таких программ увеличивается.