Побитови операции в C++

▶⚡ Накратко

За Изпита

🎯Учебни Цели

След края на тази лекция вие ще можете да:

✓Разбиране на двоичната бройна система и представянето на числа в паметта
✓Овладяване на основните побитови оператори в C++
✓Прилагане на побитови сдвигове за оптимизация
✓Практическо използване на побитови операции в реални сценарии
✓Разпознаване на грешки и дебъгване на код с побитови операции

1. Въведение и мотивация

💡Защо са важни побитовите операции?

Побитовите операции дават програмиста директен достъп до най-ниското ниво на представяне на информацията:

Системно програмиране: Управление на хардуер, регистри, драйвери, вградени устройства
Оптимизация: Сдвиговете реализират бързи умножения и деления по степени на 2
Икономия на памет: До 32 флага в един int вместо отделни bool променливи
Обработка на данни: Декодиране, компресия, криптография

Примери от практиката

🔒 Файлови разрешения

Всеки бит представя разрешение:

Бит 0: READ
Бит 1: WRITE
Бит 2: EXECUTE

🎨 Графика (RGB)

32-битово число съхранява цвят:

Байт 0: Blue
Байт 1: Green
Байт 2: Red
Байт 3: Alpha

🔐 Криптография

XOR операции за:

Криптиране/декриптиране
Checksums
Hash функции

⚙️ Хардуерни регистри

Активация/дезактивация:

GPIO pins
Конфигурационни битове
Status flags

2. Двоична бройна система и представяне на числа

Преобразувания между десетична и двоична система

ℹ️Конвертиране между системи

Десетично → Двоично:

Последователно делим на 2
Записваме остатъците
Пример: $128_10 = 10000000_2$

Двоично → Десетично:

Сумираме степени на 2
Пример: $10110_2 = 1 \times 2^4 + 0 \times 2^3 + 1 \times 2^2 + 1 \times 2^1 + 0 \times 2^0 = 22_10$

Битови позиции

Всеки бит има стойност $2^n$
MSB (Most Significant Bit): Най-ляв бит
LSB (Least Significant Bit): Най-десен бит
8-битово число: $2^8 = 256$ стойности (0–255)

Целочислени типове в C++

Тип	Размер (бита)	Без знак (unsigned)	Със знак (signed)
`char`	8	0 ... 255	-128 ... 127
`short`	16	0 ... 65,535	-32,768 ... 32,767
`int`	32	0 ... 4,294,967,295	-2,147,483,648 ... 2,147,483,647
`long long`	64	0 ... $2^{64}-1$	$-2^{63}$ ... $2^{63}-1$

⚠️Представяне на отрицателни числа

Two's complement (допълнителен код):

MSB е знаков бит (1 = отрицателно)
Отрицателно число = инверсия + 1

Пример за -5 в 8 бита:

$5 = 00000101$
Инверсия: $11111010$
$+1 = 11111011$ (това е -5)

3. Основни побитови оператори

& - Побитово AND

Резултат: 1 само ако и двата бита са 1

int c = 12 & 25;
// 00001100
// 00011001
// --------
// 00001000 (8)

Приложение: Екстракция на битове

| - Побитово OR

Резултат: 1 ако поне един бит е 1

int c = 12 | 25;
// 00001100
// 00011001
// --------
// 00011101 (29)

Приложение: Установяване на битове

^ - Побитово XOR

Резултат: 1 когато битовете са различни

int c = 12 ^ 25;
// 00001100
// 00011001
// --------
// 00010101 (21)

Приложение: Инвертиране, криптиране

~ - Побитово NOT

Резултат: Инверсия на всички битове

int b = ~35;
// 00100011
// --------
// 11011100 (-36 в signed)

Приложение: Инверсия на маски

⚠️Внимание при NOT оператора!

При знакови числа ~ може да даде отрицателна стойност заради two's complement:

unsigned char a = ~0; // 255
int b = ~0;           // -1 (всички битове са 1)

4. Побитови сдвигове

Сдвиг наляво (<<)

✅Бързо умножение по степени на 2

Формула: $a \ll n = a \times 2^n$

int a = 5;
int r = a << 3;  // 5 * 2³ = 5 * 8 = 40

Как работи:

5  = 00000101
5 << 3:
     00101000 (40)

Всички битове се преместват наляво, нови нули отдясно.

Сдвиг надясно (>>)

✅Бързо деление на степени на 2

Формула: $a \gg n = a / 2^n$ (за unsigned)

int a = 40;
int r = a >> 3;  // 40 / 2³ = 40 / 8 = 5

Как работи:

40 = 00101000
40 >> 3:
     00000101 (5)

⚠️Разширение на знака при отрицателни числа

При signed типове, сдвиг надясно може да копира знаковия бит:

int x = -8;
int y = x >> 2;  // Може да е -2 или undefined behavior

unsigned int x = -8;  // ✅ Безопасно за логически сдвиг
unsigned int y = x >> 2;

Препоръка: Използвайте unsigned типове за сдвигове!

5. Битови маски и техники

ℹ️Какво е битова маска?

Битова маска е число с 1-ци на важните позиции и 0-ли на останалите.

Позволява филтриране чрез AND, OR, XOR операции.

Основни техники с маски

// Извличане на последните 4 бита
int val = number & 0xF;  // 0xF = 00001111

// Извличане на бит на позиция n
bool bit = (number >> n) & 1;

Пример:

int num = 0b10110101;
int lastFour = num & 0xF;  // 0b0101 (5)

// Установяване на n-ти бит на 1
val |= (1 << n);

Пример:

int flags = 0b00000000;
flags |= (1 << 3);  // 0b00001000 (установяване на бит 3)

// Нулиране на n-ти бит
val &= ~(1 << n);

Пример:

int flags = 0b11111111;
flags &= ~(1 << 3);  // 0b11110111 (нулиране на бит 3)

// Инвертиране на n-ти бит
val ^= (1 << n);

Пример:

int flags = 0b00001000;
flags ^= (1 << 3);  // 0b00000000 (инвертиране на бит 3)

// a % 2ⁿ = a & (2ⁿ - 1)
int remainder = number & 7;  // number % 8

Защо работи:

$2^n = 100...0$ (n нули)
$2^n - 1 = 011...1$ (n единици)
AND операцията оставя само последните n бита!

Пример:

int x = 25;
int rem = x & 7;  // 25 % 8 = 1
// 25 = 11001
//  7 = 00111
// AND = 00001 (1)

Напреднали техники

int lowestBit = x & -x;

Как работи:

-x е two's complement на x (инверсия + 1)
AND между x и -x оставя само най-десния единичен бит

Пример:

int x = 12;       // 1100
int neg = -x;     // ...11110100 (two's complement)
int result = x & -x;  // 0100 (4)

int countSetBits(unsigned int n) {
    int count = 0;
    while (n) {
        n &= (n - 1);  // Премахва най-десния единичен бит
        count++;
    }
    return count;
}

Защо работи: n & (n-1) премахва най-десната 1:

$12 = 1100$
$11 = 1011$
$12 & 11 = 1000$ (премахната 1)

6. Примери и практически приложения

Пример 1: Система за флагове и разрешения

#define READ    0b001  // 1
#define WRITE   0b010  // 2
#define EXECUTE 0b100  // 4

unsigned char permissions = 0;

// Добавяне на разрешения
permissions |= READ;
permissions |= WRITE;
// permissions = 0b011 (READ + WRITE)

// Проверка за разрешение
if (permissions & READ) {
    std::cout << "Има разрешение за четене\n";
}

// Премахване на разрешение
permissions &= ~WRITE;
// permissions = 0b001 (само READ)

// Проверка дали има точно определено разрешение
bool hasOnlyRead = (permissions == READ);

✅Предимства на флаговете

Компактност: 32 флага в 4 байта вместо 32 байта за bool масив
Бързина: Побитовите операции са много бързи
Стандарт: Използва се в Unix файлови системи, Windows API, и др.

Пример 2: Извличане на цветни компоненти (RGB)

typedef unsigned int Color;

// Маски за извличане на компонентите
#define RED_MASK   0x00FF0000
#define GREEN_MASK 0x0000FF00
#define BLUE_MASK  0x000000FF

// Извличане на отделни канали
unsigned char getRed(Color c) {
    return (c & RED_MASK) >> 16;
}

unsigned char getGreen(Color c) {
    return (c & GREEN_MASK) >> 8;
}

unsigned char getBlue(Color c) {
    return c & BLUE_MASK;
}

// Създаване на цвят от компоненти
Color makeColor(unsigned char r, unsigned char g, unsigned char b) {
    return (r << 16) | (g << 8) | b;
}

// Пример
Color purple = 0x00800080;
std::cout << "Red: " << (int)getRed(purple) << "\n";     // 128
std::cout << "Green: " << (int)getGreen(purple) << "\n"; // 0
std::cout << "Blue: " << (int)getBlue(purple) << "\n";   // 128

💡Защо е полезно?

В компютърната графика, всеки пиксел често се съхранява като един 32-битов integer:

Бит 0-7: Blue (0-255)
Бит 8-15: Green (0-255)
Бит 16-23: Red (0-255)
Бит 24-31: Alpha/прозрачност (0-255)

Пример 3: Конверсия в двоична система

void printBinary(unsigned int number) {
    char binary[33];  // 32 бита + null terminator
    binary[32] = '\0';

    for (int i = 31; i >= 0; i--) {
        binary[31 - i] = ((number >> i) & 1) ? '1' : '0';
    }

    std::cout << "Binary: " << binary << "\n";
}

// Пример
printBinary(42);
// Binary: 00000000000000000000000000101010

Как работи:

Сдвигаме числото надясно на i позиции
AND с 1 за да вземем само последния бит
Конвертираме в символ '0' или '1'

7. Интерактивни дейности

Дейност 1: Бърз тест

Отговор: 1

= 0101
= 0011
&   ----
(1)

Отговор: 14

= 1100
= 0110
|    ----
(14)

Отговор: 12

= 1000
= 0100
^   ----
(12)

Отговор: 12

<< 2 = 3 * 2² = 3 * 4 = 12

= 0011
<< 2:
(12)

Дейност 2: Дебъгване на код

⚠️Открийте грешката!

int x = 3;
x = x | 1 << 5;  // Дали това е валидно?

Проблем: Приоритет на операторите!

Операторът << има по-висок приоритет от |, така че израза се изпълнява като:

x = x | (1 << 5);  // Правилно

Но ако искахме (x | 1) << 5, трябва да използваме скоби:

x = (x | 1) << 5;  // С явни скоби

Съвет: Винаги използвайте скоби за яснота!

8. Чести грешки и предпазни мерки

⚠️Често срещани грешки

1. Объркване на побитови и логически оператори

// ❌ ГРЕШНО
if (x & y == 0)  // Сравнението има предимство!

// ✅ ПРАВИЛНО
if ((x & y) == 0)

2. Undefined behavior при големи сдвигове

int x = 1 << 32;  // ❌ Undefined behavior на 32-битов int

3. Разширение на знака при отрицателни числа

int x = -1;
int y = x >> 1;  // ⚠️ Може да е -1 (копира знаковия бит)

4. Забравени скоби

val |= 1 << n;   // ✅ Правилно
val = val | 1 << n;  // ✅ Също правилно (сдвигът е първи)

✅Best Practices

1. Използвайте unsigned типове за битови операции

unsigned int flags = 0;  // ✅ Предпочитано

2. Дефинирайте константи за маски

const unsigned int MASK = 0xFF;
const int BIT_5 = (1 << 5);

3. Добавяйте коментари

// Извличане на последните 8 бита
int byte = value & 0xFF;

4. Винаги използвайте скоби за яснота

result = (a & b) | (c & d);

Резюме и ключови изводи

▶⚡ Накратко

За Изпита

Допълнителни ресурси

Онлайн туториали

GeeksforGeeks - Bitwise Operators in C++ - Подробно обяснение на всички оператори
cppreference - Arithmetic operators - Официална документация
Hackerearth - Bit Manipulation Tutorial - Интерактивни примери

Визуализация и инструменти

VisuAlgo - Bit Manipulation - Визуална демонстрация на битови операции
Compiler Explorer - Вижте как компилаторът оптимизира побитови операции

Видео лекции

CS50 - Bitwise Operators - Въведение от Harvard
Back To Back SWE - Bit Manipulation - Практически техники

Практически задачи

LeetCode - Bit Manipulation Problems - Задачи с различна сложност
HackerRank - Bit Manipulation - Интерактивни упражнения
Codeforces - Bitmasks Tutorial - Напреднали техники

Книги и статии

"Hacker's Delight" by Henry S. Warren - Библията на побитовите техники
"Bit Twiddling Hacks" от Stanford - Колекция от оптимизационни трикове
C++ Primer (5th Edition) - Глава за побитови операции

▶⚡ Накратко

🎯Учебни Цели

1. Въведение и мотивация​

Примери от практиката​

🔒 Файлови разрешения

🎨 Графика (RGB)

🔐 Криптография

⚙️ Хардуерни регистри

2. Двоична бройна система и представяне на числа​

Преобразувания между десетична и двоична система​

Битови позиции​

Целочислени типове в C++​

3. Основни побитови оператори​

& - Побитово AND

| - Побитово OR

^ - Побитово XOR

~ - Побитово NOT

4. Побитови сдвигове​

Сдвиг наляво (<<)​

Сдвиг надясно (>>)​

5. Битови маски и техники​

Основни техники с маски​

Напреднали техники​

6. Примери и практически приложения​

Пример 1: Система за флагове и разрешения​

Пример 2: Извличане на цветни компоненти (RGB)​

Пример 3: Конверсия в двоична система​

7. Интерактивни дейности​

Дейност 1: Бърз тест​

Дейност 2: Дебъгване на код​

8. Чести грешки и предпазни мерки​

Резюме и ключови изводи​

▶⚡ Накратко

Допълнителни ресурси​

Онлайн туториали​

Визуализация и инструменти​

Видео лекции​

Практически задачи​

Книги и статии​

1. Въведение и мотивация

Примери от практиката

2. Двоична бройна система и представяне на числа

Преобразувания между десетична и двоична система

Битови позиции

Целочислени типове в C++

3. Основни побитови оператори

4. Побитови сдвигове

Сдвиг наляво (<<)

Сдвиг надясно (>>)

5. Битови маски и техники

Основни техники с маски

Напреднали техники

6. Примери и практически приложения

Пример 1: Система за флагове и разрешения

Пример 2: Извличане на цветни компоненти (RGB)

Пример 3: Конверсия в двоична система

7. Интерактивни дейности

Дейност 1: Бърз тест

Дейност 2: Дебъгване на код

8. Чести грешки и предпазни мерки

Резюме и ключови изводи

Допълнителни ресурси

Онлайн туториали

Визуализация и инструменти

Видео лекции

Практически задачи

Книги и статии