A Real Life Application for Bit Math

Disclaimer: I wrote this a few years ago for personal use but figured I would publish it. No guarantees on accuracy or readability. I use medium as a notebook for referencing later

I recently came across some code in my work that utilized bit math.

Often times we find ourselves in the situation where we need to check if a value is contained inside a list or collection. Something like the following:

function doesContainItem(list, item) {
  for testItem in list {
    if (testItem == item) {
      return true
    }
  }
  return false
}

This is great, but it is an O(n) operation where n is the length of list. In other words , it could be faster. Let me show you how.

Let’s start by laying out the foundation. First remember that unsigned integer values are stored as 1’s and 0’s in memory. So the value 3 is stored as the following in a 32-bit system

00000000000000000000000000000011 // integer 3

In a 64-bit system there are 64 places instead of 32, but for the sake of simplicity, going forward I will imagine we have an 8-bit system so memory can store 8 bits. Some examples below.

00000001  // 8-bit integer 1
00000010  // 8-bit integer 2
00000011  // 8-bit integer 3
00000100  // 8-bit integer 4
00000101  // 8-bit integer 5
00001000  // 8-bit integer 8
00010000  // 8-bit integer 16

Now imagine that we have some enumerations defined in our code. For example some colors. There are 8 different values, if we assign them integer values that are powers of 2 something cool happens:

const black = 1    // 00000001 in memory
const red = 2      // 00000010 in memory
const orange = 4   // 00000100 in memory
const yellow = 8   // 00001000 in memory
const green = 16   // 00010000 in memory
const indigo = 32  // 00100000 in memory
const violet = 64  // 10000000 in memory

As you can see, each const has a single bit set to 1. Each bit position in memory starts to act like a flag for that color. The first position is violet, the second position indigo, etc.

Now I would like to introduce the bitwise OR operator |. The bitwise OR operator compares the bit values of two items in memory. In this case, it checks if any bit is 1 and if so, will return 1 for that bit position. Look at the example below:

const blackWithRed = black|red // bit OR operation
00000001 // black memory value
00000010 // red memory value
-------- // bit OR operation
00000011 // blackWithRed memory value

Next I’d like to introduce the bitwise AND operator &. The bitwise AND operator checks if all bits are 1 and if so returns a 1 for that bit position.

const myVariable = 3 & 1
00000011 // integer 3 memory value
00000001 // integer 1 memory value
-------- // bit AND operation
00000001 // myVariable memory value

Now let’s come back to our problem, imagine we want to check if a color is part of the rainbow. We could do it like this:

const rainbow = [ red, orange, yellow, green, indigo, violet ]
// O(n) complexity
function isPartOfRainbow (rainbow, color) {
 return doesContainItem(rainbow, color) 
}
// O(n) complexity

But now that we understand how to use the bitwise OR and AND operators lets do that instead:

const rainbowBitMask = red|orange|yellow|green|blue|indigo|violet
// bit AND operation
// O(n) complexity
function isPartOfBitMaskRainbow(rainbowBitMask, color) {
  const maskBitAndColor = rainbowBitMask & color // bit AND operation
  return maskBitAndColor > 0
}
// O(1) complexity

Let’s break this down and look at whats happening under the hood. To see how we achieved such a remarkable improvement.

First let’s check the rainbowBitMask. Remember the OR operator checks if any of the bits represented in each item contains a 1

const rainbowBitMask = red|orange|yellow|green|blue|indigo|violet
// O(n) complexity
00000010  // red memory value
00000100  // orange memory value
00001000  // yellow memory value
00010000  // green memory value
00100000  // blue memory value
01000000  // indigo memory value
10000000  // violet memory value
--------
11111110  // rainbowBitMask

Now lets look at the function

const isPartOfRainbow = isPartOfBitMaskRainbow(rainbowBitMask, orange)
function isPartOfBitMaskRainbow(rainbowBitMask, color) {
  const maskBitAndColor = rainbowBitMask & color
  
  11111110 // rainbowBitMask
  00000100 // orange
  -------- // bit AND operation
  00000100 // maskBitAndColor memory value is now equal to integer 8
  
  return maskBitAndColor > 0
  // 8 > 0 is true
}
// O(1) complexity