Упражнения: Побитови операции

Напредък

✅ Завършени: 0 / 0📊 Напредък: 0%

💡 Напредъкът се записва локално в браузъра

ℹ️Информация за упражненията

Този набор от упражнения покрива:

Двоична бройна система и конвертиране
Основни побитови оператори (AND, OR, XOR, NOT)
Побитови сдвигове (влево и вдясно)
Битови маски и техники за манипулация
Практически приложения: флагове, RGB, оптимизации

Общо упражнения: 30 задачи в 5 нива на сложност

Лесни упражнения (EASY)

Фундаментални концепции и базови разбирания на двоичната система и побитовите оператори.

Упражнение

5-10 minЛЕСНО

Задача 1: Конвертиране от десетична в двоична система

Конвертирайте десетичното число 13 в двоична бройна система. Покажете стъпките на преобразуването.

Последователно делете на 2 и записвайте остатъците (отдолу нагоре).

Стъпки:

÷ 2 = 6, остатък 1
÷ 2 = 3, остатък 0
÷ 2 = 1, остатък 1
÷ 2 = 0, остатък 1

Резултат: Четем остатъците отдолу нагоре: 1101

Проверка: $1 \times 2^3 + 1 \times 2^2 + 0 \times 2^1 + 1 \times 2^0 = 8 + 4 + 0 + 1 = 13$ ✅

Упражнение

5 minЛЕСНО

Задача 2: Представяне на число в двоична форма

Какво е представянето на числото 127 в 8-битов unsigned char? Запишете резултата в двоична форма.

Отговор: 01111111

Обяснение:

127 е $2^7 - 1$ (всички битове освен MSB са 1)
MSB (бит 7) е 0, всички останали са 1
$127 = 64 + 32 + 16 + 8 + 4 + 2 + 1 = 01111111_2$

Упражнение

5 minЛЕСНО

Задача 3: Най-младши бит (LSB)

Въпрос: Каква е стойността на най-младшия бит (LSB) в числото 26?

A) 0
B) 1
C) 2
D) 13

Отговор: A) 0

Обяснение:

$26 = 11010_2$
Най-десният бит е LSB = 0
26 е четно число, така че LSB винаги е 0

Упражнение

5 minЛЕСНО

Задача 4: Капацитет на 16-битово число

Колко различни стойности може да представи 16-битово число без знак (unsigned short)?

Отговор: $2^{16} = 65,536$ стойности

Обхват: 0 до 65,535

Обяснение:

Всеки бит има 2 възможни стойности (0 или 1)
16 бита → $2^{16}$ комбинации

Упражнение

5-10 minЛЕСНО

Задача 5: Побитово AND

Каква е стойността на израза 7 & 5? Покажете побитовата операция.

Отговор: 5

Стъпки:

= 0111
= 0101
&   ----
(5)

Обяснение:

AND връща 1 само ако и двата бита са 1
Бит 2: 1 & 1 = 1
Бит 1: 1 & 0 = 0
Бит 0: 1 & 1 = 1
Резултат: 0101 = 5

Упражнение

5-10 minЛЕСНО

Задача 6: Побитово OR

Каква е стойността на израза 4 | 2? Обяснете резултата с двоични числа.

Отговор: 6

Стъпки:

= 0100
= 0010
|   ----
(6)

Обяснение:

OR връща 1 ако поне един бит е 1
Бит 2: 1 | 0 = 1
Бит 1: 0 | 1 = 1
Резултат: 0110 = 6

Упражнение

5 minЛЕСНО

Задача 7: Побитово NOT върху 0

Въпрос: Операторът ~ (NOT) върху числото 0 (в 8-битово представяне) дава:

A) 0
B) 1
C) 255
D) -1

Отговор: C) 255 (за unsigned char) или D) -1 (за signed char)

Обяснение:

0    = 00000000
~0   = 11111111

За unsigned char: 11111111 = 255
За signed char: 11111111 = -1 (two's complement)

Важно: Типът променя резултата!

Упражнение

5 minЛЕСНО

Задача 8: Сдвиг наляво като умножение

Въпрос: Какво прави операцията x << 1 върху числото x?

A) Умножава по 2
B) Дели на 2
C) Добавя 1
D) Изважда 1

Отговор: A) Умножава по 2

Обяснение:

Сдвиг наляво с 1 позиция удвоява числото
$x \ll 1 = x \times 2^1 = x \times 2$

Пример:

= 0101
<< 1:
(10)

$5 \times 2 = 10$ ✅

Лесни-Средни упражнения (EASY-MEDIUM)

Изграждане на разбиране и приложение на побитовите концепции.

Упражнение

10-15 minЛЕСНО-СРЕДНО

Задача 9: Проверка на бит

Напишете израз в C++, който проверява дали 3-тият бит (броейки от 0) на променлива num е установен (равен на 1).

Използвайте маска (1 << n) и AND операция.

Решение:

bool isBit3Set = (num & (1 << 3)) != 0;

// Или по-кратко:
bool isBit3Set = num & (1 << 3);

Обяснение:

1 << 3 създава маска 00001000 (бит 3 е 1)
num & (1 << 3) извлича само бит 3
Ако резултатът е != 0, битът е установен

Пример:

int num = 13;  // 1101
bool bit3 = num & (1 << 3);  // 1101 & 1000 = 1000 (true)

Упражнение

10-15 minЛЕСНО-СРЕДНО

Задача 10: Побитово XOR

Каква е стойността на израза 15 ^ 10? Покажете побитовата операция и обяснете XOR оператора.

Отговор: 5

Стъпки:

= 1111
= 1010
^    ----
(5)

Обяснение на XOR:

XOR връща 1 когато битовете са различни
XOR връща 0 когато битовете са еднакви

a	b	a ^ b
0	0	0
0	1	1
1	0	1
1	1	0

Интересно свойство: x ^ x = 0 и x ^ 0 = x

Упражнение

10-15 minЛЕСНО-СРЕДНО

Задача 11: Установяване на бит

Напишете C++ код, който установява (прави равен на 1) 5-ия бит на променлива flags, без да променя останалите битове.

Решение:

flags |= (1 << 5);

Обяснение:

1 << 5 създава маска 00100000 (само бит 5 е 1)
OR операцията |= установява бит 5 на 1
Останалите битове не се променят (OR с 0)

Пример:

unsigned char flags = 0b00001010;  // Бит 1 и 3
flags |= (1 << 5);                  // Бит 1, 3 и 5
// flags = 0b00101010

Алтернативен запис:

flags = flags | (1 << 5);

Упражнение

10-15 minЛЕСНО-СРЕДНО

Задача 12: Сдвиг надясно

Дадена е променлива int value = 80;. Каква ще бъде стойността след value >> 3? Обяснете защо.

Отговор: 10

Обяснение:

80 = 01010000
80 >> 3:
     00001010 (10)

Формула: $80 \gg 3 = 80 / 2^3 = 80 / 8 = 10$

Как работи:

Всички битове се преместват надясно с 3 позиции
Нови нули се добавят отляво
Еквивалентно на целочислено деление на $2^3 = 8$

Упражнение

10-15 minЛЕСНО-СРЕДНО

Задача 13: Извличане с битова маска

Напишете израз, който извлича последните 6 бита от променлива data използвайки битова маска.

Маска за последните 6 бита има формата 00111111.

Решение:

Hex маска
Binary маска
Формулна маска

int result = data & 0x3F;

Обяснение:

0x3F = 0011 1111 (6 единици)
AND операцията оставя само последните 6 бита

int result = data & 0b00111111;

Обяснение:

Директна двоична маска
По-ясно показва кои битове се извличат

int result = data & ((1 << 6) - 1);

Обяснение:

1 << 6 = 64 = 01000000
64 - 1 = 63 = 00111111
Универсална формула за n бита: (1 << n) - 1

Пример:

int data = 0b11011010;  // 218
int last6 = data & 0x3F;
// 11011010 & 00111111 = 00011010 (26)

Средни упражнения (MEDIUM)

Приложение и анализ на побитовите концепции за решаване на проблеми.

Упражнение

15-20 minСРЕДНО

Задача 14: Дебъгване на побитов код

Открийте грешката в следния код:

int x = 10;
if (x & 2 == 2) {
    cout << "Bit 1 is set";
}

Проверете приоритета на операторите & и ==.

Грешка: Приоритетът на == е по-висок от &!

Кодът се изпълнява като:

if (x & (2 == 2))  // x & true → x & 1

Правилен код:

if ((x & 2) == 2) {
    cout << "Bit 1 is set";
}

Или по-кратко:

if (x & 2) {
    cout << "Bit 1 is set";
}

Таблица на приоритети:

Оператор	Приоритет
`==`	По-висок
`&`	По-нисък

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

Упражнение

15-20 minСРЕДНО

Задача 15: Побитово NOT върху 0

Каква е стойността на ~0 в 32-битов signed int? Обяснете резултата.

Отговор: -1

Обяснение:

0    = 00000000 00000000 00000000 00000000
~0   = 11111111 11111111 11111111 11111111

В two's complement:

Всички битове са 1
MSB (знаков бит) е 1 → отрицателно число
11111111...11111111 = -1

Проверка:

signed int x = ~0;
cout << x;  // -1

unsigned int y = ~0;
cout << y;  // 4294967295 (2³² - 1)

Важно: Типът променя интерпретацията!

Упражнение

20-25 minСРЕДНО

Задача 16: Проверка за степен на 2

Напишете функция bool isPowerOfTwo(int n), която проверява дали числото n е степен на 2, използвайки побитови операции.

Степените на 2 имат само един единичен бит: 1, 2, 4, 8, 16...

Какво прави n & (n-1)?

Решение:

bool isPowerOfTwo(int n) {
    return n > 0 && (n & (n - 1)) == 0;
}

Обяснение:

Степени на 2 в двоична форма:

Имат само една 1 в двоичното представяне!

Как работи n & (n-1):

За степени на 2: премахва единствения бит
Резултат: 0

Пример:

   = 1000
- 1 = 0111
& 7 = 0000 ✅ (степен на 2)

   = 0110
- 1 = 0101
& 5 = 0100 ❌ (не е степен на 2)

Проверка за n > 0: Елиминира отрицателни числа и 0.

Тестване:

cout << isPowerOfTwo(8);   // true
cout << isPowerOfTwo(10);  // false
cout << isPowerOfTwo(0);   // false
cout << isPowerOfTwo(-2);  // false

Средни-Трудни упражнения (MEDIUM-HARD)

Напреднало приложение и комбиниране на побитови операции.

Упражнение

20-30 minСРЕДНО-ТРУДНО

Задача 17: Нулиране на определен бит

Напишете C++ функция, която нулира (прави равен на 0) определен бит на позиция pos в числото num.

unsigned int clearBit(unsigned int num, int pos) {
    // Вашият код тук
}

Използвайте NOT (~) за да инвертирате маска и AND (&) за да нулирате бита.

Решение:

unsigned int clearBit(unsigned int num, int pos) {
    return num & ~(1 << pos);
}

Обяснение:

1 << pos: Създава маска с 1 на позиция pos
```
Пример: pos=3 → 00001000
```
~(1 << pos): Инвертира маската (0 на позиция pos)
```
~00001000 = 11110111
```
num & ~(1 << pos): AND нулира само бит pos
```
10111010 & 11110111 = 10110010
```

Алтернативен подход:

unsigned int clearBit(unsigned int num, int pos) {
    unsigned int mask = ~(1u << pos);
    return num & mask;
}

Тестване:

unsigned int x = 0b11111111;  // 255
x = clearBit(x, 3);           // 0b11110111 (247)

Упражнение

25-35 minСРЕДНО-ТРУДНО

Задача 18: Система за разрешения с флагове

Даден е следният код за управление на разрешения:

#define READ    0b001
#define WRITE   0b010
#define EXECUTE 0b100

unsigned char permissions = READ | EXECUTE;

Напишете код, който:

Проверява дали има WRITE разрешение
Добавя WRITE разрешение
Премахва READ разрешение

Решение:

// 1. Проверка за WRITE разрешение
bool hasWrite = (permissions & WRITE) != 0;
// Или по-кратко:
bool hasWrite = permissions & WRITE;

cout << "Has WRITE: " << hasWrite << "\n";  // false

// 2. Добавяне на WRITE разрешение
permissions |= WRITE;
cout << "After adding WRITE: " << (int)permissions << "\n";  // 7 (111)

// 3. Премахване на READ разрешение
permissions &= ~READ;
cout << "After removing READ: " << (int)permissions << "\n";  // 6 (110)

Пълен пример:

#include <iostream>
using namespace std;

#define READ    0b001
#define WRITE   0b010
#define EXECUTE 0b100

void printPermissions(unsigned char p) {
    cout << "READ: " << (p & READ ? "YES" : "NO") << "\n";
    cout << "WRITE: " << (p & WRITE ? "YES" : "NO") << "\n";
    cout << "EXECUTE: " << (p & EXECUTE ? "YES" : "NO") << "\n";
    cout << "Binary: " << bitset<3>(p) << "\n\n";
}

int main() {
    unsigned char permissions = READ | EXECUTE;

    cout << "Initial permissions:\n";
    printPermissions(permissions);  // 101

    // 1. Проверка
    if (!(permissions & WRITE)) {
        cout << "No WRITE permission\n\n";
    }

    // 2. Добавяне
    permissions |= WRITE;
    cout << "After adding WRITE:\n";
    printPermissions(permissions);  // 111

    // 3. Премахване
    permissions &= ~READ;
    cout << "After removing READ:\n";
    printPermissions(permissions);  // 110

    return 0;
}

Таблица на операциите:

Операция	Код	Резултат
Проверка	`p & FLAG`	true/false
Добавяне	`p \|= FLAG`	Установява бита
Премахване	`p &= ~FLAG`	Нулира бита
Toggle	`p ^= FLAG`	Инвертира бита

Упражнение

25-35 minСРЕДНО-ТРУДНО

Задача 19: Извличане на RGB компоненти

Дадено е 32-битово RGB число 0x00FF8040 (формат: 0x00RRGGBB).

Напишете функции, които извличат стойностите на червения, зеления и синия компонент.

Използвайте маски и сдвигове:

Red: бит 16-23
Green: бит 8-15
Blue: бит 0-7

Решение:

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

Обяснение:

Структура на цвета:

0x00FF8040
  00 FF 80 40
  |  |  |  |
  X  R  G  B

Извличане на Red:

0x00FF8040 & 0x00FF0000 = 0x00FF0000
0x00FF0000 >> 16 = 0x000000FF (255)

Тестване:

Color purple = 0x00800080;

cout << "Red: " << (int)getRed(purple) << "\n";     // 128
cout << "Green: " << (int)getGreen(purple) << "\n"; // 0
cout << "Blue: " << (int)getBlue(purple) << "\n";   // 128

Color newColor = makeColor(255, 128, 64);
cout << hex << "Color: 0x" << newColor << "\n";     // 0xFF8040

Бонус: Alpha channel (прозрачност) на бит 24-31:

unsigned char getAlpha(Color c) {
    return (c & 0xFF000000) >> 24;
}

Упражнение

25-35 minСРЕДНО-ТРУДНО

Задача 20: Броене на установени битове

Напишете функция int countSetBits(unsigned int n), която брои колко бита са установени (равни на 1) в числото n.

Използвайте техниката n & (n-1).

n & (n-1) премахва най-десния единичен бит. Колко пъти трябва да се извърши, докато n стане 0?

Решение:

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

Обяснение:

Как работи n & (n-1):

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

8     = 1000
8-1   = 0111
8&7   = 0000  (премахната последната 1)

Демонстрация:

n = 13 (1101)
count = 0

Iteration 1:
13 & 12 = 1101 & 1100 = 1100 (12)
count = 1

Iteration 2:
12 & 11 = 1100 & 1011 = 1000 (8)
count = 2

Iteration 3:
8 & 7 = 1000 & 0111 = 0000 (0)
count = 3

Result: 3 единични бита ✅

Производителност:

Времева сложност: $O(\text{брой единични битове})$
По-бързо от проверка на всеки бит поотделно!

Алтернативен подход (наивен):

int countSetBits(unsigned int n) {
    int count = 0;
    for (int i = 0; i < 32; i++) {
        if (n & (1 << i)) {
            count++;
        }
    }
    return count;
}

Но първият подход е по-ефективен за числа с малко единици!

Тестване:

cout << countSetBits(0);    // 0
cout << countSetBits(7);    // 3 (0111)
cout << countSetBits(255);  // 8 (11111111)
cout << countSetBits(13);   // 3 (1101)

Трудни упражнения (HARD)

Комплексни алгоритми и напреднали приложения на побитовите операции.

Упражнение

30-45 minТРУДНО

Задача 21: Размяна на два бита

Напишете функция void swapBits(unsigned int &num, int pos1, int pos2), която разменя битовете на позиции pos1 и pos2 в числото num.

Проверете дали битовете са различни. Ако са, използвайте XOR за да ги инвертирате.

Решение:

Оптимизиран подход
Експлицитен подход

void swapBits(unsigned int &num, int pos1, int pos2) {
    // Извличане на битовете
    bool bit1 = (num >> pos1) & 1;
    bool bit2 = (num >> pos2) & 1;

    // Размяна само ако са различни
    if (bit1 != bit2) {
        num ^= (1 << pos1);  // Инвертира бит на pos1
        num ^= (1 << pos2);  // Инвертира бит на pos2
    }
}

Обяснение:

Ако битовете са еднакви, нищо не се променя
Ако са различни, XOR ги инвертира (размяна)
Времева сложност: $O(1)$

void swapBits(unsigned int &num, int pos1, int pos2) {
    // Извличане на битовете
    unsigned int bit1 = (num >> pos1) & 1;
    unsigned int bit2 = (num >> pos2) & 1;

    // Нулиране на двата бита
    num &= ~(1 << pos1);
    num &= ~(1 << pos2);

    // Установяване на размените битове
    num |= (bit2 << pos1);
    num |= (bit1 << pos2);
}

Обяснение:

Извличаме стойностите на битовете
Нулираме и двата бита
Установяваме размените стойности

Тестване:

unsigned int x = 0b10110;  // 22 в десетична (биtove: 0=0, 1=1, 2=1, 3=0, 4=1)

cout << "Before: " << bitset<5>(x) << " (" << x << ")\n";  // 10110 (22)

swapBits(x, 1, 4);  // Размяна на позиции 1 и 4

cout << "After: " << bitset<5>(x) << " (" << x << ")\n";   // 00111 (7)

Демонстрация:

Before: 10110
         ^   ^
         4   1

After:  00111
        ^   ^
        1   4

Упражнение

30-40 minТРУДНО

Задача 22: XOR криптиране/декриптиране

Имплементирайте функция за прост XOR cipher:

void xorCipher(char* data, int length, char key) {
    // Вашият код тук
}

Обяснете защо същата функция работи и за криптиране, и за декриптиране.

XOR има свойството: (a ^ b) ^ b = a

Решение:

void xorCipher(char* data, int length, char key) {
    for (int i = 0; i < length; i++) {
        data[i] ^= key;
    }
}

Обяснение:

XOR свойства:

Комутативност: $a \oplus b = b \oplus a$
Асоциативност: $(a \oplus b) \oplus c = a \oplus (b \oplus c)$
Идемпотентност: $a \oplus a = 0$
Неутрален елемент: $a \oplus 0 = a$
Обратимост: $(a \oplus b) \oplus b = a$

Защо работи за криптиране И декриптиране:

Оригинал:     "HELLO"
Key:          'X'

Encryption:   original ^ key = encrypted
Decryption:   encrypted ^ key = original

Защо?
(original ^ key) ^ key = original ^ (key ^ key) = original ^ 0 = original

Пълен пример:

#include <iostream>
#include <cstring>
using namespace std;

void xorCipher(char* data, int length, char key) {
    for (int i = 0; i < length; i++) {
        data[i] ^= key;
    }
}

int main() {
    char message[] = "HELLO WORLD";
    char key = 'X';

    cout << "Original: " << message << "\n";

    // Encryption
    xorCipher(message, strlen(message), key);
    cout << "Encrypted: " << message << "\n";

    // Decryption (същата функция!)
    xorCipher(message, strlen(message), key);
    cout << "Decrypted: " << message << "\n";

    return 0;
}

Output:

Original: HELLO WORLD
Encrypted: 0%--. '.0-$
Decrypted: HELLO WORLD

Демонстрация на XOR:

'H' = 72  = 01001000
'X' = 88  = 01011000
XOR         --------
            00010000 = 16

16  = 00010000
'X' = 01011000
XOR   --------
      01001000 = 72 = 'H' ✅

⚠️ Важно:

Това е много прост cipher
НЕ е сигурен за реална криптография!
Уязвим на frequency analysis
Използва се само за образователни цели

Упражнение

35-50 minТРУДНО

Задача 23: Обръщане на реда на битовете

Напишете функция unsigned int reverseBits(unsigned int num), която обръща реда на всички битове в 32-битово число (първият става последен и обратно).

Извличайте всеки бит от дясно и го добавяйте отляво в резултата.

Решение:

Итеративен подход
Swap подход

unsigned int reverseBits(unsigned int num) {
    unsigned int result = 0;

    for (int i = 0; i < 32; i++) {
        // Извличане на най-десния бит от num
        unsigned int bit = num & 1;

        // Добавяне на бита в result отляво
        result = (result << 1) | bit;

        // Преместване на num надясно
        num >>= 1;
    }

    return result;
}

Обяснение:

Извличаме най-десния бит с num & 1
Сдвигаме result наляво и добавяме бита
Сдвигаме num надясно
Повтаряме 32 пъти

Демонстрация:

num = 13 (00000000 00000000 00000000 00001101)

Iteration 1: bit=1, result=1
Iteration 2: bit=0, result=10
Iteration 3: bit=1, result=101
Iteration 4: bit=1, result=1011
...
Iteration 32: result=10110000...00000000

Result: 2952790016 (10110000 00000000 00000000 00000000)

unsigned int reverseBits(unsigned int num) {
    // Размяна на съседни битове
    num = ((num & 0xAAAAAAAA) >> 1) | ((num & 0x55555555) << 1);

    // Размяна на съседни 2-битови групи
    num = ((num & 0xCCCCCCCC) >> 2) | ((num & 0x33333333) << 2);

    // Размяна на съседни 4-битови групи
    num = ((num & 0xF0F0F0F0) >> 4) | ((num & 0x0F0F0F0F) << 4);

    // Размяна на съседни байтове
    num = ((num & 0xFF00FF00) >> 8) | ((num & 0x00FF00FF) << 8);

    // Размяна на половините
    num = (num >> 16) | (num << 16);

    return num;
}

Обяснение:

Използва divide-and-conquer подход
Размяна на битове на различни нива
Времева сложност: $O(\log n)$ операции
По-ефективно от итеративния подход!

Маски:

0xAAAAAAAA = 10101010... (нечетни битове)
0x55555555 = 01010101... (четни битове)
0xCCCCCCCC = 11001100... (2-битови групи)
И т.н.

Тестване:

unsigned int x = 13;  // 00000000 00000000 00000000 00001101

unsigned int reversed = reverseBits(x);

cout << "Original: " << bitset<32>(x) << "\n";
cout << "Reversed: " << bitset<32>(reversed) << "\n";
cout << "Decimal: " << reversed << "\n";

Output:

Original: 00000000000000000000000000001101
Reversed: 10110000000000000000000000000000
Decimal: 2952790016

Анализ на сложността:

Подход	Времева сложност	Пространствена
Итеративен	$O(n)$	$O(1)$
Swap	$O(\log n)$	$O(1)$

Упражнение

40-60 minТРУДНО

Задача 24: Умножение с побитови операции

Имплементирайте функция, която изчислява x * y използвайки САМО побитови операции (без аритметични оператори *, +, -).

Използвайте алгоритъм на руските селяни или binary multiplication:

Ако y е нечетно, добавете x към резултата
Сдвигайте x наляво и y надясно

За събиране без +, използвайте XOR и AND със сдвиг.

Решение:

// Помощна функция: събиране без +
unsigned int add(unsigned int a, unsigned int b) {
    while (b != 0) {
        unsigned int carry = a & b;  // Битове, които генерират carry
        a = a ^ b;                    // Събиране без carry
        b = carry << 1;               // Carry се премества наляво
    }
    return a;
}

// Умножение без *
unsigned int multiply(unsigned int x, unsigned int y) {
    unsigned int result = 0;

    while (y != 0) {
        // Ако y е нечетно, добави x към резултата
        if (y & 1) {
            result = add(result, x);
        }

        // x = x * 2 (сдвиг наляво)
        x <<= 1;

        // y = y / 2 (сдвиг надясно)
        y >>= 1;
    }

    return result;
}

Обяснение на add функцията:

a = 5  = 0101
b = 3  = 0011

Iteration 1:
carry = 0101 & 0011 = 0001
a     = 0101 ^ 0011 = 0110 (6)
b     = 0001 << 1   = 0010 (2)

Iteration 2:
carry = 0110 & 0010 = 0010
a     = 0110 ^ 0010 = 0100 (4)
b     = 0010 << 1   = 0100 (4)

Iteration 3:
carry = 0100 & 0100 = 0100
a     = 0100 ^ 0100 = 0000 (0)
b     = 0100 << 1   = 1000 (8)

Iteration 4:
carry = 0000 & 1000 = 0000
a     = 0000 ^ 1000 = 1000 (8)
b     = 0000 << 1   = 0000 (0)

Result: 8 = 5 + 3 ✅

Обяснение на multiply функцията:

Използва binary multiplication (руски селяни):

5 * 3:

3 = 0011 (binary)

y=3 (0011): нечетно → result += 5*1 = 5
x=10, y=1

y=1 (0001): нечетно → result += 10*1 = 15
x=20, y=0

Result: 15 ✅

Демонстрация:

x = 5, y = 3

Iteration 1: y=3 (нечетно)
result = 0 + 5 = 5
x = 10, y = 1

Iteration 2: y=1 (нечетно)
result = 5 + 10 = 15
x = 20, y = 0

Result: 15 = 5 * 3 ✅

Тестване:

cout << multiply(5, 3) << "\n";    // 15
cout << multiply(7, 8) << "\n";    // 56
cout << multiply(12, 4) << "\n";   // 48
cout << multiply(0, 100) << "\n";  // 0

Времева сложност:

add: $O(\log n)$ (worst case)
multiply: $O(\log y \times \log n)$

⚠️ Ограничения:

Работи само с неотрицателни числа
За отрицателни числа е нужна допълнителна логика

Упражнение

50-70 minТРУДНО

Задача 25: BitSet клас за флагове

Създайте клас BitSet, който съхранява до 32 булеви флага в един unsigned int и предоставя методи:

void set(int pos) - установява бит
void clear(int pos) - нулира бит
bool test(int pos) - проверява бит
void toggle(int pos) - инвертира бит
int count() - брои установени битове

Решение:

class BitSet {
private:
    unsigned int bits;

public:
    // Конструктор
    BitSet() : bits(0) {}

    // Установяване на бит
    void set(int pos) {
        if (pos < 0 || pos >= 32) {
            throw std::out_of_range("Position out of range");
        }
        bits |= (1u << pos);
    }

    // Нулиране на бит
    void clear(int pos) {
        if (pos < 0 || pos >= 32) {
            throw std::out_of_range("Position out of range");
        }
        bits &= ~(1u << pos);
    }

    // Проверка на бит
    bool test(int pos) const {
        if (pos < 0 || pos >= 32) {
            throw std::out_of_range("Position out of range");
        }
        return (bits & (1u << pos)) != 0;
    }

    // Инвертиране на бит
    void toggle(int pos) {
        if (pos < 0 || pos >= 32) {
            throw std::out_of_range("Position out of range");
        }
        bits ^= (1u << pos);
    }

    // Броене на установени битове
    int count() const {
        int cnt = 0;
        unsigned int temp = bits;
        while (temp) {
            temp &= (temp - 1);  // Премахва най-десния единичен бит
            cnt++;
        }
        return cnt;
    }

    // Допълнителни полезни методи

    // Установяване на всички битове
    void setAll() {
        bits = ~0u;
    }

    // Нулиране на всички битове
    void clearAll() {
        bits = 0;
    }

    // Проверка дали поне един бит е установен
    bool any() const {
        return bits != 0;
    }

    // Проверка дали всички битове са нули
    bool none() const {
        return bits == 0;
    }

    // Проверка дали всички битове са единици
    bool all() const {
        return bits == ~0u;
    }

    // Размер (винаги 32 за този клас)
    int size() const {
        return 32;
    }

    // Достъп до вътрешното представяне
    unsigned int value() const {
        return bits;
    }

    // Принтиране в двоична форма
    void print() const {
        for (int i = 31; i >= 0; i--) {
            std::cout << ((bits & (1u << i)) ? '1' : '0');
            if (i % 8 == 0) std::cout << ' ';
        }
        std::cout << '\n';
    }

    // Overload на оператор []
    class BitReference {
    private:
        BitSet& bs;
        int pos;
    public:
        BitReference(BitSet& b, int p) : bs(b), pos(p) {}

        // Присвояване
        BitReference& operator=(bool value) {
            if (value) {
                bs.set(pos);
            } else {
                bs.clear(pos);
            }
            return *this;
        }

        // Конвертиране към bool
        operator bool() const {
            return bs.test(pos);
        }
    };

    BitReference operator[](int pos) {
        return BitReference(*this, pos);
    }

    bool operator[](int pos) const {
        return test(pos);
    }
};

Пълен пример за използване:

#include <iostream>
using namespace std;

int main() {
    BitSet flags;

    cout << "Initial state:\n";
    flags.print();
    cout << "Count: " << flags.count() << "\n\n";

    // Установяване на битове
    flags.set(3);
    flags.set(7);
    flags.set(15);

    cout << "After setting bits 3, 7, 15:\n";
    flags.print();
    cout << "Count: " << flags.count() << "\n\n";

    // Проверка
    cout << "Bit 3 is " << (flags.test(3) ? "set" : "clear") << "\n";
    cout << "Bit 5 is " << (flags.test(5) ? "set" : "clear") << "\n\n";

    // Toggle
    flags.toggle(7);
    cout << "After toggling bit 7:\n";
    flags.print();
    cout << "Count: " << flags.count() << "\n\n";

    // Използване на operator[]
    flags[10] = true;
    flags[15] = false;

    cout << "After flags[10]=true, flags[15]=false:\n";
    flags.print();
    cout << "Count: " << flags.count() << "\n\n";

    // Допълнителни проверки
    cout << "Any set? " << flags.any() << "\n";
    cout << "None set? " << flags.none() << "\n";
    cout << "All set? " << flags.all() << "\n";

    return 0;
}

Output:

Initial state:
00000000 00000000 00000000 00000000
Count: 0

After setting bits 3, 7, 15:
00000000 00000000 10000000 10001000
Count: 3

Bit 3 is set
Bit 5 is clear

After toggling bit 7:
00000000 00000000 10000000 00001000
Count: 2

After flags[10]=true, flags[15]=false:
00000000 00000000 00000100 00001000
Count: 2

Any set? 1
None set? 0
All set? 0

Производителност:

Операция	Времева сложност
`set`	$O(1)$
`clear`	$O(1)$
`test`	$O(1)$
`toggle`	$O(1)$
`count`	$O(k)$ где k = брой единични битове

Предимства:

✅ Много компактно: 32 флага в 4 байта
✅ Бързи операции
✅ Cache-friendly (един integer в един cache line)

Сравнение с bool array[32]:

bool array[32]: 32 байта
BitSet: 4 байта
Спестяване: 87.5% памет!

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

ℹ️Полезни инструменти за практика

Онлайн Compiler:

Compiler Explorer (Godbolt) - Вижте асемблерния код на побитовите операции
C++ Shell - Бърз online C++ compiler

Визуализация:

VisuAlgo - Bitmasks - Интерактивна визуализация
Binary Calculator - Калкулатор за двоични операции

Практика:

LeetCode - Bit Manipulation - 100+ задачи
HackerRank - Bitwise Operators

✅Ключови точки за запомняне

AND (&): Извличане на битове чрез маски
OR (|): Установяване на битове
XOR (^): Инвертиране на битове, криптиране
NOT (~): Инверсия на всички битове
Сдвигове: Бързо умножение/деление на степени на 2
n & (n-1): Премахване на най-десния единичен бит
x & -x: Извличане на най-десния единичен бит
Винаги използвайте скоби за да избегнете грешки с приоритет!

Практически съвети:

Използвайте unsigned типове за сдвигове
Дефинирайте константи за маски
Добавяйте коментари за яснота
Избягвайте undefined behavior (големи сдвигове)

Напредък

Лесни упражнения (EASY)​

Задача 1: Конвертиране от десетична в двоична система​

Задача 2: Представяне на число в двоична форма​

Задача 3: Най-младши бит (LSB)​

Задача 4: Капацитет на 16-битово число​

Задача 5: Побитово AND​

Задача 6: Побитово OR​

Задача 7: Побитово NOT върху 0​

Задача 8: Сдвиг наляво като умножение​

Лесни-Средни упражнения (EASY-MEDIUM)​

Задача 9: Проверка на бит​

Задача 10: Побитово XOR​

Задача 11: Установяване на бит​

Задача 12: Сдвиг надясно​

Задача 13: Извличане с битова маска​

Средни упражнения (MEDIUM)​

Задача 14: Дебъгване на побитов код​

Задача 15: Побитово NOT върху 0​

Задача 16: Проверка за степен на 2​

Средни-Трудни упражнения (MEDIUM-HARD)​

Задача 17: Нулиране на определен бит​

Задача 18: Система за разрешения с флагове​

Задача 19: Извличане на RGB компоненти​

Задача 20: Броене на установени битове​

Трудни упражнения (HARD)​

Задача 21: Размяна на два бита​

Задача 22: XOR криптиране/декриптиране​

Задача 23: Обръщане на реда на битовете​

Задача 24: Умножение с побитови операции​

Задача 25: BitSet клас за флагове​

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

Лесни упражнения (EASY)

Задача 1: Конвертиране от десетична в двоична система

Задача 2: Представяне на число в двоична форма

Задача 3: Най-младши бит (LSB)

Задача 4: Капацитет на 16-битово число

Задача 5: Побитово AND

Задача 6: Побитово OR

Задача 7: Побитово NOT върху 0

Задача 8: Сдвиг наляво като умножение

Лесни-Средни упражнения (EASY-MEDIUM)

Задача 9: Проверка на бит

Задача 10: Побитово XOR

Задача 11: Установяване на бит

Задача 12: Сдвиг надясно

Задача 13: Извличане с битова маска

Средни упражнения (MEDIUM)

Задача 14: Дебъгване на побитов код

Задача 15: Побитово NOT върху 0

Задача 16: Проверка за степен на 2

Средни-Трудни упражнения (MEDIUM-HARD)

Задача 17: Нулиране на определен бит

Задача 18: Система за разрешения с флагове

Задача 19: Извличане на RGB компоненти

Задача 20: Броене на установени битове

Трудни упражнения (HARD)

Задача 21: Размяна на два бита

Задача 22: XOR криптиране/декриптиране

Задача 23: Обръщане на реда на битовете

Задача 24: Умножение с побитови операции

Задача 25: BitSet клас за флагове

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