Bitwise Operations and Subset Masks

Lesson 5 of 7 · Advanced techniques

In a computer an integer is a sequence of bits (zeros and ones). Bitwise operations work directly on these bits and are extremely fast. The most important use at competitions: a subset of a set of n ≤ 20 elements is written as one number – a mask – so all subsets are visited with an ordinary loop.

Before you start: prior knowledge you need – generating subsets (SR), complexity (SR).
How to learn: retype and run every example, and solve the tasks at the end on your own first; open the hint and the solution only after that. All programs are in C++.

Bitwise operations

OperatorMeaningExample (5 = 101₂, 3 = 011₂)
a & bAND – a bit is 1 if it is 1 in both5 & 3 = 001₂ = 1
a | bOR – a bit is 1 if it is 1 in at least one5 | 3 = 111₂ = 7
a ^ bexclusive OR – a bit is 1 if they are different5 ^ 3 = 110₂ = 6
~anegation of all bits
a << kshift left = multiplying by 2k5 << 1 = 1010₂ = 10
a >> kshift right = dividing by 2k5 >> 1 = 10₂ = 2
TaskExpression
is bit i set?(x >> i) & 1
set bit ix | (1 << i)
clear bit ix & ~(1 << i)
flip bit ix ^ (1 << i)
is x even?(x & 1) == 0
is x a power of two?x > 0 && (x & (x − 1)) == 0
the number of ones in the binary notation__builtin_popcount(x)
#include <iostream>
using namespace std;

int main() {
    int x;
    cin >> x;
    // the binary notation of x (8 bits), from the highest to the lowest
    for (int i = 7; i >= 0; i--) cout << ((x >> i) & 1);
    cout << endl;
    cout << "ones: " << __builtin_popcount(x) << endl;
    cout << "power of two: " << ((x > 0 && (x & (x - 1)) == 0) ? "yes" : "no") << endl;
    return 0;
}

For the input 40 the program prints:

00101000
ones: 2
power of two: no
Precedence: the operators &, | and ^ have lower precedence than ==. x & 1 == 0 means x & (1 == 0)! Always write parentheses: (x & 1) == 0. For shifting by more than 31 bits use 1LL << i.

Subsets as masks

We give the elements of the set the positions 0, 1, …, n − 1. A subset is written as a number whose bit i is 1 if element i is in the subset. For example, for n = 3 the mask 5 = 101₂ stands for the subset {element 0, element 2}. All subsets are the numbers from 0 to 2n − 1:

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

int main() {
    int n;
    long long S;
    cin >> n >> S;
    vector<long long> a(n);
    for (auto &x : a) cin >> x;
    int count = 0;
    for (int mask = 0; mask < (1 << n); mask++) {        // all 2^n subsets
        long long sum = 0;
        for (int i = 0; i < n; i++)
            if ((mask >> i) & 1) sum += a[i];              // element i is in the subset
        if (sum == S) count++;
    }
    cout << count << endl;
    return 0;
}

For the input 4 5 / 1 2 3 4 the program prints 2 (the subsets {1, 4} and {2, 3}).

The complexity is O(2n · n) – for n = 20 that is about 2·107 steps. The same can be done with recursion (SR), but masks are shorter to write and combine easily with DP.

Meet in the middle

For n = 40 there are 240 ≈ 1012 subsets – too many. But the array can be divided into two halves of 20: for each we compute all subset sums (2·220 ≈ 2·106), sort one list, and for every sum from the other we count the matching ones with binary search (SR). The complexity drops from 2n to about 2n/2 · n.

Tricks with XOR

x ^ x = 0 and x ^ 0 = x hold, and the order does not matter. That is why the XOR of all elements of an array in which all numbers appear twice, except one, gives exactly that one number – in O(n) and without extra memory.

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int x = 0;
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        x ^= a;                // pairs cancel each other out
    }
    cout << x << endl;
    return 0;
}

For the input 5 / 4 7 4 9 7 the program prints 9.

Practice tasks

Every task has an example, a hint and a solution. The solutions have been checked on the examples in the text.

TASK 01Difficulty: medium

The best choice of items

There are n ≤ 20 items with a weight and a value, and a knapsack with capacity W. Print the largest total value of items whose total weight is not greater than W.

Input: n W, then n pairs weight value.

Example

Input

4 7
3 4
4 5
2 3
5 8

Output

11
TASK 02Difficulty: medium

Dividing into two groups

n ≤ 20 apples have to be divided into two groups so that the difference between the total weights is as small as possible. Print the smallest difference.

Example

Input

5
3 2 7 4 1

Output

1
Common mistakes and tips
  • Put parentheses around bitwise expressions in comparisons: ((m >> i) & 1) == 1.
  • 1 << n is an int; for n ≥ 31 use 1LL << n.
  • Masks pay off only for n up to about 20–23; for larger n another idea is needed (DP, meet in the middle).

Check your knowledge

Open the quiz

Bitwise operations

1. What is 6 & 3?




2. Which subset of the set {a0, a1, a2} does the mask 6 (110₂) stand for?




3. How many subsets does a set of 20 elements have?