Бітові операції та їх використання при розв’язуванні алгоритмічних задач
· Вступ
Зазвичай при написанні розв’язків до алгоритмічних задач ми звертаємо увагу, в основному, на високо-рівневі оптимізації, що впливають на асимптотичну складність алгоритму. Низько-рівневі оптимізації використовуються рідше, бо вони, здебільшого, ускладнюють програму, роблять її важко читабельною та сприяють виникненню помилок. В цьому відношенні бітові операції становлять вийняток. Вони є одними з найбільш корисних та ефективних низько-рівневих оптимізацій. Більш того, використання бітових операцій та бітових масок часто веде до спрощення коду програми. На цій лекції ми розглянемо як можна використовувати цілі числа, як бітові маски, для представлення множин. Але розпочнемо ми лекцію з більш базових питань, поступово переходячи до розгляду конкретних технік програмування.
· Базові поняття, необхідні для маніпуляції бітами.
Основою при оперуванні з бітами в С++ є чотири бітові оператори:
· “&” – and (побітове логічне “і”);
· “|” – or (побітове логічне “або”);
· “~” – not (побітове логічне заперечення);
· “^” – xor (побітове логічне “виключне або”);
Перші три повинні здатися вам знайомими, бо вони нагадують відповідні операції над логічним типом даних (“&&”, “||” і “!”).
Розглянемо таблицю істиності для цих операторів:
A | B | !A | A & B | A | B | A ^ B |
0 | 0 | 1 | 0 | 0 | 0 |
0 | 1 | 1 | 0 | 1 | 1 |
1 | 0 | 0 | 0 | 1 | 1 |
1 | 1 | 0 | 1 | 1 | 0 |
На відміну від логічних операторів, побітові оператори виконуються над кожним бітом числа.
Надалі будемо записувати цілі числа в бітовому представленні, при цьому справа стоятиме наймолодший біт, зліва – найстарший.
Наприклад, якщо розглянемо такі цілі числа в бітовому представленні:
A = 1010 та B = 1100,
то отримаємо такі результати (знову ж таки, в бітовому представленні) виконання відповідних операторів:
A & B = 1000
A | B = 1110
A ^ B = 0110
~ A = 11…110101
Звернемо увагу на четвертий приклад: тут кількість одиниць в старших розрядах залежить від типу даних, яким представлено число А. Наприклад, якщо це 32-розрядне ціле число, то загальна кількість бітів повинна бути 32, тобто в прикладі зліва стоятиме 28 одиниць.
Для маніпуляції бітами нам знадобляться ще два оператори – оператори побітового зсуву:
· << – зсув вліво;
· >> – зсув вправо.
Оператор зсуву вліво a<<b зсуває біти числа a вліво на b позицій. Аналогічно оператор зсуву вправо зсуває біти вправо. При цьому, біти, що дописуються до числа заповнюються нулями. Наприклад, якщо А = 1010, то
А << 2 = 101000
A >> 1 = 101
Взагалі кажучи, a<<b це те саме, що число a домножити на 2b. Аналогічно a>>b еквівалентно цілочисельному діленню a на 2b. Звідси можна зробити корисний висновок:
· 2a = 1<<a
Операції побітового зсуву найчастіше використовують для встановлення певного біту в числі. Наприклад, 1<<i – це число, в якому i-ий біт встановлений (дорівнює 1), а всі решта біти рівні нулю.
· Представлення множин за допомогою бітових масок.
Для представлення множини з доменом розмірністю до 32, тобто такої, яка може містити до 32 різних елементів, будемо використовувати ціле число стандартного 32-розрядного цілого типу даних (можемо використати 64-розрядний тип, тоді дозволена кількість елементів зростає до 64, відповідно). В цьому числі, якщо і-тий біт дорівнює 1, то і-тий елемент міститься в множині; якщо ж і-тий біт дорівнює 0, то і-тий елемент в множині відсутній. Таке ціле число, яким представляється множина і будемо називати бітовою маскою множини.
Розглянемо стандартні операції над множинами і вирази, що їм відповідають при роботі з масками.
· Об’єднання множин: A | B
· Перетин множин: A & B
· Різниця множин: A & ~B
· Доповнення множини: ALL_BITS ^ A (тут ALL_BITS – маска, в якій всі біти, що відповідають елементам домена встановлені в 1)
· Додавання і-того елемента в множину (встановлення і-го біту): A |= 1<<i
· Видалення і-того елемента: A &= ~(1 << і)
· Перевірка, чи і-тий елемент належить множині: (A & (1 << і)) != 0
· Операції над бітовими масками.
Усі операції над бітовими масками, які можуть знадобитися при розв’язуванні алгоритмічних задач легко побудувати використовуючи логіку та елементарні маніпуляції з множинами, розглянуті вище. Розглянемо кілька найпоширеніших операцій над бітовими масками.
§ Знаходження наймолодшого встановленого біта.
Не важко показати, що наймолодший встановлений біт числа х можна знайти такою комбінацією арифметичних та бітових операцій: х & ~(х - 1). Результатом обчислення такого виразу є значення наймолодшого встановленого в х біта, але не його індекс. Якщо ж нам потрібно знайти індекс цього біта, то очевидним способом є пробігтися в циклі по бітах числа починаючи від наймолодшого і перевіряти їх встановлення. Цей підхід на перший погляд здається не дуже ефективним, але якщо вважати, що всі можливі 2N множин з домену величиною N можуть траплятися з однаковою ймовірністю, середнє число ітерацій такого методу буде дорівнювати всього 2.
§ Підрахунок кількості встановлених бітів.
Для підрахунку кількості бітів у масці, що дорівнюють 1 скористаємося наступним твердженням. Видалити з маски х наймолодший встановлений біт можна такою операцією: х &= x - 1.
Тепер нескладно реалізувати алгоритм підрахунку кількості бітів що дорівнюють 1 в масці х. Будемо просто видаляти встановлені біти з числа, поки воно не стане рівним 0. Роглянемо реалізацію на С++:
int countOnes(int x)
{
int k = 0;
while (x != 0)
{
k++;
x &= x - 1;
}
return k;
}
Цей алгоритм є надзвичайно ефективним, адже він виконає рівно стільки кроків, скільки в х є встановлених бітів.
§ Ітерація по всіх підмножинах даної множини.
По-перше, варто зазначити, що якщо х є маскою, що зображає деяку множину S, то всі маски, що зображають підмножини S будуть мати числове значення менше ніж х. Цей факт є корисним для задач, що розв’язуються методом динамічного програмування.
Для ітерації по всіх підмножинах множини заданої маскою mask використаємо ідею, схожу на ту, що ми використовували раніше, при підрахунку кількості встановлених бітів. Нехай у нас є деяка маска х, що відповідає підмножині множини заданої у mask. Якщо ми віднімемо від неї одиницю, то наймолодший встановлений у ній біт стане нулем, а всі, молодші за нього – одиницями. Але нам потрібно залишити серед щойно встановлених молодших бітів лише ті, які встановлені в mask, тому ми знаходимо перетин отриманої маски з mask. Таким чином, отримаємо наступний ітераційний крок: x = (x - 1) & mask.
Отже наступним оператором циклу ми проходимо по всіх підмножинах множини заданої бітовою маскою mask:
for ( x = (mask – 1) & mask; x > 0; x = (x - 1) & mask )
{ … }
· Найпоширеніші помилки при роботі з бітовими масками.
Розглянемо кілька помилок, яких найчастіше допускаються суденти при роботі з бітовими масками. Допущення решти помилок залишимо на домашнє завдання.
§ При використанні 64-розрядного типу даних для представлення маски, легко допустити помилку при застосуванні оператора зсуву вліво. При записі команди a<<b, необхідно пересвідчитися, що операнд a є 64-розрядного типу! Найчастіше помилка зустрічається в записах виду 1<<b – компілятор сприймає число 1, як ціле число типу int, тобто 32-розрядного типу, тому результат виконання операції буде теж 32-розрядним. В такому випадку потрібно писати не 1<<b, а 1LL<<b або ((long long)1)<<b , таким чином явно специфікуючи тип лівого операнда.
§ Оператори & та | мають нижчий пріоритет ніж оператори порівняння. Це означає, що вираз x & 3 == 1 буде інтерпретовано, як x & (3 == 1) , це мабуть не зовсім так, як хотілося б. Тому при використанні порівнянь бітові операції потрібно брати в дужки: ( x & 3 ) == 1
§ При виконанні інструкцій зсуву, наприклад a<<b , процесори з архітектурою x86 (тобто такі, якими ми користуємося) використовують лише молодші 5 бітів числа b (6 бітів для 64-розрядного типу). Тобто результати виконання операцій a << 34 та a << 2 будуть однаковими. А зсув на 32 зовсім не змінить число (замість того, щоб занулити всі біти). Все ж стандарт С99 каже, що результат зсуву на кількість позицій, що є більшою чи рівною ніж розмір типу змінної в бітах, є непередбачуваним. Тому краще уникати таких операцій.
Задачі
· Задача 1. SRM 359. Easy. DriveFailures.
http://www.topcoder.com/stat?c=problem_statement&pm=7702&rd=10770
Система зберігання даних може перенести деяку кількість збоїв жорстких дисків, при цьому не втративши інформацію. Вам доручено підрахувати деякі статистичні дані про цю систему. Вам відома ймовірність збою кожного з N (1 <= N <= 15) жорских дисків. Необхідно визначити для кожного і (0 <= i <= N) яка ймовірність того, що рівно i дисків вийдуть з ладу. Вважаємо, що поломки різних дисків є незалежними подіями.
Вказівки до розв’язання: Як ми можемо підрахувати, кількість різних комбінацій дисків, що зламаються є не дуже великою, вона дорівнює 2N <= 215 = 32768. Це означає, що ми можемо перебрати всі ці комбінації. Для перебору всіх комбінацій, перебиратимемо всі бітові маски довжини N, в яких біти, що дорівнюють 1 відповідатимуть дискам, що вийшли з ладу. Для кожної комбінації рахуватимемо ймовірність її виникнення (добуток ймовірностей поломки кожного диску, які відповідають встановленим бітам) і додаватимемо цю ймовірність до числа, яке відповідає ймовірності виходу з ладу k дисків (k – кількість встановлених бітів у масці, тобто кількість поломаних дисків у відповідній комбінації).
Лістинг розв’язку:
class DriveFailures {
public:
vector <double> failureChances(vector <double> P)
{
int N = P.size();
vector<double> R(N+1, 0);
int i;
int m;
int k;
double p;
for (m = (1<<N)-1; m >= 0; --m)
{
k = 0;
p = 1;
for (i= 0; i < N; ++i)
if (m&(1<<i))
{
++k;
p *= P[i];
}
else
{
p *= 1-P[i];
}
R[k] += p;
}
return R;
}
Birthday(s):
