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; // 00001
const B = 1 << 1; // 00010
const C = 1 << 2; // 00100
const D = 1 << 3; // 01000
const 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) & A

00011 &
00001 =
00001 ✔


(A | C) & B

00101 &
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 != comparison
0 ^ 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) ^ A

00011 ^
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 === 1
if ((toggle ^= 1))
  console.log('true');

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

// 0 ^ 1 === 1
if ((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; // 00001
const B = 1 << 1; // 00010
const C = 1 << 2; // 00100
const D = 1 << 3; // 01000
const 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;
// 11111

AtoE & A;       // ✔
AtoE & B;       // ✔
AtoE & (A | C); // ✔


const F = 1 << 5;
// 100000

AtoE & 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 0000011111
FtoJ 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 all
const AtoJ = (1 << 10) - 1;
// 1111111111


// and this one subtract AtoE group
const 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 example
11 & ~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 constants
for (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 0000011111
FtoJ 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
  // ensure positive number up to (2 ** 32) - 1
  const group = (values & subgroup) >>> 0;
  // 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 better introduce >>> too, which is the unsigned right shift operator, and it covers twice Int32, being Uint32.

function* eachValue(values, filter = ~0) {
  let mask = (values & filter) >>> 0, 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:

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

// 0000101001
let mask = (A | D | F);

//     ↓ ↓  ↓
// 0000101001 &
// 0000000001 ✔  A
if (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 ✔  D
if (mask & 1);

mask >>>= 1;

//         ↓ 
// 0000000010 &
// 0000000001 ✖
if (mask & 1);

mask >>>= 1;

//          ↓
// 0000000001 &
// 0000000001 ✔  F
if (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: 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

About ES6 / ES2015 support

It is definitively worth mentioning that modern browsers understand 0b0001 like syntax, up to 0b10000000000000000000000000000000, the equivalent of (1 << 31) >>> 0, so that playing around the 32 bit boundaries should help, similarly as thinking "binary strings" helps too, except it's supported right away 👍

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.

(2 ** 32) - 1;
// 11111111111111111111111111111111
// as 32bit:  4294967295

(2 ** 31) - 1;
// 01111111111111111111111111111111
// ↑ as 16bit => 2147483647

(2 ** 31);
// 10000000000000000000000000000000
// ↑ as 16bit => -2147483648

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 << 31
i32[0]++;

// now it's negative
i32[0]; // -2147483648

// that is the exact value of 1 << 31
i32[0] === 1 << 31;
// true

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.

for (let bit = 0; bit < 32; bit++)
  console.log(((1 << bit) >>> 0).toString(2).padStart(32, '0'));
  // 00000000000000000000000000000001
  // to
  // 10000000000000000000000000000000

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.

// Beyond 32 values: 128 possible values example
const big = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFn;

big & 0xFn; // truthy

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 ♥

Comments

[peerreynders]

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

Only once the for condition is fixed to check for i <= group instead.
Also const group = (values & subgroup) >>> 0; is needed — otherwise bit 31 won't be recognized.

taking the opportunity to introduce >>> too, which is the unsigned right shift operator.

Given the context I think n >>> 0 needs an introduction as well, i.e. in general bitwise operators yield Int32 — however >>> yields a Uint32 (hence the name; Alternate implementations of ToUint32 and ToInt32).

Please note that 31 is the maximum possible bit value here, while the previous version would've reached up to 53 without issues.

Given that the previous version uses group & i it's just as bound to the 32 bit limit. That said the limit can be widened to 53 bits without resorting to BigInt.

const HIGH_BASE = 0x1_0000_0000;
const HIGH_SHIFT = [(value) => value, (value) => value * HIGH_BASE];

function* eachValue(values, queryMask = Number.MAX_SAFE_INTEGER) {
  const maskSplit = splitLowHigh(queryMask);
  const valuesSplit = splitLowHigh(values);

  for (let n = 0; n < HIGH_SHIFT.length; n += 1)
    for (
      let i = 0,
        field = toUint32(valuesSplit[n] & maskSplit[n]),
        shift = HIGH_SHIFT[n];
      field > 0;
      i += 1, field >>>= 1
    )
      if (field & 1) yield shift((1 << i) >>> 0);
}

function splitLowHigh(value) {
  const low = value % HIGH_BASE;
  return [low, (value - low) / HIGH_BASE];
}

function toUint32(value) {
  return value >>> 0;
}

const KEY_BASE = 'A'.charCodeAt(0);
const KEY_INTERVAL = 26;
const c = prepareRecord();

const AtoE = 0b1_1111;

for (const value of eachValue(c.A | c.D | c.F, AtoE))
  console.log(value.toString(2).padStart(5, '0'));

// 00001
// 01000

for (const value of eachValue(c.AF + c.AG + c.BA, Number.MAX_SAFE_INTEGER))
  console.log(value.toString(16).padStart(14, '0'));

// 00000080000000
// 00000100000000
// 10000000000000

function prepareRecord() {
  const FIELD_END = [32, 53];
  const record = {};
  let i = 0;
  for (let n = 0; n < HIGH_SHIFT.length; n += 1)
    for (
      let value = 1, endIndex = FIELD_END[n], shift = HIGH_SHIFT[n];
      i < endIndex;
      value = toUint32(value << 1), i += 1
    )
      record[indexToKey(i)] = shift(value);

  return record;
}

function indexToKey(i) {
  let key = '';
  do {
    const r = i % KEY_INTERVAL;
    key = String.fromCharCode(KEY_BASE + r) + key;
    i = (i - r) / KEY_INTERVAL - 1;
  } while (i > -1);

  return key;
}

[Andrea Giammarchi]

Awesome review, thank you! I have addressed pretty much all your points but I won't go down the 1 << 31 and beyond rabbit hole, although you are right the post was misleading, and I actually had to (2 ** 31) & 1 to indeed realize that all operations are broken regardless the fact the integer is theoretically safe, as Number.MAX_SAFE_NUMBER would suggest. I guess I would've learned it the hard way once added more values to some code I'm working on, so apologies for that misleading bit, now removed, and thanks again for the hints 👍