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.

$13=1⋅8+1⋅4+0⋅2+1⋅1=1101(2)=00001101(2)13=1⋅8+1⋅4+0⋅2+1⋅1=1101(2)=00001101(2)$

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

C++ code for experimenting

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 · 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 $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∈[0,10^9]$: