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
Operator
Meaning
Example (5 = 101₂, 3 = 011₂)
a & b
AND – a bit is 1 if it is 1 in both
5 & 3 = 001₂ = 1
a | b
OR – a bit is 1 if it is 1 in at least one
5 | 3 = 111₂ = 7
a ^ b
exclusive OR – a bit is 1 if they are different
5 ^ 3 = 110₂ = 6
~a
negation of all bits
a << k
shift left = multiplying by 2k
5 << 1 = 1010₂ = 10
a >> k
shift right = dividing by 2k
5 >> 1 = 10₂ = 2
Task
Expression
is bit i set?
(x >> i) & 1
set bit i
x | (1 << i)
clear bit i
x & ~(1 << i)
flip bit i
x ^ (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
Hint
Check all masks from 0 to 2n − 1: compute the weight and the value of the subset and remember the best value among those that fit. (For larger n, DP – the knapsack problem is used.)
Solution (C++)
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
long long W;
cin >> n >> W;
vector<long long> weight(n), value(n);
for (int i = 0; i < n; i++) cin >> weight[i] >> value[i];
long long best = 0;
for (int m = 0; m < (1 << n); m++) {
long long totalWeight = 0, totalValue = 0;
for (int i = 0; i < n; i++)
if ((m >> i) & 1) { totalWeight += weight[i]; totalValue += value[i]; }
if (totalWeight <= W && totalValue > best) best = totalValue;
}
cout << best << endl;
return 0;
}
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
Hint
Every mask determines the first group; the second group has the weight total − sum. The difference is |total − 2·sum|.
Solution (C++)
#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;
int main() {
int n;
cin >> n;
vector<long long> a(n);
long long total = 0;
for (auto &x : a) { cin >> x; total += x; }
long long best = total;
for (int m = 0; m < (1 << n); m++) {
long long s = 0;
for (int i = 0; i < n; i++) if ((m >> i) & 1) s += a[i];
best = min(best, llabs(total - 2 * s));
}
cout << best << endl;
return 0;
}
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?
Podešavanja kolačića
Koristimo kolačiće da bismo vam pružili najbolje moguće iskustvo. Takođe nam omogućavaju da analiziramo ponašanje korisnika kako bismo stalno poboljšavali veb lokaciju za vas.