# Bitmask – Complete Search with Bits

Revision en1, by Nourhan_Abo-Heba, 2025-10-25 14:53:53

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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Nourhan_Abo-Heba 2025-10-25 14:53:53 3973 Initial revision (published)