В реальных задачах возникает необходимость работать с числами из определённого диапазона. Например, из условия задачи известно, что числа находятся на промежутке от нуля до трёх. Тогда для их представления в памяти достаточно двух бит, так как 310=112. Для экономии памяти возникает необходимость в одну ячейку поместить несколько чисел. Например, в двухбайтную переменную 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, так как С00016 = 11000000000000002.
Для выделения второй цифры (0) из числа 11000000000000002 получаем 00110000000000002= 300016 , используя сдвиг на два разряда и выполняем операции (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). Время выполнения таких программ увеличивается.
