Bit Manipulation Techniques

Computers store numbers in 0’s and 1’s. These numbers are represented in binary. Directly working with bits, therefore, is extremely powerful, fast and efficient. Even outside of competitive programming, bit manipulations are widely used in applications that require fast, low-level computations. Some examples include: systems programming, graphics programming, modern chess programs, etc. A very famous example of unexpected bit operation usage is the Quake III fast inverse square root algorithm. Having a repertoire of and good intuition for bit hacks can be very useful. Let’s start with basics.

Bit Shifting

We can shift all bits in a number to the left or right in the following way.

// 00101 -> 01010
int leftShift = (n << 1);
// 00101 -> 00010
int rightShift = (n >> 1);

If you are familiar with how binary numbers work (If you don’t, I strongly suggest you read up on that first), you will notice that left shifting is analogous to multiplying a number by 2 and right shifting is dividing it by 2 and taking the floor.

So, an easy way to get a power of 2 is

// get the nth power of 2
int twoPower = (1 << n);

To avoid overflow errors, use 1LL for powers above 31 and below 64.

Bit Operations

Commonly used bit operations include,

bool a, b, x;

// AND
x = (a & b);
// OR
x = (a | b);
// NOT
x = !a;
// XOR
x = a ^ b;

When done using integers, this syntax does bitwise operation. That is, it takes individual bits in the numbers’ representation and applies the operation bitwise. Here is an example

int x = 5 & 3;
// 5 -> ...101
// 3 -> ...011
// x -> ...001 = 1
cout << x << endl; // prints: 1

AND

The & operation is diminishing. It can only lose 1 bits. This can be used to check if a number has a particular bit on or off.

// check if the 24th bit of x is turned on / off 
bool check = x & (1 << 23);

OR

The | operation is additive. It can only add 1 bits. It can be used to set a certain bit on.

// set the 2nd bit of x to on
x |= (1 << 1);

NOT

The ! operator is the logical NOT function. Any data with at least one set bit will evaluate to false with this. ~ is the bitwise not operator, and this will flip every bit in a data.

This, can be used to set a bit off.

// set the 11th bit of x to off
x &= ~(1 << 10);

XOR

Exclusive OR is a very special operation, because it has some special features. It will return 1 if the input bitstream has an odd number of ones. Otherwise, it returns 0.

XOR is its own inverse and this property is used in the majority of problems involving XOR.

An important thing to note is that a series of AND or OR or XOR operations is also commutative. Meaning their order doesn’t matter. Generally, we can order numbers in an array however is more conveninent if they have to be sequentially bitwise AND, OR or XOR’ed.

Practice Problems

Bit operations are so common, they are rarely the main element of a problem. So, some of these may require a basic knowldege of some other ideas.