About bitwise operations

In 20+ years of programming, I’ve never needed to invert a binary tree except for that one time a silly interviewer asked me to do that for a web-related role. I have, however, encountered bitwise operations in hundreds of real-world situations. Incredibly enough, after the initial learning curve, I’ve never doubted that it was the right solution for these situations.

This post hopes to explain why bitwise operations are one of the best ways to actually reduce complexity and why they are so special!

Think like “strings”, not numbers!

If we try to do decimal math with ones and zeroes, we won’t likely understand bitwise operators or go too far … so let’s start with the basics:

The key take here is that we don’t really need to care about what number those “binary strings” represent, but if you really want to know, you can console.log(A, B, C, D, E) and figure it out, right? 😊

Also, remember, num.toString(2) will always produce the binary string representation, which is handy while exploring this field ... let's start now!

The AND and the OR

The binary math with these two is pretty simple:

As simple as that looks, we can already do amazing things with just these two operators!

Let’s see how grouping works, as an example:

A great feature to consider is that we can put together any combination, without ever caring about the order, so that (A | B | D) is always identical to (B | D | A), and to (D | A | B).

On top of that, we can easily check if a specific char is part of the group, using the & operator, which is true only if there is a 1 at the same position of one of the positions the group covers:

Congratulations, you’ve just learned how most permissions related logic works 🥳

Moreover, if each permission has a mask, adding another permission to a user/group would be an |= operation away.

… and because 101 | 101 will produce again 101, it's always safe to add a permission, without needing to check it was already there.

But how to remove a value from a group?

The XOR

This operator flips to 0 "columns" with the same value, producing 1 in all other cases.

While its nature looks awesome to “rotate0 and 1 around, it also does a good job at dropping values from a group:

⚠ WARNING

As previously mentioned, an OR | operator doesn't need checks upfront to be performed, but an XOR ^ operator requires mandatory checks before a value can be removed from a group because otherwise it adds the value to the group itself!

The rule of thumb with XOR in a nutshell:

  • was it there? it’ll go away
  • wasn’t it there? it’ll be added

Thinking about boolean operations, a unique digit XOR does what a ref = !ref does to a mutable, boolean, reference, and indeed it could be used as "toggle operator":

Ok, Ok, this is way too far already … but I hope we got how powerful, or destructive, could be an XOR ^ in the wild, which is why the tilde NOT operator is usually a better solution, at least to reduce groups.

The all-in case

Back to the first example with the alphabet:

… we’d like to have a special value that would return something different from 0 per each letter of the known alphabet, in this case A to E.

To do so, we need a value that would produce at least a pair of 1 with all those values.

At this point, we might think that the group (A | B | C | D | E) would cover that, and we'd be right!

However, we can also picture the fact we just need a 11111 there, which is exactly what that union of values would produce.

It’s not as high as the const F = 1 << 5, but high enough to cover all values before F:

… and the some-out case …

Let’s imagine we want to split the alphabet into two different A to E and F to J groups, so that instead of checking 5 times, per each group if there is a match, we can quickly branch between these two groups through one of those special grouping values.

Once again, there’s nothing wrong with manually assigning (A | B | C | D | E) and (F | G | H | I | J) to obtain such values, but because this post is about understanding bitwise operations, let's try to picture what we are trying to do here:

See that? We are splitting through segments of 1 and 0 our target sub-groups, but while the (1 << X) - 1 trick works to consider them all, this time we need to subtract one group to another ... and how can we do that?

… wait what?

The tilde ~

This operator, also known as NOT bitwise operator, has different applications:

  • it subtracts 1 to the negative version of the number and return
  • it subtracts known 1 from "binary strings" when combined with an AND &

The former point means that ~0 produces -1, and ~(-1) produces 0 too:

The latter point means that num & ~num is always 0, but biggerNum & ~smallerNum subtracts smallerNum from biggerNum.

Safer subtracts

Different from XOR ^, the tilde ~ operator doesn't add a group if it wasn't already present.

Got it? The & followed by NOT ~ returns the initial value minus the parts of both values that match, effectively removing any undesired 1 present on the right-hand side.

Destructuring a group

We have already seen how to group, how to check if a group, or a value, is part of a group, how to remove a specific value or subgroup, but we haven’t seen how to destructure values from a group.

By “destructuring” here, I mean a way to retrieve all subvalues of a group:

If we look closer, finding all 1 in that group is like looping from right to left all 1 and see if there is a match:

Because the loop is linear, it doesn’t matter how the group was created, the order of the returned values will be always from smaller to bigger.

I’ll leave it as a reader’s exercise to figure out how to extract bigger to smaller values, whenever it matters 👍

Destructuring a subgroup

Remember these two parts of the alphabet we wanted to group?

Now, let’s imagine we’d like to destructure only one of the two subgroups, ignoring values that don’t belong to other groups.

To do so, the very first thing we should do is to remove all undesired 1 from the given input. Let's see an example:

Passing FtoJ as a subgroup instead would've logged only F with a value of 100000.

Why subgroup -1 as default?

The -1 number is the equivalent of the tilde ~0 (NOT zero).

Because ~0 in turn means any 1, we can use it as a default value, so that every 1 found would stay.

Accordingly, if you see a signature such as function* fn(some, dflt = ~0) it's likely a utility to deal with bitwise operations.

A note about possible optimizations

Because many consider bitwise operators a must use when performance matters, even if I hope it’s clear by now these can be very convenient regardless, developers might invent any sort of indirection to basically obtain the same result, bypassing, for example, Math.pow(...) calls, when these are not necessary.

To be honest, if the code is not transpiled into API calls, operations such as 2 ** X should be pretty damn fast these days. However, because we never know who's gonna run our code, and how, we could also use a different approach to solve the previous problem, taking the opportunity to better introduce >>> too, which is the unsigned right shift operator, and it covers twice Int32, being Uint32.

Let’s break down the “smart loop” that doesn’t pow all along:

  • the mask is granted to be a positive number up to Math.pow(2, 32) - 1
  • as long as mask is not 0, the loop keeps going
  • if the very first mask bit is truthy, or better, just 1, the value with the related power of 2 is returned, ensuring that if bit is exactly 31, its sign is dropped, so it's always positive.
  • the mask first right bit is then removed, and the bit value is incremented. Please note: as mask is granted to be positive, >>=1 would have likely worked equally well in this case.

To somehow better visualize what is the logic there:

To close this chapter, it is good to understand workarounds for transpiled code, but it’s always a matter of tradeoffs: it is safe, and I believe reasonably equally fast, to use the power ** operator, or even Math.pow, but in every other case, it's possible to move everything to the right, until we reach 0.

Other benefits around bitwise operations

  • these are extremely fast to compute with every programming language
  • every C like programming language handles non-zero integers as truthy, so these are super handy in conditional flows
  • there is literally nothing smaller, simpler, or faster when it comes to grouping, and sub-grouping, domain specific values
  • it is very difficult to get these wrong, once these are fully grasped, including the XOR operator

In depth: the left shift operator

The left shift operator, with a single 1 digit to move toward the left, is like Math.pow(2, X), where X is the number on the right, as in 1 << X.

Bear in mind that the resulting number will be positive up to 1 << 30, but 1 << 31 will reach the Int32 positive edge, becoming a negative value.

The explanation is that these operators were born in 32bit based systems, where a signed integer reserves the first bit to indicate if positive or negative.

To be even more precise, let’s use typed values:

Because we want to be sure we can use all 32 positions, the unsigned right shift operator would “cast(1 << 31) >>> 0 as Uint32, giving us the possibility to use all available positions.

Not so limited though …

Even if Number.MAX_SAFE_INTEGER defines the top positive boundary where normal aritmetic operations shouldn't fail, we need to use BigInt if we'd like to have more than 32 possible values.

Conclusions

I consider this topic as important as knowing Regular Expression, for the simple reason that in most cases, bitwise operations are the best tool for the job, when it comes to groups and values, and so are RegExp when it comes to non streamed strings parsing.

What I’ve also tried to emphasize and stress is that once we think in segments of a string composed by 0 and 1, instead of the represented decimal numbers, and we associate a specific meaning to the various operators, things should naturally become clearer for most developers, and less scary to read, implement, or deal with.

In few words, I hope you enjoyed this read and learned something new and useful 👋

Credits

A very special thanks goes to my awesome peers @goatonabicycle and @JWorthe for helping me out polishing, improving, clarifying, and fixing typos all over ♥

Web, Mobile, IoT, and all JS things since 00's. Formerly JS engineer at @nokia, @facebook, @twitter.