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

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++; 
}