shifting the bits

July 14, 2019

a couple reasons to use (or not use) bit manipulation in JavaScript

This is not a complete explanation of all binary operations in JavaScript, you can find a multitude of examples on the internet, or specifically in these articles by Joshua Parker or Lucas F. Costa .

counting frequency in array

When a problem requires you count the frequency of elements in a collection, using the XOR operand may provide cleaner code and performance gains.

Single Number

The Single Number problem on LeetCode is an excellent example where using bit manipulation may result in more readable code.

My naive solution to this problem used a set, as every element except the target element occurs twice, each element is added to the set, then removed when encountered a second time. At the end of the loop, there should only be one value left in the set. You could also memoize an object in a similar way, measuring frequencies without deletion.

const singleNumber = function(nums) {
  const set = new Set()

  for (let i = 0; i < nums.length; i++) {
    if (!set.has(nums[i])) {
      set.add(nums[i])
    } else if (set.has(nums[i])) {
      set.delete(nums[i])
    }
  }

  return set.values().next().value
}

While the previous solution is accepted, the problem’s note states “Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?”, making me reconsider this solution because a set will likely use a linear amount of memory.

Once I researched a little bit about the XOR operator, I was able to come up with this solution, which I think is cleaner and easier to understand.

const singleNumber = function(nums) {
  let num = 0

  for (let i = 0; i < nums.length; i++) {
    num ^= nums[i]
  }

  return num
}

This solution works because of the XOR property 0 ^ A = A && A ^ A = 0. Everytime an element is encountered twice, it’s value will be eliminated from the num integer, leaving the remaining value at the end of loop as whichever element only occured once. Memory-wise, the first solution required a linear capacity, whereas this solution requires the creation of only one 32-bit integer. Lastly, the only operation used, num ^= nums[i], is going to be substantially faster than using using the .has(), .add(), and .delete() methods of a set.

Try to use the same concepts to design an answer for Single Number II, think about accumulating frequencies of particular bits in a 32-bit integer and comparing it to the target frequency.

iterated arithmetic

If you develop an application that does many iterative mathematical operations, there may be some specific ways of manipulating bits to achieve faster processing times as well as cleaner code. Bit shifting will provide performance gains when you need to multiply or divide numbers by a simple factor like 2. The following code shows the equivalence between Math.floor(x/(2**n)) and x >> n .

const x = 17 // integer to divide
let n = 1 // exponent or shifting number -> 'n'

let floored = Math.floor(x / Math.pow(2, n)) // 8
let shifted = x >> n // 8

n = 2

floored = Math.floor(x / Math.pow(2, n)) // 4
shifted = x >> n // 4

The opposite property exists for multiplying a number by 2**n through the expression x << n

const x = 4 // integer to multiply
let n = 1 // exponent or shifting number -> 'n'

let multiplied = x * Math.pow(2, n) // 8
let shifted = x << n // 8

n = 2

multiplied = x * Math.pow(2, n) // 16
shifted = x << n // 16

Now that equivalence has been established, let’s check out the performance differences of the first example in a high volume setting.

The performance differences are not as stark as the Sets v. Bits example, but apparent nonetheless, with bit shifting able to produce about 3 million more operations per second than Math.floor() . If a developer is aware of bit manipulation syntax in JavaScript, it could be argued that bit shifting will produce more readable code, but as with performance, some may see the gain as neglible.

wrap up

These two examples are only a subset of the possibilities of achieving performance gains and cleaner code using bit manipulation in JavaScript. The reality is that JavaScript was never meant to be a low level language, so the knowledge and use of these techniques is not of great importance to the general JavaScript developer. Bit manipulation could be quite impressive to employ during an interview and it could be a good introduction for ordinary JavaScript developers to some of the concepts used in lower level languages like C++, as it was for me. What is most important is identifying which scenarios would benefit from the application of bit manipulation, like measuring frequency of elements or iterative mathematical operations, and employing them only when they make your application faster and/or more readable.

Sam Parsons is currently a Software Engineer at Codesmith. He is also a contributor to Swell, an API development tool for streaming technologies (HTTP2, WS, SSE).

beyond logging →