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

В реальных задачах возникает необходимость работать с числами из определённого диапазона. Например, из условия задачи известно, что числа находятся на промежутке от нуля до трёх. Тогда для их представления в памяти достаточно двух бит, так как 3₁₀=11₂. Для экономии памяти возникает необходимость в одну ячейку поместить несколько чисел. Например, в двухбайтную переменную r, объявленную как unsigned short r и занимающую 16 бит, можно записать 16/2=8 чисел из диапазона 0..3. Такие задачи называют упаковкой,или сжатием,информации.

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

randomize();

unsigned short num, r=0;

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

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

num=random(4);

cout<<num<<" ";

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

}

printf(" \ n % x % d",r, r);

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

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

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

Как из такого числа r, в котором хранятся восемь чисел из диапазона 0..3, “взять” каждое из них и, например, вывести? Это называют распаковкой.

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

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

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

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

cout<<endl;

unsigned Maska=0xC000, shift=14;

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

{ num= (r & Maska)>>shift;

cout<<num<<" ";

}

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

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