Skip to content

💻 Побитови операции: Оптимизации и Алгоритми

🎯 Въведение

Побитовите операции са сред най-бързите операции, които процесорът може да извърши. Те работят директно с двоичното представяне на числата и са ключови за оптимизация на алгоритми в състезателното програмиране. Познаването на побитовите техники може да намали сложността на решението от \(O(N^2)\) до \(O(N \cdot \log N)\) или дори до \(O(N)\).

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

int a = 5;  // Binary: 0101
int b = 3;  // Binary: 0011

// AND (&): И двата бита трябва да са 1
int c = a & b;  // 0001 = 1

// OR (|): Поне един от битовете трябва да е 1
int d = a | b;  // 0111 = 7

// XOR (^): Битовете трябва да са различни
int e = a ^ b;  // 0110 = 6

// NOT (~): Обръща всички битове
int f = ~a;     // ...11111010 (complement)

// Shift left (<<): Умножение по 2^k
int g = a << 2; // 10100 = 20 (5 * 4)

// Shift right (>>): Деление на 2^k
int h = a >> 1; // 0010 = 2 (5 / 2)

Полезни трикове

// Проверка дали n е степен на 2
bool isPowerOfTwo = (n > 0) && ((n & (n - 1)) == 0);

// Включване на i-тия бит
n |= (1 << i);

// Изключване на i-тия бит
n &= ~(1 << i);

// Toggle (обръщане) на i-тия бит
n ^= (1 << i);

// Проверка дали i-тият бит е включен
bool isSet = (n & (1 << i)) != 0;

// Изолиране на най-младшия включен бит
int lowestBit = n & (-n);

// Премахване на най-младшия включен бит
n &= (n - 1);

🛠️ Вградени функции в GCC (Builtin Functions)

Компилаторът GCC предоставя функции, които използват процесорни инструкции за побитови операции (изключително бързи, \(O(1)\)).

  • __builtin_popcount(n): Брой на включените битове (1) в n.
  • __builtin_clz(n): Count Leading Zeros (брой нули отпред). Полезно за намиране на най-старшия бит (\(\lfloor \log_2 n \rfloor = 31 - \text{clz}(n)\)).
  • __builtin_ctz(n): Count Trailing Zeros (брой нули отзад). Еквивалентно на намиране на най-младшия бит.
  • __builtin_parity(n): Връща 1 ако броят на единиците е нечетен, иначе 0.
  • За long long използвайте суфикс ll (напр. __builtin_popcountll).

Практически примери:

int n = 23;  // Binary: 10111

// Брой на единиците: 4
int ones = __builtin_popcount(n);

// Най-старши бит (position): log2(23) = 4
int msb = 31 - __builtin_clz(n);

// Най-младши включен бит (trailing zeros): 0
int lsb = __builtin_ctz(n);

// Проверка за четност на единиците
int par = __builtin_parity(n);  // 0 (четен брой)

Приложение: Обхождане на битовете

// Итерация през всички включени битове
for (int mask = n; mask > 0; mask &= (mask - 1)) {
    int bit = __builtin_ctz(mask);  // Позиция на най-младшия бит
    // Обработка на бита
}

// Или по-бърз вариант
for (int mask = n; mask; mask ^= (mask & -mask)) {
    int bit = __builtin_ctz(mask);
    // Обработка
}

🔢 Линеен Базис (Linear Basis / XOR Basis)

Линейният базис е минимално множество от числа, чиито XOR комбинации могат да генерират всяко число, което може да се генерира от оригиналното множество \(S\). - Размерът на базиса е най-много \(\log(\max(S)) \approx 60\). - Позволява бърза проверка дали число \(X\) може да се получи чрез XOR на подмножество от \(S\). - Позволява намиране на максимален XOR на подмножество.

Имплементация: 

struct LinearBasis {
    std::vector<int> basis;

    void insert(int mask) {
        for (int b : basis) {
            mask = std::min(mask, mask ^ b);
        }
        if (mask > 0) {
            basis.push_back(mask);
            std::sort(basis.rbegin(), basis.rend()); // За удобство
        }
    }

    bool canForm(int mask) {
        for (int b : basis) {
            mask = std::min(mask, mask ^ b);
        }
        return mask == 0;
    }

    int maxXor() {
        int res = 0;
        for (int b : basis) {
            res = std::max(res, res ^ b);
        }
        return res;
    }
};

⚡ SOS DP (Sum Over Subsets)

Даден е масив \(A\) с \(2^N\) елемента. Искаме да пресметнем за всяка маска \(mask\): $\(F[mask] = \sum_{sub \subseteq mask} A[sub]\)$

Наивният подход е \(O(4^N)\). SOS DP го прави за \(O(N \cdot 2^N)\).

Идея: Обработваме битовете един по един. \(dp[mask][i]\) е сумата на подмножествата на \(mask\), които се различават от \(mask\) само в първите \(i\) бита.

Оптимизирана имплементация (in-place): 

for (int i = 0; i < N; ++i) { // За всеки бит
    for (int mask = 0; mask < (1 << N); ++mask) {
        if (mask & (1 << i)) { // Ако i-тият бит е включен
            F[mask] += F[mask ^ (1 << i)];
        }
    }
}

🎭 Битови маски за оптимизация (Bitset)

std::bitset<N> е шаблон в C++, който позволява операции с масиви от битове, като използва 1 бит памет за елемент. Операциите &, |, ^ върху цели bitset-и са \(N/64\) пъти по-бързи от цикъл.

Приложение - Knapsack (Раница): Проверка кои суми са достижими. 

std::bitset<100001> reach;
reach[0] = 1;
for (int x : items) {
    reach |= (reach << x); // Всички текущи суми се изместват с x
}
Сложност: \(O(N \cdot W / 64)\).

🎯 Работа с подмножества (Submask Enumeration)

Често се налага да обходим всички подмножества на дадена битова маска. Наивният подход е \(O(2^N)\), но ако искаме само подмножествата на конкретна маска, има по-бърз начин.

Итерация през всички подмножества на маска:

// Обхожда всички подмножества на mask (включително празното)
for (int sub = mask; sub > 0; sub = (sub - 1) & mask) {
    // Обработка на sub
}
// Не забравяйте празното множество (0) ако е нужно

Итерация през комплементите на подмножествата:

// За всяко подмножество намираме комплемента му
for (int sub = mask; sub > 0; sub = (sub - 1) & mask) {
    int complement = mask ^ sub;
    // Обработка
}

Сложност: Общо време е \(O(3^N)\) ако обхождаме подмножествата на всички \(2^N\) маски, защото всеки елемент може да е в маската, в подмножеството, или в нито едно.

🎨 Приложение: Проверка на свойства на маски

Пример 1: Проверка дали две маски са несвързани

bool areDisjoint(int mask1, int mask2) {
    return (mask1 & mask2) == 0;
}

Пример 2: Обединение и сечение

int unionMask = mask1 | mask2;      // Обединение
int intersectMask = mask1 & mask2;  // Сечение
int diffMask = mask1 & (~mask2);    // Разлика (елементи в mask1, но не в mask2)

Пример 3: Генериране на всички k-битови маски

// Генерира всички маски с точно k включени бита
void generateKBitMasks(int n, int k) {
    int mask = (1 << k) - 1;  // Първата маска: k единици отдясно
    while (mask < (1 << n)) {
        // Обработка на mask

        // Gosper's Hack за следваща маска
        int c = mask & -mask;
        int r = mask + c;
        mask = (((r ^ mask) >> 2) / c) | r;
    }
}

💡 Оптимизации с битови маски в задачи

Задача: Traveling Salesman Problem (TSP)

Намиране на най-краткия път, който обхожда всички градове точно веднъж.

ДП решение: \(dp[mask][i]\) = минималната цена да посетим градовете в маската и да завършим в град \(i\).

const int INF = 1e9;
int n;  // Брой градове
int dist[20][20];  // Разстояния между градовете
int dp[1 << 20][20];

int tsp() {
    for (int i = 0; i < (1 << n); i++)
        for (int j = 0; j < n; j++)
            dp[i][j] = INF;

    dp[1][0] = 0;  // Започваме от град 0

    for (int mask = 1; mask < (1 << n); mask++) {
        for (int i = 0; i < n; i++) {
            if (!(mask & (1 << i))) continue;  // i трябва да е в маската

            for (int j = 0; j < n; j++) {
                if (mask & (1 << j)) continue;  // j не трябва да е посетен

                int newMask = mask | (1 << j);
                dp[newMask][j] = min(dp[newMask][j], 
                                     dp[mask][i] + dist[i][j]);
            }
        }
    }

    // Връщаме се в началния град
    int ans = INF;
    int fullMask = (1 << n) - 1;
    for (int i = 0; i < n; i++) {
        ans = min(ans, dp[fullMask][i] + dist[i][0]);
    }
    return ans;
}

Задача: Subset Sum с битови маски

Проверка кои суми могат да се формират от елементи на масив.

bitset<100001> possible;
possible[0] = 1;

for (int x : arr) {
    possible |= (possible << x);
}

// possible[s] е true, ако сумата s е достижима

🧮 Побитови операции и GCD/LCM

Оптимизация на GCD с битови операции (Binary GCD):

int gcd(int a, int b) {
    if (a == 0) return b;
    if (b == 0) return a;

    // Премахване на общите степени на 2
    int shift = __builtin_ctz(a | b);
    a >>= __builtin_ctz(a);

    do {
        b >>= __builtin_ctz(b);
        if (a > b) swap(a, b);
        b -= a;
    } while (b != 0);

    return a << shift;
}

Това е по-бързо от класическия алгоритъм на Евклид на някои архитектури, защото използва битови операции вместо деление.

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

  1. Codeforces 165E - Compatible Numbers (Linear Basis)
  2. Codeforces 449D - Jzzhu and Numbers (SOS DP)
  3. Codeforces 1208F - Bits and Pieces (Bitwise operations)
  4. SPOJ TSUM - Triple Sums (SOS DP вариация)
  5. AtCoder DP Contest Z - Frog 3 (Convex Hull Trick с bitset)

🏁 Заключение

Побитовите операции са есенцията на машинната оптимизация. Linear Basis е задължителен за задачи с XOR максимизация, а SOS DP е стандартна техника за задачи върху подмножества (често срещани в Codeforces Div1/Div2 C-D). Владеенето на тези техники може да превърне невъзможна за решаване задача в тривиална.

Ключови точки за запомняне: - Побитовите операции са \(O(1)\) и много бързи - Използвайте __builtin_* функциите вместо да пишете собствени - SOS DP намалява сложността от \(O(4^N)\) на \(O(N \cdot 2^N)\) - Linear Basis позволява XOR оптимизации с размер \(O(\log \max(A))\) - Bitset операциите са 64 пъти по-бързи от обикновени цикли - Винаги търсете битова интерпретация на задачата преди да пишете \(O(N^2)\) решение