Блог пользователя Nourhan_Abo-Heba

Автор Nourhan_Abo-Heba, история, 13 месяцев назад, По-английски

Bitmasking is one of the most powerful and elegant techniques in competitive programming. It allows us to represent subsets using bits and perform complete search efficiently.


Complete Search → Iterative Approach

We can iterate over all subsets of a set of size n using integers from 0 to (1 << n) - 1.

Each bit in the number represents whether we include the element or not.


Difference Between Terms

Term Meaning Order Matters?
Subarray Continuous part of an array Yes
Subset Any combination of elements No
Subsequence Elements in order, not necessarily contiguous Yes

Example

Suppose we have the array:

[1, 2, 5, 9]

Each bitmask from 0000 to 1111 (binary) represents a subset:

Mask (binary) Decimal Subset Example
0000 0 {}
0001 1 {9}
0010 2 {5}
0011 3 {5, 9}
0100 4 {2}
0101 5 {2, 9}
0110 6 {2, 5}
0111 7 {2, 5, 9}
1000 8 {1}
1111 15 {1, 2, 5, 9}

1 << n = (2^n) → total number of subsets.


Example 1: Count Subsequences with Sum = K

int n, k;  
cin >> n >> k;  
vector<int> a(n);
for (int &x : a) cin >> x;

int res = 0;

for (int mask = 0; mask < (1 << n); ++mask) {
    int sum = 0;
    for (int i = 0; i < n; i++) {
        if (mask >> i & 1) {
            sum += a[i];
        }
    }
    if (sum == k) ++res;
}

cout << res;

We loop through all 2^n masks and check which subsets have a sum equal to k.


Example 2: Apple Division (CSES Problem)

Find the minimum difference between the total weights of two groups of apples.

int n;
cin >> n;
vector<int> a(n);
for (auto &i : a) cin >> i;

int mn = INT_MAX;

for (int mask = 0; mask < (1 << n); ++mask) {
    int g1 = 0, g2 = 0;
    for (int i = 0; i < n; i++) {
        if (mask >> i & 1) g1 += a[i];
        else g2 += a[i];
    }
    mn = min(mn, abs(g1 - g2));
}

cout << mn;

Bitset

A bitset is an array of bits (0 or 1). It is more memory-efficient and provides useful built-in functions.

#include <bitset>
bitset<62> b;

Useful Methods

Function Description
b.count() Returns number of 1s
b.to_string() Converts to a string of 0s and 1s
b.set() Sets all bits to 1
b.reset() Sets all bits to 0
b.all() True if all bits = 1
b.any() True if any bit = 1
b.none() True if all bits = 0
b.to_ullong() Converts to unsigned long long

Example

bitset<8> a = 5;   // 00000101
bitset<8> b = 9;   // 00001001

bitset<8> c = a | b;   // bitwise OR
cout << c << "\n";     // 00001101

cout << a[2] << "\n";  // access bit #2

a = ~a;                // bitwise NOT

Complexity

  • Operations on a 64-bit bitset → O(64)
  • Operations on a 32-bit bitset → O(32)

Summary

  • Use bitmasking to represent subsets efficiently.
  • Iterate from 0 to (1 << n) - 1 for complete search.
  • Use bitset when you need fast operations on bits.
  • Common use cases: subset sum, partitioning, combinatorial search.
  • Проголосовать: нравится
  • -11
  • Проголосовать: не нравится

»
13 месяцев назад, скрыть # |
← Rev. 3  
Проголосовать: нравится 0 Проголосовать: не нравится

There is a slightly faster solution for both problems. Instead of recalculating the sum for each mask, you can update it based on the difference between the current and previous mask.

Using Gray code ordering ensures that only one element changes between consecutive masks. In contrast, normal binary ordering can flip multiple elements in a single step, so a single mask update may require several additions or subtractions, but summed over all $$$2^n$$$ masks, this results in $$$2^{n+1}−n−2$$$ total updates. With Gray code, the sum updates require exactly one addition or subtraction per mask, resulting in $$$\mathcal{O}(2^n)$$$ complexity instead of the usual $$$\mathcal{O}(2^n\cdot n)$$$. The idea is simple: track the previous mask, find the differing index, and update the sum accordingly.

Code for Example 1(with Gray code)

This approach works for any “nice” ordering, but Gray code guarantees exactly one change per mask.

PS. I couldn't add code for the version without Gray code, so it's on Ideone.

»
13 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

That's Amazing