8 Операції над бітами

Метод доповнення до двох. Представлення числа в пам’яті залежить від технічної реалізації. Деякі комп’ютери для знака призначають один старший (крайній лівий) розряд комірки пам’яті, який називається знаковим. Якщо число додатнє, то в цьому розряді знаходитиметься число нуль, інакше – одиниця. Тоді решта розрядів використовуються для запису модуля числа. Нехай, наприклад, маємо комірку пам’яті типу signed char (8 біт), тоді в неї можна буде записати цілі числа від -127 до +127 (у двійковій системі числення – від 1111 1111 до 0111 1111). Така форма представлення числа називається знакорозмірною.

Одним із недоліків цього способу є те, що число нуль може бути як додатнім, так і від’ємним, тобто +0 або -0, бо в двійковому представленні вони матимуть вигляд відповідно 0000 0000 або 1000 0000. Це може спричинити плутанину, кожного разу приходиться враховувати, що збережене в пам’яті число 0 насправді може й не бути нулем, оскільки в старшому розряді може містити одиницю.

З метою позбавитися від цього недоліка найчастіше застосовується прийом, який називається методом доповнення до двох. Його суть полягає в тому, що додатнє число зберігається в звичайному двійковому вигляді, а від’ємне – зміненим. Покажемо це на прикладі однобайтової комірки, відомо, що в неї можна записати додатнє беззнакове число (типу unsigned char) з діапазону від 0 до 255 (двійкові від 0000 0000 до 1111 1111). Якщо число знакове, тобто може бути як додатнім, так від’ємним (signed char), то діапазон його значень становитиме від -128 до 127, причому в найстаршому розряді від’ємного числа матимемо ту ж таки одиницю, а додатнього – нуль.

Під час запису в пам’ять таких обчислювальних машин додатнє число записується у звичному для нього вигляді, а від’ємне –автоматично інвертується і додається до нього одиниця. Нехай, наприклад, маємо число 4, тоді в комірці пам’яті типу signed char воно виглядатиме як 0000 0100. Ознакою того, що число додатнє, є нуль у його старшому (крайньому лівому) розряді. Якщо число дорівнює -4, то інвертоване воно виглядатиме, як 1111 1011, а після додавання одиниці – 1111 1100. При зчитуванні стає відомо, що воно від’ємне, бо має одиницю в старшому розряді, тоді для визначення модуля його віднімають від 9-розрядного (для типу char) числа 256. Нижче це показано на прикладі числа -4.

Число 4: 0000 0100

інвертоване число 4: 1111 1011

число -4: 1111 1100

число 256: 1 0000 0000

результат віднімання (модуль числа -4): 0000 0100

Якщо число дорівнює 0, то воно не може бути від’ємним, бо в пам’яті матиме вигляд: 0000 0000 – у старшому розряді має нуль. А двійкове від’ємне (старший розряд дорівнює одиниці) число 1000 0000 – не нуль, воно дорівнює -128, покажемо це:

Число 256: 1 0000 0000

число -128: 1000 0000

результат віднімання (модуль числа 128): 1000 0000

Старший розряд (наприклад, одиниця числа -128) двійкового числа виконує подвійну функцію. Він служить, по-перше, як індикатор від’ємного числа, а, по-друге, для формування його модуля.

Маска. В техніці зустрічаються задачі, в яких для ідентифікації об’єкта достатньо лише одного або декількох біт. Це, наприклад, електрична напруга на світловому табло, яка може бути ввімкненою або вимкненою (1 біт – 0 або 1), стани бурової установки (по одному біту на кожний стан), п’ять швидкостей обертання бурового інструмента (3 біти – 5 комбінацій цифр 0 і 1) та інші. Системи автоматизованого управління технологічними об’єктами, комп’ютерні мережі, системи передачі та обробки сигналів, як правило, теж вимагають компактного представлення даних. У цих та інших подібних випадках для запам’ятовування інформації достатньо лише декількох біт, що дозволяє економити пам’ять. Спрощується й процес передачі даних за рахунок того, що в одній комірці пам’яті можна помістити декілька чисел, тобто за один сеанс можна передати декілька різних даних.

Як на стороні формування цієї комірки, так розгортання на стороні прийому, застосовується маска. Це поняття подібне до шаблону, який використовують для скриття однієї частини об’єкта або показу іншої. В програмах мовою С її можна застосувати для представлення заданих розрядів числа до обробки порозрядними операціями над бітами, показаними в розділі 2.6.

Нехай, наприклад, маємо однобайтову комірку пам’яті, з яких потрібна нам інформація зберігається в другому розряді (зправа). Решта 7 розрядів комірки можуть використоватися для інших цілей. Тоді маска повинна бути не менше, ніж 2-розрядною. Візьмемо для неї теж однобайтову комірку пам’яті, куди запишемо вісімкове число 02 (двійкове 0000 0010), оскільки за її допомогою оброблятимемо 2-й розряд. Зауважимо, що немає особливої необхідності представляти число 2 у вісімковій системі числення, однак, під час обробки двійкових чисел програмісти часто користуються їх вісімковим еквівалентом. Нагадаємо, що двійкові числа вигідно групувати вісімковими тріадами, тому з метою підкреслення цього факта вдається підвищити “читабельність” програми.

Покажемо застосування запропонованої вище маски на декількох прикладах. У першому ввімкнемо другий двійковий розряд (присвоїмо значення 1, якщо він дорівнює 0, і залишимо 1 у протилежному випадку). Для випробування візьмемо два числа: 17 і 18, назвемо їх відповідно i1 i i2. Після запису в однобайтову комірку типу unsigned char вони матимуть вигляд відповідно: 0001 0001 і 0001 0010. Ці два числа спеціально підібрані так, щоб показати, що, по-перше, у 2-му розряді вони мають різні значення (перше – нуль, а друге – одиницю), а по-друге, що одиниці в інших розрядах (у нашому випадку 5-й і 1-й) ні не впливають на результати, ні не змінюються під час маніпуляції бітами. Це робить програма mask.

#include<stdio.h> /* mask */

int main(void)

{unsigned char mask=02, i1=17, i2=18;

i1 |= mask; i2 |= mask;

printf("i1=%d i2=%d\n", i1, i2);

getch();

return(0);

}

У цій програмі оголошено 3 такі змінні цілого беззнакового типу (unsigned char) довжиною 8 біт:

1. mask – маска, mask = 02 (двійкове 0000 0010);

2. i1 – для імітації вимкненого 2-го розряду (i1 = 17 = 0001 0001);

3. i2 – для імітації ввімкненого 2-го розряду (i2 = 18 = 0001 0010).

Результати виконання програми mask будуть такими:

i1=19 i2=18

При виконанні задачі заданий розряд (в нашому прикладі другий) результату повинен дорівнювати одиниці в будь-якому випадку за рахунок застосування операції порозрядного включного “АБО”, тобто відбувається ввімкнення другого розряду чисел i1 або i2, якщо він був вимкнений. Покажемо це на такій схемі:

маска mask: 0000 0010 0000 0010

число: 0001 0001 0001 0010

результат операції |: 0001 0011 0001 0010

Аналізуючи результати, бачимо, що в обох числах: i1 та i2 другий розряд став дорівнювати одиниці, а решта залишилися незмінними.

В другому прикладі обнулимо другий розряд числа, якщо він дорівнює одиниці, і залишимо його без змін у протилежному випадку, не змінюючи інші розряди цих чисел. Для цього внесемо в програму mask такі оператори:

i1 &= ~mask; i2 &= ~mask;

Тут використано дві операції: інвертування (зворотній код) маски і її порозрядне “I” з цими числами. Одержимо такі результати:

i1=17 i2=16

Нижче подана схема такої маніпуляції розрядами.

маска mask: 0000 0010 0000 0010

результат інвертування маски: 1111 1101 1111 1101

число: 0001 0001 0001 0010

результат операції &: 0001 0001 0001 0000

Виконання третього прикладу спричинить перемикання 2-го розряду числа з одиниці на нуль та навпаки за допомогою таких операторів програми mask:

i1 ^= mask; i2 ^= mask;

Тут використовується операція порозрядного виключного “АБО”. В результаті її виконання одержимо такі значення:

i1=19 i2=16

Хід виконання операторів показано нижче на схемі.

маска mask: 0000 0010 0000 0010

число: 0001 0001 0001 0010

результат операції ^: 0001 0011 0001 0000

Аналізуючи цю схему, бачимо, що число i1 не мало одиниці в другому розряді (дорінювало 17), а виконання операції ^ дало результат 19, тобто другий розряд змінився на протилежний. З другим числом i2 сталося те саме – результат став дорівнювати 16.

В останньому прикладі перевіримо на наявність одиниці в 2-му розряді чисел i1 та i2 за допомогою операції порозрядного “І” маски з цими числами. Її результат дорівнює mask лише тоді, коли якесь із них матиме одиницю в тих же розрядах, що число mask, таку одиницю має число i2. Для цього програма mask матиме такий оператор:

printf("rez1=%d rez2=%d\n", (mask & i1)==mask, (mask & i2)==mask);

Тут вираз зі знаком & взятий у круглі дужки, бо приорітет виконання порозрядних операцій нижчий, ніж знака ==. Одержимо результат:

rez1=0 rez2=1

Нижче подана схема обчислень, яка його пояснює.

маска mask: 0000 0010 0000 0010

числа: 0001 0001 0001 0010

результати операції &: 0000 0000 0000 0010

результати операції ==: 0 (ні) 1 (так)

Цей прийом можна застосувати й для інших цілей. Покажемо приклад випробування змінної i1 на наявність розрядів зі значенням 1 та видача їх порядкових номерів. Застосуємо так звану циклічну або змінну маску за допомогою таких операторів програми mask:

int num;

for(num=1, mask=1; num<=8; num++, mask<<=1)

if((mask & i1)==mask)printf("num=%d ", num);

Під час виконання циклу кожний розряд маски дістає почергово одиницю, починаючи з першого, шляхом циклічного зсуву її вмісту вліво на один розряд. Далі відбувається її порозрядне порівняння з числом i1 (mask & i1), результатом якого буде значення mask лише в тому випадку, коли є співпадання одиниць у відповідних розрядах обох чисел. Цим способом можна знайти порядкові номери всіх одиниць заданого числа. У нашому прикладі вони такі:

num=1 num=5

Нижче показано хід виконання операцій порівняння при цих значеннях змінної num.

число i1: 0001 0001 0001 0001

маска mask (num =1 або 5): 0000 0001 0001 0000

результат операції & (num =1 або 5): 0000 0001 0001 0000

результ. операції == (num =1 або 5): 1 1

значення num: 1 5

Оскільки число і1 мало одиниці в 1-му і 5-му розрядах, значення змінної num було виведено два рази: зі значеннями 1 і 5.

Аналізуючи результати всіх цих прикладів, бачимо, що вони не залежать від наявності одиниць у інших, ніж у маски, розрядах чисел i1 або i2, а маніпуляція бітами цих чисел не впливає на інші розряди.

Зазначимо також, що маска може мати будь-яку кількість розрядів, що мають одиниці. Тоді вона дозволить обробляти одночасно декілька розрядів числа.

Бітові поля структур. Подібні маніпуляції можна виконувати з бітовими полями структур. Нижче подана програма mask_stru, в якій розв’язуються три задачі попереднього прикладу (програми mask): ввімкнення, вимкнення і перемикання другого розряду числа. В ній для запам’ятовування маски використовується бітове поле mask структури s довжиною 2 біти, йому присвоєно значення 02 (двійкове число 10). Аналізуючи результати виконання, показані нижче за текстом програми mask_stru, бачимо, що вони збігаються з виданими програмою mask.

Крім власне застосування маски, ця програма ще демонструє зберігання двох чисел в одній комірці пам’яті, для двох чисел 17 і 18 (позначених у попередньому прикладі ідентифікаторами i1 та i2) використана одна змінна i типу int. Програма призначена для виконання в середовищі системи з типом int двобайтової довжини. На її початку значення змінної i=18, потім воно посувається вліво на 8 розрядів (i<<=8;) – робиться місце для другого значення: 17. В результаті виконання операції присвоєння: i+=17; змінна i містить обидва ці числа. За результатами її виводу в такому зміненому вигляді i<<=8+17= 1211. Зауважимо, що це число виведене в 16-й системі числення за допомогою специфікатора x. Якщо представимо кожний розряд цього числа двійковими тетрадами, то одержимо таке двійкове число:

0001 0010 0001 0001

Можна помітити, що його лівий байт містить число 18, а правий – 17 у двійковій системі числення.

Для зчитування числа 18 зі змінної і достатньо її зсунути на 8 розрядів управо, тоді число 17 пропадає, а 18 залишається. Для виділення числа 17 у програмі використовується допоміжна змінна c, вона приймає це значення шляхом присвоєння c=i. Оскільки змінна c має довжину 1 байт, то вона приймає лише останні 8 розрядів числа i, тому дорівнює 17.

#include<stdio.h> /* mask_stru */

int main(void)

{unsigned int i=18;

unsigned char c;

struct

{unsigned mask: 2;}s;

s.mask=02;

printf("\n");

i<<=8; i+=17;

c=i;

printf("i<<=8+17= %x i1=%d i2=%d\n", i, c, i>>8);

printf(" Ввiмкнення 2-го розряду: %d %d\n", c | s.mask, i>>8 | s.mask);

printf(" Вимкнення 2-го розряду: %d %d\n", c & ~s.mask, i>>8 & ~s.mask);

printf("Перемикання 2-го розряду: %d %d\n", c ^ s.mask, i>>8 ^ s.mask);

getch();

return(0);

}

i<<=8+17= 1211 i1=17 i2=18

Ввiмкнення 2-го розряду: 19 18

Вимкнення 2-го розряду: 17 16

Перемикання 2-го розряду: 19 16

Зауважимо, що бітові операції та зсув (у функції printf) не змінюють саме число i, бо не відбувається присвоєння результату цій змінній.

Зрозуміло, що виграш об’єму пам’яті, одержаний за рахунок зберігання декількох чисел в одній комірці, може бути знівельований програшем часу на додаткові операції (зсуву, переприсвоєння). Тут ставилася задача тільки продемонструвати певні прийоми, доцільність застосування яких вирішується в кожній конкретній програмі окремо.

Для компілятора з 4-байтовим та більшим типом int ця програма матиме подібний вигляд. Однак, якщо будемо зберігати декілька однобайтових чисел у такій комірці пам’яті, то операцію зсуву прийдеться виконувати не на 1, а на більше байт.

Візуальне представлення двійкового коду числа. Вище вже говорилося про те, що всі числа зберігаються в пам’яті переведеними в двійкову систему числення. Оскільки програмісту мовою С часто приходиться мати справу з двійковими кодами, виникає потреба в їх візуальному перегляді. Треба зразу сказати, що мова С не має для того спеціальних засобів, а ті, які має, дозволяють вивести число лише в вісімковій, десятковій або шістнадцятковій системах числення. У зв’язку з цим може виникнути питання про те, чи не можна для перегляду внутрішнього вигляду числа скористатися кратністю вісімкового та шістнадцяткового числа двійковому. Тоді, наприклад, представлене у вісімковій системі числення число достатньо було б розкласти на двійкові тріади або 16-ве – на тетради і прочитати. Тут немає однозначної відповіді, справа в тому, що, як уже було сказано, машинне, тобто внутрішнє, представлення числа залежить від технічної реалізаціїі. Компілятори розпізнають цю реалізацію, тому перед виводом число відповідно обробляється і на екрані завжди виглядає однаково – так, як задано специфікаторами виводу.

Отже, можна сказати, що в пам’яті зберігається не число, а його внутрішній код. Цей код одного і того ж числа, але в пам’яті різних комп’ютерів може мати різний вигляд. Наприклад, вище було сказано про знакорозмірну форму числа та метод доповнення до двох. До них можна ще додати метод доповнення до одиниці, по-різному можуть бути розміщеними байти числа декількабайтової довжини – в прямому або зворотньому порядку та інші. Все це говорить про те, що програміст повинен обережно ставитися до роботи безпосередньо з бітами, а задача візуального контролю бітів набуває особливої ваги. Нижче наведений приклад програми visual_bit для читання бітів цілого числа. Вона виконувалася в середовищі системи з 2-байтовим типом int.

#include<stdio.h> /* visual_bit */

void bit_s(int,char *);

int main(void)

{int n, i;

char b[8*sizeof(int)+1];

while(puts("\n‚Введіть ціле число ") && scanf("%d",&n)==1)

{bit_s(n, b);

printf("Десяткове число %d в бітах= ",n);

i=0;

while(b[i]){putch(b[i]); if(!(++i % 4))putch(' ');}

printf("\n");

return(0);

}

}

void bit_s(int k, char *s)

{

int i, kil=8*sizeof(int);

for(i=kil-1; i>=0; i--, k>>=1)s[i]=(01 & k)+48;

s[kil]='\0';

}

Результати виконання програми visual_bit:

Введіть ціле число

32767

Десяткове число 32767 в бітах = 0111 1111 1111 1111

Введіть ціле число

32768

Десяткове число -32768 в бітах = 1000 0000 0000 0000

Введіть ціле число

65535

Десяткове число -1 в бітах = 1111 1111 1111 1111

Введіть ціле число

-1

Десяткове число -1 в бітах= 1111 1111 1111 1111

Введіть ціле число

65536

Десяткове число 0 в бітах = 0000 0000 0000 0000

Введіть ціле число

65537

Десяткове число 1 в бітах = 0000 0000 0000 0001

Введіть ціле число

17

Десяткове число 17 в бітах= 0000 0000 0001 0001

Введіть ціле число

255

Десяткове число 255 в бітах= 0000 0000 1111 1111

Введіть ціле число

u

Ця програма складається з двох функцій: головної main() і підпорядкованої void bit_s(int, char *). Головна програма має дві змінні типу int: i – лічильник, параметр циклу та n – число, яке й має бути показаним у бітах. Оголошено в ній також літерний масив b, довжина якого в байтах дорівнює 8*sizeof(int)+1 – за кількістю розрядів числа n плюс 1 для літери '\0' наприкінці масиву.

Її програмний блок складається з двох вкладених циклів – обидва типу while, з яких зовнішній призначений для вводу числа n, він буде виконуватися до тих пір (зациклений), поки успішно завершуватиметься функція вводу scanf(). Ця функція видає кількість чисел, введених за один раз. У нашому випадку вона вводить одне число n, тому й видаватиме одиницю. Як тільки замість цілого числа буде запропоновано щось інше, наприклад, буква, функція видасть 0 і виконання циклу припиниться. Це зроблено для забезпечення вводу декількох чисел підряд. У цьому циклі відбувається також звернення до підпрограми для одержання масиву букв 0 або 1 (не слід тут плутати поняття буква і біт) та виконання внутрішнього циклу, який виводить ці букви – по одній на кожний біт числа n.

Внутрішній цикл забезпечує видачу на екран по одному символу за допомогою функції putch(). Він виконується доти, поки не натрапить у масиві b на символ '\0'. Для наочності кожні 4 символи цього масиву розділюються пробілами.

Підпорядкована функція служить для представлення кожного одного біта заданого цілого числа k типу int (перший вхідний параметр функції) 1-байтовою літерою 0 або 1, утворення масиву s літер типу char і повернення цього масиву в головну функцію. Звернемо увагу на те, що ця функція ніби й не повертає ніякого значення, бо має тип void, але насправді повертає символьний рядок, який є її другим вхідним параметром (адреса типу char).

Тіло цієї функції містить цикл типу for, його параметр i змінюється від kil-1 до 0 з кроком -1. Паралельно в циклі число k (в головній програмі – n) зсувається вправо на 1 біт (операція k>>=1), тоді кожний крайній правий біт порівнюється (операція &) з маскою-константою 01. В результаті одержуємо число 1 або 0, яке перетворюється в символ шляхом додавання числа 48. Нагадаємо, що ASCII-код числа 0 дорівнює 48, а решта збільшені на одиницю.

За результатами виконання програми vizual_bit можна зробити такі висновки:

1. число n приймає значення з діапазону -32768 ÷ +32767;

2. для зберігання числа n застосовується метод доповнення до двох;

3. для чисел типу int не існує такого поняття, як переповнення пам’яті.

Порівнюючи приклад mask попереднього розділу з програмою vizual_bit, знаходимо їхню різницю в тому, що в першій для читання бітів відбувався зсув маски, а в другій – навпаки, зсувається число k, яке випробовується маскою. Для результатів це не має значення, були б вони лише вірними і ми їх одержали. Але зсування маски – поганий тон програмування, маска – це щось недоторкане і краще її не змінювати.

Таким чином, маска може мати різний вигляд: вісімкової константи, наприклад, у виразі s[i]=(01&k) програми visual_bit, бітового поля структури s.mask у програмі mask_stru або числа mask цілого типу програми mask.

Запитання для самоперевірки

1. Поясніть поняття маски.

2. Перечисліть види масок за кількістю розрядів, за типом числа.

3. Поясніть хід виконання вищеописаних порозрядних операцій.

4. Поясніть виконання операцій зсуву розрядів уліво та вправо.

5. Приведіть альтернативні способи (без маски) розв’язування задач програми mask.

6. Чи можна в одній комірці пам’яті зберігати декілька різних чисел типу int або float?

7. Як можна за допомогою однієї маски одночасно перевіряти не один, а декілька розрядів числа?

8. Чи можна в одній комірці пам’яті мати декілька різних масок?

9. Як виконуються вищеописані порозрядні операції над двома числами різної довжини?

10. Чи можна над бітовими полями структури виконувати арифметичні та логічні операції подібно до змінних типу int або float?

11. Чи можна відновити значення розрядів числа, які були втрачені в результаті його зсуву?

12. Як зв’язані між собою № розряду, з яким працює маска, і кількість її розрядів?

13. Чим регламентована довжина маски?

14. Чи може мати маска більше розрядів, ніж № розряду, з яким вона працює?

15. Для чого в програмі mask_stru використовується допоміжна змінна unsigned char c, чи можна без неї обійтися?