Логічні операції

Згадаємо дитинство, дитячий садок. Мабуть майже кожен з вас у тому віці чув самий короткий анекдот: – Колобок повісився. Чому ця пара слів викликала у всіх нас веселий настрій, адже йшлося про те, що когось позбавили життя. Тому і тільки тому, що ці два слова описують подію, яка в реальному житті не можлива.

Твердження, подібні до вище згаданого, є логічними виразами, які можуть бути або істинними або хибними. Саме ці дві поняття і лежать в основі алгебри логіки, або, як її ще іноді називають: булівської алгебри. Оскільки розглядувана мова програмування є мовою високою рівня, то основні логічні операції в ній реалізовані. У відповідності з основним поняттями всі логічні вирази можуть набувати лише двох значень: true (істинно) і false (хибно). Синонімами цих слів є твердження “так” і “ні”. Оскільки вони коротші, за “істинно” і “хибно”, надалі будемо використовувати саме слова “так” і “ні”, або “true” і “false”.

Логічних значень true і false набувають твердження та їх комбінації. В той же час логічні операції можна використовувати і до операцій з числовими величинами, але в останньому випадку потрібно бути дуже обережним, оскільки результат, виданий комп’ютером, може не співпадати з очікуваним. Відбувається це лише по одній причині: результат завжди той, що і повинен бути, але початкуючі програмісти не завжди розуміють той факт, що логічні операції над чисельними змінними відбуваються на рівні бітів, а не байтів. Тому саме зараз і настав той час, коли нам з вами необхідно розібратись в способах збереження і передачі інформації в пам’яті ПЕОМ.

Найменшою одиницею інформації є біт. Значення одного біта може бути 0 або 1. Образно кажучи, оскільки ПЕОМ є абревіатурою від персональна електронно–обчислювальна машина, то і розуміє ця машина мову електричних сигналів. Є сигнал – 1, немає сигналу – 0. Вісім біт утворюють 1 байт.

По суті справи в основі довільної ПЕОМ лежить двійкова арифметика – тобто всі операції відбуваються не в звичній нам десятковій системі числення, а в двійковій системі числення. Комірки пам’яті (біти) нумеруються не зліва направо, як ми звикли, а з права наліво, починаючи з нуля. Утворений номер біта є показником степеня двійки у двійковому записі числа, що і приведено нижче.

2⁷

2⁶

2⁵

2⁴

2³

2²

2¹

2⁰

Для кращого розуміння вищесказаного, приведемо конкретний приклад. Нехай у нас є число, що записане в двійковій формі запису у вигляді:

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

10010011₂ = 2⁷ + 2⁴ +2¹ + 2⁰ = 128 + 16 + 2 + 1 = 147₁₀

Як бачимо, для нас труднощів у переводі машинного зображення числа у двійковій формі запису в звичну для нас десяткову систему запису не викликає. Дещо трохи складніше при переході від десяткової системи числення до не звичної для нас двійкової системи числення. Тут можна порадити використовувати простий підбір суми степенів двійки на підставі вищенаведеної таблиці, а якщо це не влаштовує вас, то приведемо алгоритм переводу число з десяткової системи числення у двійкову. Спочатку ми цей алгоритм застосуємо і зобразимо, а лише потім його опишемо. Знову ж таки, для кращого розуміння використаємо конкретний приклад. Нехай нам потрібно перевести у двійкову систему числення число 156. Ділимо в стовпчик на 2, правда, дещо порушуючи класичні правила ділення в стовпчик. Ми будемо ділити одразу “все” число (див. схему на наступній сторінці).

А тапер опишемо сам алгоритм: Ділимо дане десяткове число націло на 2 в стовпчик до тих пір, доки в частці не отримаємо 0, після цього всі остачі, отримані на кожному закінченому етапі ділення записуємо в зворотному порядку. Отримана послідовність одиниць і нулів і буде двійковим зображенням даного десяткового числа. Отриманий у частці 0 є ознакою закінчення ділення в стовпчик – про це слід обов’язково пам’ятати.

156 к 2

15678 к 2

0 7834 к 2

0 3417 к 2

0 16 8 к 2

1 8 4 к 2

0 42 к 2

0 21 к 2

156₁₀ = 10001000₂ 0 0 0 Ю ! Все

Зрозуміло, що в ПЕОМ використовують крім двійкової системи числення ще й системи числення при основі 8 та 16, але розгляд цих систем числення не є метою нашого курсу, тому обмежимось лише знайомством з двійковою системою числення, оскільки вона буде потрібна нам для кращого розуміння процесу виконання комп’ютером логічних операцій, іншим же рекомендуємо звернутись до відповідної літератури.

Отже, переходимо до головного завдання даного параграфа. У мові Pascal реалізовано 4 логічні операції: not, and, or та xor. Кожна з перечислених логічних операцій має свою назву:

not – логічне “ні” (інверсія або заперечення);

and – логічне “і” (кон’юкція або логічне множення);

or – логічне “або” (диз’юнкція або логічне додавання);

xor – логічне “виключне або”;

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

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

Отже, в процесі виконання логічних операцій результат знову ж таки може набувати лише одного з двох булівських значень: true або false. Результат можна визначити згідно такої таблиці:

X Y not X X and Y X or Y X xor Y

false false true false false false

false true true false true true

true false false false true true

true true false true true false

Таблиця 3. Таблиця істинності логічних операцій.

Словесно, цю таблицю для кожної з операцій можна сформулювати так:

n Операція not завжди змінює значення логічної змінної на протилежне.

n Операція and набуває значення true тоді і тільки тоді, коли обидві змінні, що приймають участь у висловлюванні мають значення true.

n Операція or набуває значення true у тому випадку, коли хоча б одна із логічних змінних має значення true.

n Операція xor набуває значення true при умові, що тільки одна з двох логічних змінних мала значення true.

Ще раз наголошуємо, що логічні операції над числовими змінними виконуються на бітовому рівні. Тобто, якщо нам потрібно вручну виконати операції над числовими змінними, то потрібно спочатку перевести їх у двійкову форму запису, виконати побітно необхідну операцію і результат перевести знову в десятковий вигляд. При виконанні тих же дій на ПЕОМ цього робити не потрібно, так як комп’ютер створіння “розумне” і сам виконує необхідні перетворення.

Пояснимо це на прикладі.

Задача 14. Задано два числа: 113 і 47. Виконати операції: not 113, 113 and 47, 113 or 27, 113 xor 27. Результат подати у десятковому вигляді.

Розв’язання: Спочатку перетворюємо задані числа у двійкову форму запису: 113₁₀ = 1110001₂; 47₁₀ = 101111₂, після цього виконуємо відповідні операції. Так само як і при виконанні арифметичних дій так і при виконанні логічних операцій, якщо у двійковому запису не вистачає відповідних розрядів, то спереду можна дописувати необхідну кількість нулів.

Отже, операція not:

not 1110001 = 0001110 1110₂=14₁₀.

Але давайте перевіримо результат при допомозі нашого електронного партнера, для цього просто дамо команду: a := 113; write (not a);

Запускаємо і ... що це? На екрані чомусь число –114. Звідки воно взялось? Може ми забули дописати нулі? Пробуємо:

not 01110001 = 10001110 10001110₂=142₁₀.

Знову не те! Що ж ще може бути? Так, а якого типу у нас змінна а? Integer? Що ж поміняємо на byte! Знову запускаємо на виконання... отримали 142! Це те, що ми очікували, але причому тут дві різні відповіді! Не здогадались? А ми ж попереджали, що можуть бути результати, які ви не очікуєте! Гаразд, внесемо ясність. Справа в тому, що тип byte може приймати значення від 0 до 255 (згадаєте діапазони значень змінних, приведені на початку книги!). Якщо від 255 відняти 113, то ми і отримаємо число 142. Спробуйте тепер самостійно дати пояснення для типу integer та перевірте себе на інших типах цілочисельних змінних. Крім того, є ще одне пояснення способу отримання вірного результату при виконанні операції not, але бажано, щоб ви самі до нього додумались. Якщо це вам не вдалось вам необхідно ще раз ретельно розібратись з раніше вивченим матеріалом.

При виконанні інших дій ускладнень не виникає:

1110001 1110001 1110001

and or xor

010111101011110101111

0100001₂=33₁₀ 1111111₂=127₁₀ 1011110₂=94₁₀

Задачу розв’язано.

Операція xor має одну цікаву властивість, а саме: якщо a xor b = c, то c xor b =a. Саме цю властивість операції xor в застосуванні до числових змінних часто використовують при складанні різноманітних алгоритмів по шифруванню інформації. Наведемо приклад. Нехай нам потрібно захистити інформацію від несанкціонованого доступу. Не будемо придумувати “наворочений” алгоритм, а просто зашифруємо слово при допомозі операції xor над кожним символом інформації. Припустимо, що інформацією є слово “Олег”. За “код” приймемо довільне число в межах від 0 до 255, наприклад, число 55 (просто ми мріємо вчитись на одні п’ятірки!). Слово “Олег” у комп’ютерному представленні являє собою послідовність чисел: 142 171 165 163. Провівши над кожним з них операцію xor 55 отримаємо нову послідовність: 185 156 146 148, яка в символьному представленні буде мати вигляд “¦ЬТФ”. А якщо ми пам’ятаємо код, то повторне застосування операції xor 55 до вже зашифрованого слова знову дасть слово “Олег”. Все, що нам потрібно – це пам’ятати код! Погодьтесь, що практично здогадатись про те, що отримане слово колись було “Олегом” дуже важко. При справжньому шифруванні використовуються досить складні алгоритми з декількома кодами, які в свою чергу можуть модифікуватись в процесі шифрування і тоді процес розшифровки стає практично не можливим, або, точніше кажучи, – економічно не вигідним.

Програму, що реалізує описаний спосіб шифрування ми напишемо при розгляді питання про роботу з літерними величинами.

Читайте також:

<== попередня сторінка	\|	наступна сторінка ==>
Стандартні операції для роботи з символьною інформацією.	\|	Вправи та завдання

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.007 сек.