In this series of articles we take a look at different Computer Science topics from the prism of JavaScript. We’ve already played around with different algorithms and sorted a bunch of arrays. However, going back to the most fundamental concepts is always a good idea.
When I say fundamental I mean the most fundamental of them all, ones and zeros, also known as bits. To be fair, I’ve always neglected bitwise operations since I don’t use them in my daily work and probably never will. But for the computer everything comes down to them.
Understanding bits and bitwise operation won’t make you a better JavaScript developer. It probably won’t help you with the React app you’re working on but it will generally make you a better software developer.
You don’t need to know it all and in fact you will never remember it all. My goal in this article will be to cover the most fundamental knowledge one must have about bits and bit manipulation.
What are bits?
Okay, so technically for the computer everything goes down to 1s and 0s. It does not operate with digits or characters or strings, it uses only binary digits (bits). The short version of this explanation is that everything is stored in binary form. Then the computer uses encodings such as UTF-8 to map the saved bit combinations to characters, digits or different symbols (the ELI5 version).
The more bits you have, the more permutations and the more things that you can represent.
Let’s take the number 113 for example. The easiest way in JS to get it’s binary form is like this: Number(113).toString(2). This will give us 1110001. Knowing that everything is just bits under the hood, we will now take a look at how we can manipulate them.
A lot of articles have examples with hexadecimal numbers. In this one, we will be looking only at decimal and binary numbers. The reasoning behind that is that I find this to be more intuitive to understand. When in doubt you can basically write down the bits and all the operations on a piece of paper and trace what is happening.
Something else to note is that there is no way to enter binary directly in JavaScript. If you want to convert a binary number to a decimal one you can use the parseInt function: parseInt(1111, 2) // 15.
& (AND)
Much like the && logical operator that we’ve already been using in our daily programming tasks, this one will return 1 if both compared bits are 1s and 0 in every other case. It takes a number on both sides (number, not it’s binary form) and then compares their bits one by one.
Let’s visualise that. The numbers 12 and 15 have the binary representations of 1100 and 1111. Let’s use the & operator on those numbers. If you just log it out you will receive 12 again. Weird, did that do anything?
Yes, it compared every bit of 12 with the corresponding bit of 15 and due to how the operator works it got 1100 again, which is in fact 12.
An interesting trick with the & operator is find out whether a number is even or odd. If a number is odd it’s first bit will always be 1. Therefore we can use & and compare the number with 1, so if the number is odd the result will aways be 1. However, I don’t recommend using this in your actual codebase for it is not that clear what you are doing.
| (OR)
This one works much like the || one. It is used to compare two binary numbers bit by bit by returning a 1 for each comparison in which there is at least one 1 and 0 when the compared bits are both 0. If we take the previous example and use this operator12 | 15 will return 15. Why so?
1100 | 1111 will return a 1 for each comparison which is again equal to 1111 or 15.
~ (NOT)
This is a bitwise NOT. The result is e negative number in two’s compliment arithmetic. What is does is that it reverts all bits from 1s to 0s and vice versa.
However, if you log out ~15 you will see that the result is -16, even though the bits are correct. This is because in two’s complement arithmetic, in order to get the negative representation of a number you first need to flip it’s bits then add 1 to it.
You can google it for a better explanation but this is one of those things that you just need to take for granted.
^ (XOR)
This operator is known as the XOR operator or the exclusive OR. Like the & and | operators it takes the numbers on both sides, differentiating in the way it does the comparison.
It will compare the corresponding bits and return a 1 only when there is only a single 1. Maybe this is not that good of an explanation so let’s give a more visual one. 1 ^ 0 will return 1. But 1 ^ 1 will return 0.
The ^ operator returns 1 only in the specific case in which we compare 1 to 0.
Shifting operators
There are two operators that deal with shifting bits — >> and <<. As you can guess the difference between them is the position in which they shift the bits of a number.
The << operator shifts all the bits of a number n times. The thing to note here is that the empty spaces that occur when the number is shifted are all filled with 0s.
The >> operator on the other hand, shifts to the right. The difference between this and the previous shifting operator is that this one will fill a positive number’s bits with 0s and a negative number’s bits with 1s.
Here is the place to point out, that usually the first bit of the number is used to represent it’s sign. If it’s a 1 then it’s negative, if it’s 0 it is positive. Hence the reasoning behind the right shift — it is meant to keep the sign of the number we are shifting.
Bit manipulation
Now that we know what the operators do, let’s have a look at how we can utilise them to manipulate bits.
Say we want to set a bit in a given position. We want the second bit from the right to be set (to be 1). This brings us to the concept of masks. Masks are numbers in binary form where we have only the bit that we want to modify set to 1 or 0 depending on what we want to achieve. We can also say that they are used as a flag to define which bits are to be changed.
If we want to set the first bit the mask will be 0001. In case we want to set the second it will be 0010 and so forth.
An example will make this more clear:
So far, so good. Let’s look at how we can clear a bit — set it to 0. This won’t be as easy as the previous example for we need to keep all other bits as they are.
The difference here is that we want to have a mask full of 1s and have a 0 only at the position where we want to clear. Then we use the & operator which will set only the required position to 0.
We now know how to set and clear bits, but what if we want to flip it? We don’t know whether the bit is set or not, but we really desire to change it’s current state. This is a job for XOR.
XOR is used in this case because using it with 1 on one is guaranteed to flip the value of the bit.
Conclusion
The intention of this post was to cover the fundamentals of bit manipulation and operators. Even though we have barely scratched the surface, this is enough to demystify the topic so you can venture into the world of 1s and 0s on your own and do different kinds of bitwise shenanigans.
Thank you for the read and hope this article has helped you. You can help me, by holding the clap button for a bit (pun intended) and sharing this article with a friend who may be interested!
Programming with JS:
Recursion: https://hackernoon.com/programming-with-js-recursion-31371e2bf808Merge Sort: https://medium.com/@KondovAlexander/programming-with-js-merge-sort-deb677b777c0Binary Search: https://medium.com/@KondovAlexander/programming-with-js-binary-search-aaf86cef9cb3Insertion Sort: https://medium.com/@KondovAlexander/programming-with-js-insertion-sort-1316df8354f5