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:

// left shift operator:// how many `0` after `1`?const A = 1 << 0; // 00001const B = 1 << 1; // 00010const C = 1 << 2; // 00100const D = 1 << 3; // 01000const E = 1 << 4; // 10000

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:

// & is like boolean &&0 & 0 0 & 1 1 & 0 1 & 1 // | is like boolean ||0 | 0 0 | 1 1 | 0 1 | 1 

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 | B)A       00001 |B       00010 =        00011(A | C)A       00001 |C       00100 =        00101(A | B | D)A       00001 |B       00010 |D       01000 =        01011

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:

(A | B) & A00011 &00001 =00001 (A | C) & B00101 &00010 =00000 (A | B | D) & D;01011 &01000 =01000 (A | B | D) & C;01011 &00100 =00000 // multiple groups inclusion(A | B | D) & (A | C);01011 &00101 =00001 

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.

user.permission = GUEST;if (user.groups.has(developer))  user.permission |= DEVELOPER;

... 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.

// ^ is like a != comparison0 ^ 0 0 ^ 1 1 ^ 0 1 ^ 1 

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

(A | B) ^ A00011 ^00001 =00010 B(A | B | D) ^ D;01011 ^01000 =00011 (A | B)(A | B | D) ^ B;01011 ^00010 =01001 (A | D)// multiple groups removal(A | B | D) ^ (A | D);01011 ^01001 =00010 B

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!

// C was not in the group before(A | B | D) ^ C;01011 ^00100 =01111 (A | B | C | D)

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":

let toggle = 0;// 0 ^ 1 === 1if ((toggle ^= 1))  console.log('true');// 1 ^ 1 === 0if (!(toggle ^= 1))  console.log('false');// 0 ^ 1 === 1if ((toggle ^= 1))  console.log('true');

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:

const A = 1 << 0; // 00001const B = 1 << 1; // 00010const C = 1 << 2; // 00100const D = 1 << 3; // 01000const E = 1 << 4; // 10000

... 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:

const AtoE = (1 << 5) - 1;// 11111AtoE & A;       // AtoE & B;       // AtoE & (A | C); // const F = 1 << 5;// 100000AtoE & 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:

AtoE 0000011111FtoJ 1111100000

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?

// this one groups them allconst AtoJ = (1 << 10) - 1;// 1111111111// and this one subtract AtoE groupconst FtoJ = AtoJ & ~AtoE;// 1111100000

... 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:

( 0 * -1) - 1;  // -1(-1 * -1) - 1;  //  0

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

// decimal basic example11 & ~1;    // 10// always works as expected with binary strings(parseInt('1111', 2) & ~parseInt('11', 2)).toString(2);// 1100

Safer subtracts

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

// C was not in the group before(A | B | D) & ~C;// subtract C from (A | B | D) ?01011 &00100 =00000 // B was in the group(A | B | D) & ~B;// subtract B from (A | B | D) ?01011 &00010 =00010       =01001 (A | D)// multiple subtractions(A | B | D) & ~(A | D);01011 &01001 =01001       =00010 B// subtracts A only(A | B | D) & ~(A | C);01011 &00101 =00001       =01010 (B | D)

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:

(A | B | D) 01011// find:         A  00001         B  00010         D  01000

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:

function* eachValue(group) {  // loop through all multiple of 2 and match  for (let pow = 0, i = 1; i < group; i = 2 ** ++pow) {    if (group & i)      yield i;  }}// given original A, B, C, D, E constantsfor (const value of eachValue(A | B | D))  console.log(value.toString(2).padStart(5, '0'));// A  00001// B  00010// D  01000

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?

AtoE 0000011111FtoJ 1111100000

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:

function* eachValue(values, subgroup = -1) {  // remove all undesired `1` from the list of values  const group = values & subgroup;  // loop through all multiple of 2 and check if these match  for (let pow = 0, i = 1; i < group; i = 2 ** ++pow) {    if (group & i)      yield i;  }}for (const value of eachValue((A | D | F), AtoE))  console.log(value.toString(2).padStart(5, '0'));// A  00001// D  01000

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 introduce >>> too, which is the unsigned right shift operator.

function* eachValue(values, filter = -1) {  let mask = values & filter, bit = 0;  while (mask) {    if (mask & 1)      yield (1 << bit) >>> 0;    mask >>>= 1;    bit++;  }}

Let's break down the "smart loop" that doesn't pow all along:

• 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. Please note that 31 is the maximum possible bit value here, while the previous version would've reached up to 53 without issues
• the mask first bit is then removed, and the bit is incremented

To somehow better visualize what is the logic there:

// 0000101001let mask = (A | D | F);//        // 0000101001 &// 0000000001   Aif (mask & 1);// move all 1 one spot on the right mask >>>= 1;//         // 0000010100 &// 0000000001 if (mask & 1);mask >>>= 1;//         // 0000001010 &// 0000000001 if (mask & 1);mask >>>= 1;//         // 0000000101 &// 0000000001   Dif (mask & 1);mask >>>= 1;//          // 0000000010 &// 0000000001 if (mask & 1);mask >>>= 1;//          // 0000000001 &// 0000000001   Fif (mask & 1);mask >>>= 1;// 0000000000// end of the loop

To close this chapter, it is good to understand workarounds for transpiled code, but it's always a matter of tradeoffs: if you'd like to have more than 31 possible values grouped, 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 literally 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, even if not strictly specified, the resulting number will be positive up to Math.pow(2, 31) - 1.

After that, operations will still work, but produced values will be negative.

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.

(2 ** 32) - 1;// 32bit:  4294967295// 11111111111111111111111111111111(2 ** 31) - 1;// 16bit:  2147483647// 01111111111111111111111111111111-(2 ** 31) + 1;// 16bit: -2147483647// 11111111111111111111111111111111

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

const i32 = new Int32Array(1);i32[0] = (2 ** 31) - 1;i32[0]; // 2147483647// increment by 1, reaching 1 << 31i32[0]++;// now it's negativei32[0]; // -2147483648// that is the exact value of 1 << 31i32[0] === 1 << 31;// true

Not so limited though ...

The real limitation, at least with JavaScript regular integers, is defined by Number.MAX_SAFE_INTEGER, which usually is the equivalent of Math.pow(2, 53) - 1, and produces a long 11111111111111111111111111111111111111111111111111111 string, granting space for 53 different values we can use and group without issues.

This is also the number that will return truthy results with every value except 0, so it's the biggest group of them all unless we use BigInt.

// 53 ... and beyond! 128 possible values hereconst big = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFn;

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
@JWorthe for helping me out polishing, improving, clarifying, and fixing typos all over