Bitwise Operators in JavaScript

Bitwise Operators are rarely used in JavaScript whereas you would commonly see it being in used in languages like Objective-C or Java. Do other languages just have more resource constraints or have problems that need hyper performance more? That’s not really what I’m here to talk about, this is more of a fun blog on what Bitwise Operators can do in your JavaScript application.

Crash Course #

Here is a short recap of your CS 101 class on Bitwise Operators:

Applications #

Bitwise AND ( & ) #

Bitwise OR ( | ) #

Bitwise XOR ( ^ ) # 

a ^= b, b ^=a, a ^= b;

Bitwise NOT ( ~ ) #

Shift operators ( >> and <<) # 

const dec = parseInt(HEX, 16);

const RGB = {};
RGB.r = (dec >> 16) & 0xFF;
RGB.g = (dec >> 8) & 0xFF;
RGB.b = (dec) & 0xFF;

const HEX = ('#' + (1 << 24) + (RGB.r << 16) + (RGB.g << 8) + RGB.b).toString(16).substr(1);

Zero-filling Shift Operators ( >>> and <<< ) #

Applications When Mixed Together #

Finding the smaller (or larger) of two integers # 
const x = 7;
const y = 31;

const smaller = y ^ ((x ^ y) & -(x < y));

console.log(smaller); // 7

or the larger …

const x = 7;
const y = 31;

const larger = x ^ ((x ^ y) & -(x < y));

console.log(larger); // 31
Bit Mask Config #

Rather than having a separate boolean parameter for each case and having a cascading if/else statements (as well as existence checking), a bitmask configuration is an option. A bitmask is a sequence of bits that can manipulate and/or read flags. Each placement of a bit represents a configuration of either true or false (1 or 0). A layman way of explaining this is represented by how 2 which is 0010 is different from 1 which is 0001 but not 3 which is 0011 since they share the same 2nd to last placement.

const flags = 5; // 0101 from config

const FLAG_A = 1; // 0001
const FLAG_B = 2; // 0010
const FLAG_C = 4; // 0100
const FLAG_D = 8; // 1000

// If we own a Boggart or Chimaera
const mask = FLAG_B | FLAG_C; // 0010 | 0100 => 0110

if (flags & mask) { // 0101 & 0110 => 0100 => true
  // The same thing as (flags & FLAG_B) || (flags & FLAG_C)
  // Take care of magical beasts (Boggart or Chimaera)
}

if (flags & ~mask) {
  // ~mask equals ~(0110) = 1001
  // Essentially an else since we flipped the mask
}

Adapted source

As you can see bitmask can be very powerful by making configuration requirements into compact statements. There are also plenty of options in automating the creation of the flags configuration such as using arguments or an actual array.

Other uses for masks are also: error flags, permission flags, etc.

Automated Bitmask Config from Arguments #

If we wanted to make use of bitmasks for configurations, we need to find an efficient way to manage configurations, here is a method that handles the creation of the bitmask.

The first argument acts as the first placement i.e. 2^0 for the bitmask.

The nth argument acts as the nth placement i.e. 2^(n - 1) since we start at 0.

function createBitMask(...states) {
  // Overflows at 32-bits and wraps around
  const len = (states.length > 32) ? 32 : states.length;

  const mask = states.reduce((mask, state, index) => {
    return mask |= state << index;
  }, 0);

  return mask;
}

createBitMask(false, true, false, true); // 10 === 1010
createBitMask(true, true, true); // 7 === 0111
createBitMask(false, true); // 2 === 0010
createBitMask(true); // 1 === 0001
Bit/Byte-Based Data Structures #

Using bits (or bytes) instead of types that take on more memory such as Strings, Objects, or what not, allows us to be able to search, sort, and store data more efficiently. Imagine a bit/byte-based data structure versus a traditional one with respect to sorting Integers, the byte array would allow us to implement Bucket Sort with little memory consumption.

Bucket sort works as follows:

  1. Set up an array of initially empty “buckets”.
  2. Scatter: Go over the original array, putting each object in its bucket.
  3. Sort each non-empty bucket.
  4. Gather: Visit the buckets in order and put all elements back into the original array.
Encoding Decoding #

Not to go in deep into security topics, but encoding and decoding algorithms use bitwise operations. See Base64 encoding and decoding. Or MD5 algorithm.

Hash Code Calculation #

When using a custom hash function for cases such as memoization, bitwise operators would be useful to generate the unique hash key from the parameters provided with little computational time (you’re using memoize so we know you need every little millisecond!).

Use Case for xor #

xor is quite useful in situations where you want to check if one of the two configurations (a or b) are active but not neither nor both. For reference, a XOR b results are displayed as the following:

a b a XOR b
0 0 0
0 1 1
1 0 1
1 1 0

With bitwise operations …

const RAVENCLAW = true;
const GRYFFINDOR = false;

if (RAVENCLAW ^ GRYFFINDOR) {
  // Either is RAVENCLAW or GRYFFINDOR but not both
} else {
  // Neither RAVENCLAW nor GRYFFINDOR and not both
}

Without bitwise operations …

if ((RAVENCLAW || GRYFFINDOR) && RAVENCLAW !== GRYFFINDOR) {
  // Either is RAVENCLAW or GRYFFINDOR but not both
} else {
  // Neither RAVENCLAW nor GRYFFINDOR and not both
}

TLDR #

Bit operators add complexity and less readability to your code in exchange for faster processing speed and less memory taken. However does the increase in performance warrant the technical debt bit operators produce? Right tools for the job is always the default answer but just as es2015 is here to stay, so too would very efficient javascript application use cases such as trading or medical scenarios. But on the other hand, so too does more powerful JIT compilers become standard to optimize your code possibly negating the benefits.

 
56
Kudos
 
56
Kudos

Now read this

Collatz Conjecture

In this blog post we deviate a little from the ES6 parade I’ve been writing here. We dive into the Collatz Conjecture (otherwise known as the 3n + 1 conjecture) on today’s blog. The Collatz conjecture is the simplest open problem in... Continue →