Bitwise Operators

Yonatan Kra
Dec 22, 2018 · 7 min read

This is a guest post by Yonatan Kra from WalkMe. This post was originally posted in the WalkMe Engineering blog.

Image for post
Image for post

Bitwise operators are frequently used by the pros, usually for memory-related performance boosts. What are they, when should you use them, and how do they impact performance? Stay tuned for answers to all of this and more!

This subject irked me for a long time. I saw it. I heard about it. I even used it without fully understanding it (at least at first). It can certainly be confusing for newbies (heck — it was confusing for me when I already had 10 years’ experience).

I believe we are only confused by concepts we’ve learned if they’re taught to us poorly. So, in the name of dispelling confusion, here’s my attempt at effectively explaining the bit only wise people can see.

This article assumes that you know what binary numbers are and how to read them. If not, you might want to read this before proceeding.

The Bits and Pieces

  1. Menu open: Should I show the side menu?
  2. List focused: Should I highlight the list component?
  3. Request ongoing: Should I show the progress circle?
  4. Process X running: Should I show the process X running sign?

And let’s further image these flags’ current individual states are as follows:

  1. 0 (false)
  2. 0 (false)
  3. 1 (true)
  4. 0 (false)

So… you can represent your app’s state as follows: 0010 (see image below):

Image for post
Image for post

These 0s and 1s are our bits. Each bit is binary, which means that every bit has two states: 1 and 0.

This binary sequence (0010) can be converted into decimal (the intuitive way we humans look at numbers (i.e., 1, 2, 3, 4, etc.)). In JavaScript, we can convert between the two representations easily.

From binary to decimal:

parseInt(“0010”, 2); // results in “2”

And from decimal to binary:

const x = 2; x.toString(2); // results in “10”

That means that every binary sequence (or each of your app’s binary state sequences) can be represented as a single integer!!!

How about that? Can you think of any implications this might have for your app?

Image for post
Image for post

Just sayin’…

The Meaning of Nothing

000000000000000000000000010 = 10

This concludes the philosophical portion of this article.

Signed Integers

32 bits means the number is represented by, well, 32 bits.

00000000000000000000000001100000 //96

If the left-most bit signifies the sign of the number (i.e., 96 vs -96), then the left-most bit is called the sign bit.

This 32 bit, signed binary format is called the two’s complement format. In this format, a number’s negative counterpart is the reverse of all bits in the number (one’s complement) plus one. So, noting the 32-bit representation of 96 above, -96 would be calculated like this, in two steps:

11111111111111111111111110011111 // -97 -> one’s complement

+ 1

11111111111111111111111110100000 // -96 -> two’s complement

The reason for using two’s complement is out of the scope of this article, but is explained here.

Bitwise Shift Operators

Bitwise Left Shift (<<)

Let’s see an example.

1 << 0 = “1” = 1

1 << 1 = “10” = 2

1 << 2 = “100” = 4

Here’s an example showing this concept in action:

The number five is represented by three bits: 101. Recall the sign bit rule: If we have a signed bit of 0, our number is positive. If it is 1, our number is negative. Recall that five can be written like this:

00000000000000000000000000000101

If we choose to do so, our signed (left-most) bit is zero.

If you shift this number 27 bits to the left (5 << 27), 27 zeros are added to the right of the 101, doubling the decimal value with each zero. Since the number started with three bits, adding 27 zeros on the right means we now have 30 bits including and to the right of 101.

01010000000000000000000000000000

That still leaves us positive, since our left-most bit is still 0.

Left shifting five for 28 bits (5 << 28) gives us a total of 31 bits to the right. Still positive.

However, if we left shift five by 29 bits (5 << 29), we will reach 32 bits, and the left-most bit will be 1. Finally, our number is negative!

Image for post
Image for post
Left shifting the number 5

I’ve built this simple tool. With it, you can enter a number and see its left-shifted values up to a maximum of 32 shifts. Notice that the bigger the number, the sooner there are negative values; this is because, once any 1 in the binary number is pushed to the left-most (32nd) bit, it becomes the signed bit and flips the number’s sign to negative.

Still confused? You can play around some more with the online tool here.

Bitwise Right Shift (>>> and >>)

Zero-fill does the same as left shift, only it adds the zeros from the left (pushing to the right). This can result in a sign change if our number is negative (since it will change the sign bit). You can use it as follows:

5000 >>> 3 //625
-5000 >>> 3 //536870287

Sign-preserving adds a copy of the left-most bit — hence preserving the the sign bit. You can use it like this:

5000 >> 3 //625
-5000 >> 3 //-625

You can see it in action with this tool.

The Bitwise Logic Operators

1. Bitwise AND (&)

5 & 13 // output is 5

What’s happening behind the scenes is well-represented by this algorithm.

Holla!

2. Bitwise OR (|)

5 | 13 // output is 13

And here’s an algorithm!

Why do I spoil you so?…

3. Bitwise XOR (^)

XOR (^) returns 1 every time only one of the bits in a pair is 1, but 0 when the bits are the same. So 0/0 returns 0, 1/1 returns 0 but 1/0 and 0/1 return 1. It is used like this:

5 ^ 13 // output is 8

Implementing the XOR is your homework. It’s the same algorithm — with different validation.

You can verify your results via the browser’s console (using the parseInt and toString(2) methods to verify your answer). You can also debug using a binary calculator like this one.

4. NOT (~)

~ 16 // output is -17

The algorithm is simple to implement. In decimals, it would look like this:

-(x + 1)

Parting Thoughts

While I’m sure you’re super eager to try out what you’ve learned, in most cases it’s a best practice to avoid using bitwise operators for readability’s sake. However, in performance-sensitive operations (especially in games or other rendering engines like Angular), bitwise operators may be just the ticket.

Bitwise operators are widely used in graphics-rendering (gaming anyone?) but not just. There are plenty more use cases as well; flags, compression, and encryption are among the most common use-cases of bitwise operators.

In my upcoming articles, I will show you real world use-cases in JavaScript, as well as their performance implications.

WarsawJS

We talk about JavaScript. Every month in Warsaw, Poland.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store