This is a guest post by Yonatan Kra from WalkMe. This post was originally posted in the WalkMe Engineering blog.
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
Imagine you have an app (go ahead… I’ll wait) with several boolean flags that declare the state of your app. For instance, here is a list of some of these hypothetical flags and what they might mean:
- Menu open: Should I show the side menu?
- List focused: Should I highlight the list component?
- Request ongoing: Should I show the progress circle?
- Process X running: Should I show the process X running sign?
And let’s further image these flags’ current individual states are as follows:
- 0 (false)
- 0 (false)
- 1 (true)
- 0 (false)
So… you can represent your app’s state as follows: 0010 (see image below):
These 0s and 1s are our bits. Each bit is binary, which means that every bit has two states: 1 and 0.
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?
The Meaning of Nothing
Did you notice that when I converted 0010 to binary, the result was 2, but when I converted 2 back to binary, the result was only 10? This happens because leading zeros are meaningless; they add no information and hence are not needed. Here’s why:
000000000000000000000000010 = 10
This concludes the philosophical portion of this article.
You may have heard this phrase (or a fuller version like “32/64-bit signed integers”) before. The bitwise operators work with 32-bit signed integers. They actually convert the integers you supply as input (more on that later) to 32-bit signed integers. Let’s discuss what a signed integer is, beginning with signed 32-bit integers:
32 bits means the number is represented by, well, 32 bits.
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
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 shift operators are just what their name implies — they shift the bits either to the left or the right.
Bitwise Left Shift (<<)
Adds zeros from the right. This means the number is doubled with every shift, until we reach the 32 bit boundary. Then, we start using our knowledge regarding the sign bit.
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:
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.
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!
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 >>)
We have two types of right shifts: Zero-fill (>>>) and sign-preserving (>>).
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
Now that we know what bits are and how to manipulate them, we can move on to bitwise logic operators. There are four bitwise logic operators:
1. Bitwise AND (&)
Here’s an example of bitwise AND:
5 & 13 // output is 5
What’s happening behind the scenes is well-represented by this algorithm.
2. Bitwise OR (|)
The bitwise OR operator ( | ) acts the same as AND, except that it returns true whenever at least one of the relative bits is 1. Here’s an example operation:
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 (~)
The NOT operator (~) just flips the bits. So every 1 bit turns to 0, and vice versa. It only receives one operand, like this:
~ 16 // output is -17
The algorithm is simple to implement. In decimals, it would look like this:
-(x + 1)
Now you know all about bitwise operators and how they work!
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.