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

Системи числення
Для початку нагадаю, що:
Цифра – символ, що використовується для запису чисел.
Число – абстрактне поняття, що позначає кількість предметів.
Система числення – спосіб запису чисел.

У цій статті ми будемо працювати лише з цілими числами. Запис числа має, очевидно, взаємну відповідність з числами; але запис числа і число – це різні речі.

Ми використовуємо для запису чисел позиційну десяткову систему числення. Що це означає? Позиційна система числення – це така система, де значення знаку залежить від його положення в записі числа. Як приклад непозиційної системи можна навести римську систему числення, де, скажімо, цифра V в записі XV (десять і п’ять, тобто п’ятнадцять) і VII (п’ять, один і один) має одне й те саме значення 5, хоча сама цифра знаходиться в різних місцях числа. Натомість цифра 5 у числах 15 (десять і п’ять) і 51 (п’ятдесят і один) має різні значення залежно від позиції. Але і римська, і наша системи числення ґрунтуються на використанні степенів 10 (1, 10, 100 і т.д.), тобто є десятковими. Кажуть, що число 10 є основою десяткової системи числення; 10 цифр потрібні, що позначати числа між двома степенями основи, а далі додається ще один розряд числа. Позицію цифри в числі також називають розрядом, а відповідний розряду степінь основи – вагою розряду.

Запис числа 123 означає «сума ста, двадцяти і трьох»: 123 = 1∙10²+2∙10¹+3∙10⁰. Але що буде, якщо ми спробуємо використовувати замість 10 інше число, скажімо, 8? Така система числення буде зватися вісімковою; вісімкові числа (себто числа у вісімковому записі) зазвичай позначаються в математиці нижнім індексом ₈ (наприклад, 123₈), але в цій статті я використовуватиму (як у деяких мовах програмування) префікс 0o, як у деяких мовах програмування: 0o123 =1∙8²+2∙8¹+3∙8⁰ =75. Літера o походить від англ. Octal – «вісімковий». Ще можна зустріти в деяких мовах програмування (зокрема, C та C++) запис 0123, але його радять уникати, бо не завжди очевидно, що це не десяткове число.
Запис числа без індексів чи префіксів, вочевидь, позначає наші звичні десяткові числа; в математиці більш поширений запис нижнім індексом ₁₀ (123₁₀=123), але він має неприємну рекурсію – числа в індексі десяткові без індексу.
Отже, вісімкова система. Як із нею працювати? Так само, як із десятковою:
0o0 = 0
0o1 = 1
0o2 = 2
…
0o7 = 7
0o8… Стоп! У нас же вісімкова система! Число 8 має у ній інше позначення: 0o10 – у будь-якій позиційній системі (принаймні, з тих, які ми розглянемо в цій статті), основа і її степені позначається одиницею на відповідному місці. А що ж означає 0o8? Нічого, бо це позначення не є записом вісімкового числа. У вісімковій системі всього 8 цифр, від 0 до 7.
0o7+0o1 = 0o10.

Як виконується додавання в вісімковій системі? Так само, як і в десятковій, але у вісімковій. Префікси я для зручності пропустив:
III
476
+
765
----
1463

1. 0o6+0o5 = 0o13 (тобто 6+5=11), 3 записуємо, 1 переносимо.
2. 0o7+0o6 +0o1(переніс) = 0o16 (тобто 7+6+1=14), 6 записуємо, 1 переносимо
3. 0o4+0o7 +0o1(переніс) = 0o14 (тобто 4+7+1=12), 4 записуємо, 1 переносимо
4. Дописуємо на початок перенесену одиничку.
Отже, 0o476+0o765 = 0o1463, або ж 318+501=819.

Віднімання, множення, ділення – всі операції виконуються так само. Раджу для вправи скласти таблицю множення вісімкових чисел і виконати одне множення в стовпчик 3- або 4-значних чисел у вісімковій системі.

Добре, а що робити, якщо основа системи числення більша за 10? Як ви вже могли здогадатися, нам знадобиться більш, ніж 10 цифр. У шістнадцятковій системі, яка позначається нижнім індексом – правильно – ₁₆ або ж префіксом 0x, від англ. heXadecimal – “шістнацятковий», як цифри для 10 і більше використовуються літери A, B, C, D, E, F:
0xA = 10
0xB = 11
0xC = 12
0xD = 13
0xE = 14
0xF = 15
0x10 = 16
0x1F = 31
0xFF = 255
Так само, як і в інших системах числення, 0x123 = 1∙16²+2∙16¹+3∙16⁰ = 291.

Виконаємо для прикладу одну операцію віднімання в шістнадцятковій системі:
II
A19
-
1FC
----
81D
1. 0x9<0xC, запозичуємо 1; 0x19-0xC=25-12=13=0xD,
2. 0x1-0x1<0xF, запозичуємо 1, 0x11-0x1-0xF = 17-1-15=1=0x1
3. 0xA-0x1-0x1 = 10-1-1=9=0x8
Отже, 0xA19-0x1FC=0x81D, тобто 2585-508=2077.

Для вправи раджу виконати пару арифметичних дій в шістнадцятковій системі (шістнадцяткова таблиця множення містить 16*16=256 значень, тому раджу обмежитися додаванням і відніманням).

Гаразд, а як мало цифр може бути у системі числення? Звісно, можна спробувати обійтися однією цифрою 1, але така система буде непозиційна (скільки одиничок – таке й число). Мінімальна кількість цифр у позиційній системі – 2: це 0 і 1. Така система, вочевидь, зватиметься двійковою і матиме основу 2; розряди такої системи звуться бітами. Позначатимемо її префіксом 0b, від англ. Binary – двійковий, хоча знову ж таки, математики послуговуються нижнім індексом 2: 123=1111011₂.

Таблиці додавання і множення в двійковій системі настільки маленькі, що я їх прямо тут наведу:
+ 0 1      × 0 1
0 0 1      0 0 0
1 1 10     1 0 1
Операції виконуються так само:
       1100110
      ×
       1010001
      --------
       1100110
   1100110
1100110
--------------
10000001000110
Або ж 0b1100110×0b1010001 = 102×81 = 8262 = 0b10000001000110. Зверніть увагу на те, як легко виконується множення – фактично ми лише переписали перший множник для тих розрядів, де у другому множнику стоїть 1 (кажуть, що цей біт встановлено, а якщо там 0 – то його скинуто). З іншого боку, нам потрібно значно більше символів для запису двійкових чисел, ніж в інших системах числення.

Ваги двійкових розрядів (тобто степені 2) я дуже раджу вивчити якщо не до 2²⁰, то хоча б до 2¹⁶. Це дуже допомагає в програмуванні з використанням бітових операцій. Також треба вивчити напам’ять двійкові числа до 16 (хоча взагалі що більше – тим краще).

Оскільки числа 8 і 16 є степенями 2, то ці системи мають певну спорідненість. Візьмемо для прикладу число 102 = 0b1100110 = 1∙2⁶+1∙2⁵+0∙2⁴+0∙2³+1∙2²+1∙2¹+0∙2⁰. Згрупуємо розряди по 3 з найменшого: (1∙2⁰)∙2⁶+(1∙2²+0∙2¹+ 0∙2⁰)∙2³ +(1∙2²+1∙2¹+0∙2⁰)∙2⁰ = 1∙2⁶+4∙2³+6∙2⁰. Але ж 2³ = 8, а 1∙8²+4∙8¹+6∙8⁰ – це розшифровка запису вісімкового числа 0o146! Тобто 0b1100110=0o146. Якщо цю ж операцію провести з групами по 4 розряди, то матимемо 0b1100110=0x66. І взагалі, для перетворення запису числа з двійкової системи числення у вісімкову необхідно згрупувати розряди числа по 3 з кінця і замінити кожну групу на відповідну вісімкову цифру.
0b1100110 == 0b_1_100_110 == 0o_1_4_6 == 0o146

Зворотна дія, відповідно - замість кожної цифри вісімкового числа підставляємо відповідне двійкове (якщо треба, доповнене нулями до 3 розрядів):
0o427 => 0o_4_2_7 => 0b_100_010_111 => 0b100010111

Так само легко перетворювати числа між шістнадцятковою і двійковою системами:
0b1100110 => 0b_110_0110 => 0x_6_6 => 0x66
0xA3 => 0x_A_3 => 0b_1010_0011 => 0b10100011

Для перетворення між вісімковою і шістнадцятковою системами необхідно перетворити число в двійкову форму.
Цікавий факт: дописування 0 в кінець числа у будь-якій позиційній системі еквівалентно множенню на основу системи, а викреслювання останньої цифри – діленню з відкиданням остачі на основу. Наприклад, 123*10 = 1230.

Представлення чисел у комп’ютері
Комп’ютер працює з двійковими числами, бо найлегше розрізняти 2 стани носія – наприклад, два рівня напруги, наявність і відсутність струму і т.д. Але працювати з окремими бітами незручно – надто вони малі, тому зазвичай використовуються блоки бітів по кілька байтів, найчастіше 1, 2, 4, 8 – тобто, відповідно, 8, 16, 32 і 64 біти (так, 32-х і 64-х бітні архітектури – це саме про розмір таких блоків).

Можна в різному порядку зберігати ці байти в пам’ять – починаючи з наймолодшого байту чи з найстаршого. Частіше можна зустріти збереження з молодшого байту (англ. little-endian), це дозволяє розглядати невеликі числа з великою кількістю розрядів (тобто здатні вміститися в коротші блоки) як менші без додаткового перетворення адрес; збереження зі старшого байту (англ. big-endian) зустрічається рідше, але трапляється, наприклад, при передачі даних. Це слід враховувати лише в мовах низького рівня та при перетвореннях чисел «вручну», а не штатними засобами мов програмування; але знати про це варто. 32-бітне число 266 у форматі з молодшого до старшого буде збережене як
00001010 00000001 00000000 00000000
Але при операціях воно буде оброблене як 0b_00000000_00000000_00000001_00001010.

Якщо треба зберігати лише додатні числа, все просто: 0b00000000 == 0, 0b11111111 == 255. А що ж з від’ємними числами? Поширений доповнений код представлення від’ємних чисел (англ. two's complement) розглядає старший біт числа як знак (0 - +, 1 – -), після чого всі двійкові розряди замінюються на протилежні і додається 1. Ця дещо недолуга операція дозволяє безпроблемно виконувати операції з від’ємними числами, як із додатними. Так, 8-бітне число 10 матиме вигляд 00001010, а -10 виглядатиме як 11110110. Але якщо додати ці два числа за звичайними правилами, матимемо (1)00000000 – одиниця в старшому (дев’ятому) розряді не збережеться, бо розрядів у числа всього 8, і матимемо 0. Ось ще кілька прикладів чисел у доповненому коді:
8-бітне число 127 – 01111111
8-бітне число -128 – 10000000
8-бітне число -1 – 11111111
16-бітне число -3 – 11111111 11111101
16-бітне число 20 – 00000000 00010100

Опис бітових операцій
От, нарешті, ми й дішли до бітових операцій. Бітові операції виконуються над числами в пам’яті (тобто, ще раз, блоками бітів) як над масивами бітів. Виявляється, такі операції будуть відносно дешевими з точки зору комп’ютерної техніки, вони виконуються швидше навіть за додавання. Ці операції схожі на логічні (булеві), але виконуються одночасно із усіма бітами (для бінарних операцій - попарно), а не з одним логічним значенням True/False.

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

Доповнення. Позначається NOT або ~.
B ~B
0 1
1 0
Замінює всі біти на протилежні.
На відміну від оператору заперечення ! в C-подібних мовах цей оператор не перетворює 0 на 1 – натомість, 0 (тобто 0b00000000) стає 255 чи -1 (0b11111111), залежно від того, розглядається знакове число чи ні.
Наприклад: ~0b1001 = 0b110

І (звичайний український сполучник і). Позначається AND або  &.
X Y X&Y
0 0 0
0 1 0
1 0 0
1 1 1
Результат має 1 лише там, де обидва розряди операндів мають 1.
Треба бути уважним – логічна операція AND часто позначається &&, а бітова &. У мовах програмування, де будь-яке значення, крім 0, перетворюється на True, а 0 – на False, це може призвести до непорозумінь: 7&8 == 0, але 7&&8 == True!
Наприклад: 0b1110 & 0b1001 = 0b1000

АБО. Позначається OR або |.
X Y X|Y
0 0 0
0 1 1
1 0 1
1 1 1
Результат має 1 лише там, де хоча б один розряд операндів має 1.
Тут усе трохи легше – плутанина з логічним оператором (| замість ||) не матиме негативних наслідків; але бажано все ж використовувати потрібну для конкретної задачі операцію.
Наприклад: 0b1010 & 0b1001 = 0b1011

Виключне АБО (XOR, ^).
X Y X^Y
0 0 0
0 1 1
1 0 1
1 1 0
Результат має 1 лише там, де один з операндів має 1, а другий 0.
0b1010 ^ 0b1001 = 0b11

Окрему групу бітових операцій становлять зсуви. Зсуви просто «переміщують» біти на кілька розрядів (другий операнд) ліворуч чи праворуч. Зсуви поділяються на логічні, арифметичні та циклічні. Логічні зсуви дописують на звільнене місце нулі.

Логічний зсув праворуч (SHR, >>):
0b1011 >> 2 = 0b0010

Логічний зсув ліворуч (SHL, <<):
0b1011 << 2 = 0b101100

Арифметичний зсув праворуч (SAR, >>) зберігає знак, копіюючи старший розряд (0 чи 1):
Для 1-байтової змінної
0b10101010 >> 2 = 0b11101010

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

Арифметичний зсув ліворуч (SAL, <<) фактично від логічного не відрізняється.
0b10101010 << 2 = 0b11101010

Циклічні зсуви (ROL і ROR) зазвичай не мають усталеного  позначення у мовах високого рівня; вони заповнюють звільнені розряди значеннями, витісненими в інший бік.
0b10010110 ROR 3 = 0b11010010
0b10010110 ROL 4 = 0b01101001

Звісно, всі бінарні операції в C мають аналогічну операцію, що змінює перший операнд, наприклад, &=, <<= і т.д.

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

Маски
Операції 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';
std::cout<<(c&0xF); //6

Великі і малі латинські літери в ASCII розрізняються на 32, причому у великих 5-й біт завжди 0, а у маленьких – завжди 1. Відповідно,
const char CASE_MASK = 0x20;
std::cout<< char('a'& ~CASE_MASK) << char('B'| CASE_MASK)<< char('C'^ CASE_MASK);
виведе “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++; 
}