Операції з бітами. Бітові поля

1. Порозрядні логічні операції

Для відстеження стану різних програмних об’єктів можна використовувати біти змінних. Окрім того, бітові операції лежать в основі обробки цифрових сигналів. За допомогою цих операцій  можемо з одного чи декількох сигналів на вході одержати новий сигнал.
На базі платформи Intel 1 байт=8 біт інформації. Кожен біт може приймати значення 0 або 1. Таким чином, у кожному байті може бути закодовано будь-яке ціле число від 0 до 255, оскільки 2⁸=256. Біти в байті нумерують від нуля справа наліво (←).

Порозрядні (побітові) операції можна виконувати з будь-якими цілими змінними та константами. Ці дії не застосовують до змінних типу float та double. Результатом побітових операцій завжди є ціле число.
У таблиці наведено побітові логічні операції, що застосовують у мові програмування С.

Таблиця - Порозрядні логічні операції

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

2. Операція зсуву

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

10001010 << 2;

одержимо результат 00101000. Кожен біт зсувається вліво на дві позиції, а пусті біти заповнюються нулями.
Зсув бітів змінної на одну позицію вліво приводить до такого ж результату, як і множення числа на 2. У загальному випадку, якщо виконати зсув бітів на n кроків, то одержимо результат, що дорівнює множенню змінної на 2ⁿ.

Операція зсуву вправо >> зсуває біти змінної на крок, указаний у правому операнді. Наприклад, зсув 00101011 >> 2; приводить до результату 00001010. Цю операцію можна використати замість ділення значення змінної на величину 2ⁿ.
Типові функції при роботі з бітами наведено у таблиці, де data – те число, з бітами якого виконують дію; bit – номер біта. В усіх функціях mask = 1.

Таблиця - Робота з окремими бітами

3. Застосування бітових операцій

Маски

Операції AND та OR дозволяють гарантовано виставити певні біти в 1 та 0; такі операції звуть «накладанням маски».
Припустимо, нас цікавлять лише останні 4 біти числа x, тоді x&0xF «вимкне» (зробить нулями) всі біти, окрім потрібних.

Прапорці

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

const int SUNDAY = 0x1;
const int MONDAY = 0x2;
const int TUESDAY = 0x4;
const int WEDNESDAY = 0x8;
const int THURSDAY = 0x10;
const int FRIDAY = 0x20;
const int SATURDAY = 0x40;
int flags = MONDAY | WEDNESDAY | FRIDAY; //виставлені прапорці по 3 днях тижня
…
if(flags & WEDNESDAY) … //якщо прапорець «середа» висталений…

Бітові поля вручну

Можна зберігати і більші блоки даних. Наприклад, можна умовно поділити байт між двома змінними в 3 і 5 бітів:

const char LOWER5_MASK = 0x1F;
const char UPPER3_MASK = 0xE0;
unsigned char c;
c &= UPPER3_MASK; // пишемо 0 в молодші 5 біт
c |= 11; //зберігаємо число до 32 в молодші біти
c &= LOWER5_MASK // пишемо 0 в старші 3 біти
c |= 4<<5; //зберігаємо число до 8 в старші 3 біти
std::cout<<((c&UPPER3_MASK)>>5); //виводимо вміст старших 3 бітів

Звісно, це не дуже зручно, тому, наприклад, в мові C є вбудований засіб для подібних операцій – бітові поля.

Встановити біти з m-го до n-го

При роботі з масками і полями часто потрібно отримати числа вигляду 0b0..01..10..0 (група нулів, група одиниць і знову група нулів), або ж навпаки 0b1..10..01..1 (одинці, нулі і знову одиниці). Робимо послідовно:

x = 1;
x <<= (m-n+1); //другий параметр - довжина групи нулів
x -= 1; //тепер x має вигляд 0b0..01..1
x <<= n;

А тепер записуємо це компактно

x = (1<<(m-n+1)-1)<<n;

Звісно, щоб отримати протилежну маску, треба застосувати доповнення:

x =~( (1<<(m-n+1)-1)<<n);

Маніпуляції з ASCII

Багато хто знає, що можна перетворювати цифри в числа відніманням коду символу '0'. Оскільки '0'=0x30, тобто останні 4 біти містять нулі, цю ж операцію можна робити бітовими операціями, вимкнувши старші біти числа

char c = '6';
printf("%d\n", c & 0xF); // Виведе 6

Великі і малі латинські літери в ASCII розрізняються на 32, причому у великих 5-й біт завжди 0, а у маленьких – завжди 1. Відповідно,

const char CASE_MASK = 0x20;

char ch1 = 'a' & ~CASE_MASK;      //  'A'
char ch2 = 'B' | CASE_MASK;       // 'b'
char ch3 = 'C' ^CASE_MASK;        // 'c'

виведе “Abc“ – перша операція вимикає відповідний біт, друга – вмикає, а третя – змінює його значення на протилежний.
Зауважу, що бажано так не робити (хто користується ASCII в часи Unicode?), але іноді можна зекономити пару тактів процесора чи символів коду при змагальному програмуванні.

Змішування за допомогою XOR

Виключне АБО – досить цікава операція. Наприклад, будь-яке число після застосування цієї операції із самим собою стає 0:

a^a==0

Вона у певному «змішує» числа, а потім дозволяє їх «розділити»:

x = a ^ b;//змішане число
x^a == b; //виділяємо b за допомогою a
x^b == a; //виділяємо a за допомогою b

Ця властивість операції використовується в криптографії: якщо змішати XOR-ом корисні дані з випадковим ключем і передати окремо «заксорені» дані, а окремо ключ, то отримувач зможе відновити дані (тільки, будь ласка, не робіть так у реальних програмах, користуйтеся перевіреними надійними криптографічними алгоритмами).
Вона ж дозволяє обмінювати числа без додаткової змінної. Послідовність

a ^= b;
b ^= a;
a ^= b;

або ж скорочено

a ^= b ^= a ^= b;

обмінює змінні a та b значеннями.

Знаходження min та max

min = (y ^ (x ^ y) & -(x < y));
max = (x ^ (x ^ y) & -(x < y));

Тут основна ідея в тому, що -(x<y) буде дорівнювати 0 (всі біти нульові), якщо порівняння не виконується, і -1 (тобто всі біти 1), якщо виконується. Далі виконується XOR або з 0, або з x^y залежно від x<y.

Множення і ділення на степені 2

Операції зсуву фактично є операціями множення (ліворуч) і ділення (праворуч) на степінь 2 – так само, як дописування нулів  чи викреслення знаків в кінці десяткового числа множить чи ділить на 10.
5<<2 == 20 //тобто 5*(2²).

Перевірка, чи є число степенем 2

if((x!=0) && (x & (x-1) == 0)) …

Оскільки число 2ⁿ має вигляд 0b100…0 (n нулів), а 2ⁿ -1 – 0b11..1 (n одиниць), а при будь-якому іншому числі перенесення 1 зі старшого розряду не відбудеться і AND даватиме ненульове значення.
Звісно, за правилами мови C x!=0 у булевому виразі еквівалентно самому x, а щось ==0 - ! щось, і можна записати

if(x && !(x&(x-1)))...

Перевірка на парність (чи на ділення на степінь 2)

if(x&1==0) //x – парне

Останній біт відповідає останній цифрі; як в десятковій системі числа, що закінчуються на парну цифру, є парними, так буде і в двійковій.
Те саме стосується і вищих степенів 2 – треба брати більшу кількість цифр

if(x&(1<<3-1)==0) //перевіряємо, чи ділиться на 2**3==8

Циклічний зсув числа n на d розрядів ліворуч

x = (n << d)|(n >> (sizeof(n)*8 - d));

Оскільки немає вбудованого оператора циклічного зсуву, користуємося арифметичним/логічним.

Підрахувати кількість одиниць у двійковому представленні числа

Алгоритм Кернігана

int count = 0; 
while (x) 
{ 
    x &= (x-1); 
    count++; 
}

4. Практичне використання побітових операцій

Побітові операції мають різні практичні застосування в програмуванні. Деякі поширені випадки використання включають:

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

Приклад: 

// Встановлення 4-го та 5-го бітів на 1, зберігаючи інші біти без змін
int number = 0b00110011;
int mask = 0b00011000;
int result = number | mask; // результат = 0b00111011

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

Приклад: 

// Шифрування XOR
int data = 0b11001100;
int key = 0b10101010;
int encryptedData = data ^ key; // зашифровані дані = 0b01100110

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

Приклад: 

// Множення на ступні 2, використовуючи зсув вліво
int number = 5;
int result = number << 3; // результат = 5 * 2^3 = 40

Поради з безпеки

Коли використовуються побітові операції для цілей безпеки, важливо забезпечити безпечну реалізацію алгоритмів, щоб уникнути вразливостей. Ось кілька порад з безпеки:

• Використовуйте добре відомі та перевірені криптографічні алгоритми замість спроб створити власні побітові операції для шифрування.
• Регулярно оновлюйте та виправляйте криптографічні алгоритми, щоб виправити будь-які виявлені вразливості.

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

5. Бітові поля структур