You can watch my Youtube video (link) with the same content as this blog. Anyway, enjoy.

Introduction

Let's learn bitwise operations that are useful in Competitive Programming. Prerequisite is knowing the binary system. For example, the following must be clear for you already.

Keep in mind that we can pad a number with leading zeros to get the length equal to the size of our type size. For example, char has $$$8$$$ bits and int has $$$32$$$.

Bitwise AND, OR, XOR

You likely already know basic logical operations like AND and OR. Using if(condition1 && condition2) checks if both conditions are true, while OR (c1 || c2) requires at least one condition to be true.

Same can be done bit-per-bit with whole numbers, and it's called bitwise operations. You must know bitwise AND, OR and XOR, typed respectively as & | ^, each with just a single character. XOR of two bits is $$$1$$$ when exactly one of those two bits is $$$1$$$ (so, XOR corresponds to != operator on bits). There's also NOT but you won't use it often. Everything is explained in Wikipedia but here's an example for bitwise AND. It shows that 53 & 28 is equal to $$$20$$$.

53 = 110101
28 = 11100

  110101
&  11100  // imagine padding a shorter number with leading zeros to get the same length
 -------
  010100  =  20

#include <bits/stdc++.h>
using namespace std;

string to_binary(int x) {
	string s;
	while(x > 0) {
		s += (x % 2 ? '1' : '0');
		x /= 2;
	}
	reverse(s.begin(), s.end());
	return s;
}

int main() {
	cout << "13 = " << to_binary(13) << endl; // 1101
	
	int x = 53;
	int y = 28;
	cout << "x = " << to_binary(x) << ", y = " << to_binary(y) << endl;
	
	cout << "AND, OR, XOR:" << endl;
	cout << to_binary(x & y) << " " << to_binary(x | y) << " " << to_binary(x ^ y) << endl;
}

Shifts

There are also bitwise shifts << and >>, not having anything to do with operators used with cin and cout.

As the arrows suggest, the left shift << shifts bits to the left, increasing the value of the number. Here's what happens with 13 << 2 — a number $$$13$$$ shifted by $$$2$$$ to the left.

    LEFT SHIFT                             RIGHT SHIFT
       13 =     1101                          13 =   1101
(13 << 2) =   110100                   (13 >> 2) =     11   

If there is no overflow, an expression x << b is equal to $$$x \cdot 2^b$$$, like here we had (13 << 2) = 52.

Similarly, the right shift >> shifts bits to the right and some bits might disappear this way, like bits 01 in the example above. An expression x >> b is equal to the floor of $$$\frac{x}{2^b}$$$. It's more complicated for negative numbers but we won't discuss it.

So what can we do?

$$$2^k$$$ is just 1 << k or 1LL << k if you need long longs. Such a number has binary representation like 10000 and its AND with any number $$$x$$$ can have at most one bit on (one bit equal to $$$1$$$). This way we can check if some bit is on in number $$$x$$$. The following code finds ones in the binary representation of $$$x$$$, assuming that $$$x \in [0, 10^9]$$$:

for(int i = 0; i < 30; i++) if((x & (1 << i)) != 0) cout << i << " ";

(we don't have to check $$$i = 30$$$ because $$$2^{30} > x$$$)

And let's do that slightly better, stopping for too big bits, and using the fact that if(value) checks if value is non-zero in C++.

for(int i = 0; (1 << i) <= x; i++) if(x & (1 << i)) cout << i << " ";

Consider this problem: You are given $$$N \leq 20$$$ numbers, each up to $$$10^9$$$. Is there a subset with sum equal to given goal $$$S$$$?

It can be solved with recursion but there's a very elegant iterative approach that iterates over every number $$$x$$$ from $$$0$$$ to $$$2^n - 1$$$ and considers $$$x$$$ to be a binary number of length $$$n$$$, where bit $$$1$$$ means taking a number and bit $$$0$$$ is not taking. Understanding this is crucial to solve any harder problems with bitwise operations. Analyze the following code and then try to write it yourself from scratch without looking at mine.

for(int mask = 0; mask < (1 << n); mask++) {
	long long sum_of_this_subset = 0;
	for(int i = 0; i < n; i++) {
		if(mask & (1 << i)) {
			sum_of_this_subset += a[i];
		}
	}
	if(sum_of_this_subset == S) {
		puts("YES");
		return 0;
	}
}
puts("NO");

Two easy problems where you can practice iterating over all $$$2^N$$$ possibilities:
- https://mirror.codeforces.com/problemset/problem/1097/B
- https://mirror.codeforces.com/problemset/problem/550/B

Speed

Time complexity of every bitwise operation is $$$O(1)$$$. These operations are very very fast (well, popcount is just fast) and doing $$$10^9$$$ of them might fit in 1 second. You will later learn about bitsets which often produce complexity like $$$O(\frac{n^2}{32})$$$, good enough to pass constraints $$$n \leq 10^5$$$.

I will welcome any feedback. Coming next: popcount, bitsets, dp with bitmasks. I will also make a YT video on this. YT video link is at the top.

Part 2 link