Ім'я файлу: КНИГА.docx
Розширення: docx
Розмір: 22кб.
Дата: 05.05.2020
скачати

Розділ 2

ОСНОВИ

2.1. Маніпуляції молодшими бітами

Багато із наведених в цьому розділі формул використовуються в наступних розділах. Для того, щоб обнулити крайній справа одиничний біт, а якщо такого немає – повернути 0 ( наприклад 01011000 →01010000), використовується формула



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

Для того, щоб установити крайній справа нульовий біт, рівним 1, а якщо такого не існує – установити всі біти рівними 1

(наприклад 01100111 →10101111), можна скористатись формулою



Наведенна далі формула дозволяє створити слово з єдиним бітом 1 в позиції крайнього справа 0 в слові х, а якщо такого немає, то повернути значення 0 (наприклад 10100111→00001000)



Ця формула може використовуватись для перевірки того, чи має беззнакове ціле чисто вид -1, дорівнює нулю чи всі його біти дорівнюють 1: для цього варто результат обчислень перевірити на рівність нулю

Щоб перетворити всі завершуючі значення нульові біти в одиничні, а якщо таких немає, просто повернути в вихідне значення (наприклад 10101000→ 10101111) можна виконати наступну операцію:



Наведенна далі формула дозволяє створити слово з єдиним бітом 1 в позиції крайнього справа 0 в слові х. а якщо такого не існує, то повернути значення 0

(наприклад 10100111→00001000)



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

(наприклад, 10101000→11110111)



РОЗДІЛ 2. ОСНОВИ

Для створення слова з одиницями в позиціях завершальних нульових бітів з нульовими бітами у всіх інших місцях можна скористатися однією з наведених нижче формул (наприклад, 01011000 → 0000011)

або

або



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

(наприклад, 10100111 →11111000) використовується

Формула

Формула

виділяє крайній праворуч одиничний біт, повертаючи 0, якщо такого немає (наприклад 01011000→0001000).

Формула

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

(наприклад 01011000→00001111)

Використовуйте наведену далі формулу для створення слова з одиничними бітами в позиціях крайнього праворуч нульового біта і наступних за ним одиничних бітів х, якщо нульового біта немає - слово нз одиничних бітів, і ціле число, рівне 1, немає завершальних одиниць

(наприклад, 01010111→ 00001111):



Для того щоб обнулити крайній справа безперервний рядок одиниць

(наприклад 01011100 →01000000) [1 12], можна скористатися однією з формул

і



Ці формули можна застосувати для визначення, чи має невід'ємне ціле число вид

для деяких Для цього слід застосувати формулу і перевірити результат на рівність нулю.

Розширенні закони де Моргана

Логічні тотожності, відомі як закони де Моргана, можна розглядати як поширення, або множення, знака не. Цю ідею можна застосувати до виразів з цього розділу (і деяких інших), як показано нижче (перші два рівняння являють собою вихідні закони де Моргана)



















Ось приклад застосування цих формул:



Є проста перевірка того, чи можна реалізувати задану функцію у вигляді послідовності команд додавання, віднімання, і, або заперечення [108]. До перелічених вище командам, звичайно, можна додати інші команди з основного безлічі, які, в свою чергу, є комбінацією команд додавання, віднімання. і, або і не, наприклад можна додати команду зрушення наліво на певну величину (яка еквівалентна послідовності команд складання) або команду "множення. Команди, які не можуть бути виражені через команди додавання, віднімання та інші з основного списку, виключаються з розгляду. Критерій перевірки випливає з наступної теореми

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

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

Якщо ж таким чином (справа наліво) обчислити функцію неможливо, то її неможливо реалізувати в вигляді послідовності зазначених команд.

Найбільший інтерес представляє твердження, що будь-яка з функцій соженная віднімання, і, або і не може бути обчислена справа наліво, так що будь-яка комбінація цих функцій також володіє цією властивістю, тобто може бути обчислена справа наліво

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



Біти пронумеровані справа наліво від 0 до 31. Так як біт 2 результата є функцією тільки крайніх справа бітів вихідних операндів (біта номер 2 і бітів молодша за нього), він також обчислюється справа наліво Запишемо машинні слова , зрушене на два біта вліво, і у, зрушене на один біт вліво, як показано нижче. Додамо до запису маску, яка виділяє другий біт







0 0 … 0 1 0 0

0 0 … 0 0 0

До рядків 2 і 3 застосуємо операцію побітового і, потім, відповідно до формули (1), до одержали слову тріменім операцію побітового або з рядком 1, після чого до отриманого результату і масці (рядок 4) застосуємо операцію побітового і. В отриманому таким звертаючись слові все біти, крім другого, будуть нульовими. Виконаємо подібні обчислення для отримання інших бітів результату і об'єднаємо всі 32 слова за допомогою операції або. В результаті отримаємо шукану функцію.

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

Використовуючи цю теорему, можна відразу ж побачити, що не існує такої послідовності команд, яка обнуляє б в слові крайній зліва одиничний біт, так як для цього необхідно переглянути біти, що знаходяться зліва від нього (щоб точно знати. Що то дійсно крайній зліва одиничний біт ). Аналогічно не існує такої послідовності операцій, яка б давала зрушення вправо, циклічний зсув або зсув вліво на змінну величину, а також могла підрахувати кількість завершальних нульових бітів в слові (при підрахунку завершальних нульових бітів молодший біт результату повинен бути рівний 1, якщо ця кількість непарній , і 0, якщо парне; так що необхідно переглянути біти зліва від молодшого, щоб з'ясувати його значення).

Нове застосування

Одним із застосувань розглянутої сортування бітів є завдання пошуку наступного числа, яке більше заданого, але має таку ж кількість одиничних бітів. Навіщо це може знадобитися? Це завдання виникає при використанні бітових рядків для подання підмножин. Можливі члени безлічі перераховані в одновимірному масиві, а підмножина являє собою слово або послідовність слів, в яких біт i встановлений рівним 1, якщо i - й елемент належить цьому подмножеству. Тоді об'єднання множин обчислюється за допомогою побітової операції або над бітовими рядками, перетин - за допомогою операції і т.д.

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

Компактний алгоритм для цього завдання складено Р.У. Госпер (RW. Gosper) [44, item 175]. Нехай є деяка слово х, що представляє собою підмножину. Ідея в тому, щоб спочатку знайти в х крайню справа групу суміжних одиничних бітів наступну за нульовими бітами, а потім «збільшити» представлену тією групою величину таким чином, щоб кількість одиничних бітів залишилося незмінним. Наприклад рядок xxx011110000, де xxx - довільні біти, перетворюється в рядок xxx100000111. Алгоритм працює наступним чином. Спочатку в х визначається наймолодший одиничний біт, тобто обчислюється 5 - х & х (в результаті отримуємо 000000010000). Потім той рядок складається з х, даючи r - xxx 100000000, в якій отримано перший одиничний біт результату. Щоб отримати інші біти, встановимо n - 1 млашіх бітів слова рівними 1, де n - розмір крайней справа групи одиничних бітів у вихідному слові х. Для цього над і х виконується операція виключає або, що в нашому прикладі дає рядок 00011 111 0000.

В отриманій рядку міститься більше одиничних бітів, ніж у вихідній, тому виконаємо ще одне перетворення. Поділимо шукане число на s, що еквіваентно ero зрушення вправо (s - ступінь 2), зрушимо ero вправо ще на два розряду, що відкине ще два небажаних біта, і виконаємо операцію побітового або над отриманим числом і r. У записі комп'ютерної алгебри результат у отримують у такий спосіб.






скачати

© Усі права захищені
написати до нас