Bit Manipulation : A Simple Example

(Note : this article is migrated from my Medium page. Link to my Medium article lies here.)

As a casual programmer, I frequently check on sites like Codeforces and Kattis to hone my programming logic and skills. One day, I stumbled upon an interesting problem to me. At first, this problem looked quite challenging, so I tried to solve it (problem will be explained in later sections). At first, I couldn’t solve it — I couldn’t find any patterns relating to the problem. I wasn’t in such a rush, so I left the problem as it’s already midnight.

Once when I was doing nothing at the shopping mall, I went to look back at the problem, and I got an idea on how to do it — which is by using bit manipulation!

What are bitmasks?

Because I’m still on my studies, I’m still learning a lot more about computer science, hence this so far is what I know about bit manipulation.

In order to understand bit manipulation, we need to first understand bitmasks. What are bitmasks, you might ask? As you might already know, a bit is short of “binary digits” — a digit which only consist of zeros and ones. An integer variable usually have a 32 bits limit, which means it consists of 32 bits with its range of 2³² (2 derived from the state of bits — 0 or 1 which is 2 possibilities).

Bit-masks, on the other hand, are simply integers used as a set of booleans. Since booleans have a state of only True or False, it can also be represented by zeros and ones, and that is why it is called bit-masks! So, simply put:

Bit-masks take advantage of how an integer be represented in its binary form, meaning that it can be used as a compact set of booleans.

Bitwise Operators.

Bit manipulation is a technique that is used to, well, manipulate the bits that represents an integer. I’m going to show you some commonly used bitwise operators in C++.

1. Shift Left and Shift Right (<< and >>)

Shifts the binary form of an integer to left/right depending on how many shifts.

Note that shift left is equivalent to multiplying by 2, and shift right is dividing by 2 and rounding it — it’s generally faster than usual dividing operations.

int x=5; // 101 in binary
If shifted left by 1 : x=x<<1; //10 = 2 in decimal
If shifted left by 3: x=x<<3; //0 = 0 (see it as 0101)
If shifted right by 1 : x=x>>1; //1010 = 10 in decimal
If shifted right by 2: x=x>>2; //10100 = 20 in decimal

2. Bitwise OR (|)

Does an OR operation on the binary form of two integers.

int x=5; // 101 in binary
int y=9; // 1001 in binary
int z=x|y;
x = 0101
y = 1001
--------- OR
z = 1101 = 13 in decimal

3. Bitwise AND (&)

Does an AND operation on the binary form of two integers.

int x=5; // 101 in binary
int y=9; // 1001 in binary
int z=x&y;
x = 0101
y = 1001
--------- AND
z = 0001 = 1 in decimal

4. Bitwise NOT (~)

Inverts the bits of the binary form of an integer.

This operation is usually used in conjunction of other operators; for example to make an NAND or NOR operations.

5. Bitwise XOR (^)

Applies the XOR operation of the binary form of two integers.

int x=5; // 101 in binary
int y=9; // 1001 in binary
int z=x^y;
x = 0101
y = 1001
--------- XOR
z = 1100 = 12 in decimal

Fun Fact: Swapping 2 integers can be done by using XOR operations; try it out for yourself!

int a=3;
int b=5;
a=a^b; // a=6, b=5
b=a^b; // a=6, b=3
a=a^b; // a=5, b=6

Remember, this is only the bit operators, the usage will be shown in the example. It’s uncommon to use it purely like in the examples — we can do so much more than that!

A Problem with the use of Bitmask!

Back to my story of solving that problem in Kattis, here’s the problem that I was talking about in the previous section.

Abridged problem statement : An infinite binary tree, each node consisting of a fraction with numerator p and a denominator q. The left node is equal to p/(p+q), and the right node is equal to (p+q)/q. A function F(n) is defined such that it will return the fraction from the respecting node. The nodes is numbered as depicted in the illustration taken from the problem below:

The first node starts from the value of p=1 and q=1. This means that F(1)=1/1, F(2)=1/2, F(3)=2/1, so on and so forth. We are required to input the value of the fraction and outputting the N. There will be several testcases.

At a glance, this problem may not represent anything related to bit manipulation. But, it actually has two states — going to the left or right node! Before I give you my perspective on this problem, you may want to try and solve it for yourself.

My Insight to This Problem.

The problem may suggest you to manually use breadth first search (BFS) method, by using a queue. For a fraction that lies in a small N, this would be viable. However, we don’t know where the inputted fraction would lie, as this is an infinite binary tree.

So, how do we solve the problem? Here’s my logic:

• It’s better to find directly from each testcase compared to pruning, as it would take too much time and memory.
• We can represent each node with its binary form!
• p is always <q in the left node, while p is always > q in the right node.

What do you mean by using its binary form?

Well, let’s take the first, second, and third node in their binary form (1, 10, 11). With a simple analysis, we can first assume that in the left node we append a 0 from the first node, and in the right node we append a 1 from the first node.

We can further check if our analysis is correct by looking at the pattern; and it turns out to be correct! (See picture for better visual explanation.)

Why does it work?

Simple — this is a binary tree! Well of course the N would follow the pattern of binary digits!

Because we’re solving the problem from the top down, we need to append digits (if left 0, if right 1) from the front. How do we achieve such result? We use the OR operator with the shift left operator to turn on a bit in specified location.

Take a look at this pseudocode:

int result=0;
int pos=2;
result|=(1<<pos); //turning on the 2nd bit from the right (0-based)

This way, we can just put 1 if the node’s coming from the right side, and each level we go up, we increase the variable pos by one! We do this until we reach the final node (meaning, p=1 and q=1).

Here’s my solution to the problem, written in C++:

Note that because we start from the index of one, we append another 1 after we reach the initial node.

This solution, because we traverse up a binary tree, it makes the time complexity of the program of O(log n)!

Conclusion!

That problem is just one example of the usage of bit manipulation. Some other applications are also interesting to be studied, such as Reverse Backtracking by using Bitmasks, Dynamic Programming with Bitmasks, and more.

I hope this guide can be a good start to understand bit manipulation techniques, or enrich the readers with more knowledge.

Thank you for reading!