Happy new year! A lot of things have been set in motion since my recent announcement, so I’ll focus on a shorter guide this week, which will nonetheless be very interesting if you’ve always wondered what bitwise operators could be useful for.
Imagine you’re working with a recursive data structure that can be broken down until an atomic level is reached. The concrete data structure doesn’t really matter for the outcome of this guide, so I’ll just go for a tree.
Let’s say we’re trying to assign identifiers for each node, and we want to store information about the hierarchy and orientation of the node. We expect nodes to be primary or secondary, and we want to annotate this in the identifier.
There are many ways to solve this issue, but we’ll focus on saving space and doing some clever bitwise arithmetics to store exactly what we need: the level (height) and primary/secondary flag. To store our flag, we’ll use an integer, but we don’t really care about the decimal representation here, only the fact that with a standard integer in C, we get 4 bytes of storage, which translates to 32 bits of information we can use for our mask.
To understand exactly how the mask should work, let’s look at some examples.
Bit flags all the way down
For the root level, where no orientation exists, we always mark our node as primary, the value will be
1[000 0000 0000 0000 0000 0000 0000 0000]
If we go a level deeper, we will have a primary and secondary node. Their respective identifiers will be
primary: 11[00 0000 0000 0000 0000 0000 0000 0000]
secondary: 01[00 0000 0000 0000 0000 0000 0000 0000]
We can go a level further! If we split up the primary node once more, we’ll have
primary: 111[0 0000 0000 0000 0000 0000 0000 0000]
secondary: 011[0 0000 0000 0000 0000 0000 0000 0000]
As you can see, for every new level in our tree, we “push” our primary/secondary flag to the most significant bit. You could almost think of the identifier as a stack of flags.
If we needed to compute the sibling’s identifier for any node, we could simply XOR the most significant bit:
node x: 111
sibling of x: 011
This way, not only do we store the orientation (primary/secondary), but we can also efficiently retrieve the sibling identifier.
Keeping this in mind, we can dive into the implementation. As I recently needed this solution, it’s written in C, but you can probably port the code to any other language with minimal effort (hint: sizeof(int) evaluates to 4).
Creating an initial (root) mask
For our root mask, we expect a value of 1 followed by all 0s. An easy way to get there is by performing a left shift of 1 by size - 1 positions.
int initial_mask() {
// return most significant bit 1 and the rest 0
return 1 << (sizeof(int) * 8 - 1);
}
Let’s look at this in more detail.
i = 1 // remember that 31 zeroes lead up to the 1
i << 1 // [30 zeroes]10
i << 2 // [29 zeroes]100
i << 3 // [28 zeroes]1000
...
i << 31 // 1[31 zeroes]
Pretty neat, huh? Bitwise operators aren’t all scary once you start thinking in bits.
Going a level deeper
Whenever we want to split a mask into two children, we need to shift our current value to the right and append either a 1 for the primary child or a 0 for the secondary child.
int split_mask(int mask) {
// shift the mask to the right and add 1 as the most significant bit
return (mask >> 1) | (1 << (sizeof(int) * 8 - 1));
}
Our split_mask function will always return the identifier for our primary child. Let’s examine how it works under the hood:
mask = 101[29 zeroes]
// step 1: shift mask 1 to the right
(mask >> 1) // 0101
// step 2: set most significant bit to 1
0101 | (1 << (sizeof(int) * 8 - 1)) // 1101
// evaluates to
0101[28 zeroes] | 1000[28 zeroes]
The bitwise or returns a 1 in each bit position for which the corresponding bit of either or both operands are 1s. Because we set the right sight to all zeroes except for the most significant bit, we force the result to start with 1 but don’t perform any other changes to the left side (as x OR 0 will always return x, no matter 1 or 0).
Who’s my buddy?
int sibling_mask(int mask) {
// xor most significant bit with 1
return mask ^ (1 << (sizeof(int) * 8 - 1));
}
First, let’s start with converting an identifier mask to the sibling identifier. As we said previously, we want to XOR the most significant bit (and only the most significant bit).
mask = 101
101[29 zeroes] XOR 100[29 zeroes]
// remember: 1 XOR 0 = 1 and 0 XOR 0 = 0
101 XOR 100 = 001
Here, we use the fact that x XOR 1 flips x while leaving any other bit untouched, as the right-hand value will always be zero.
Next, we can write a helper method to detect if a mask is a sibling mask, helping to understand the orientation of a node.
int is_sibling_mask(int mask) {
// if most significant bit is 0 then it is a sibling
return (mask & (1 << (sizeof(int) * 8 - 1))) == 0;
}
Once again, we can follow the bitwise operations to understand why the function works the way it does. The bitwise AND operator returns a 1 in each bit position for which the corresponding bits of both operands are 1s.
// remember: 1 & 1 = 1, anything else is 0
mask = 001
001 & 100 = 000 => 000 == 0
mask = 101
101 & 100 = 100 => 100 != 0
This way, we can detect if a mask identifies a sibling node, but not whether it’s a sibling of a given node. For that, we can simply compare the result of our conversion function for a given node mask with a given sibling mask.
int is_sibling(int mask, int siblingMask) {
// if the mask is a sibling of the siblingMask
return siblingMask == sibling_mask(mask);
}
To be a sibling mask, it has to match the result of the conversion function.
Going back up
int merge_mask(int mask) {
// shift mask to left
return mask << 1;
}
After doing our work on a given level, we may want to walk up the tree again, or merge two nodes. For this, we can perform a single left shift to get the parent identifier. Nodes with the same parent identifier are also siblings, by the way.
mask = 101
101 << 1 // 01[30 zeroes]
That’s it! It wasn’t all that difficult, right? Bitwise operations tend to look scary, but in the end, for arithmetics, it’s just a fancy way of dividing or multiplying by 2. For our use case, we wanted a stack-like representation of two flags respecting the height of a tree, and 32 layers were plenty. In case you need to support a greater depth, go for a bigger data type (e.g. int64).