A Comprehensive Primer on Binary Computation and Bitwise Operators in Javascript
Bitwise operators, though they take a few minutes to learn, are a fun way to make your code more space and time-efficient. They can also provide surprisingly simple solutions to complex problems.
But what are bitwise operators?
According to MDN, bitwise operators are operators that “treat their operands as a sequence of 32 bits (zeroes and ones), rather than as decimal, hexadecimal, or octal numbers. For example, the decimal number nine has a binary representation of 1001. Bitwise operators perform their operations on such binary representations, but they return standard JavaScript numerical values.”
What this means is that we can use these operators to manipulate integers as if they were binary representations of the same numbers. And frankly, there’s no reason not to treat them, or think of them, in binary. After all, ‘1100’ in binary and ’12' in base 10 merely represent the same quantity in two different ways.
So when we apply conventional mathematical operators to our numbers (+, -, *, /), it is usually easier to think of our numbers in base 10. However, when we apply bitwise operators to these numbers (>>, <<, &, |, ^, -, ~), it will make our lives much easier to envision them as being represented in base two (binary).
But what is base two?
What do I mean when I refer to base 2? It will be easier to understand if we start by talking about base 10. Our math system is built around base 10 because we have ten fingers. This is literally the only reason. There is no mathematical reason that ten is inherently special. If you looked at ten objects on a table, you would most likely say “that is a pretty random quantity, I don’t think we should base our number system around this amount.” In my humble opinion, twelve would otherwise make a bit more sense, since it is evenly divisible by 2,3, and 4.
What base 10 means is that we have a separate symbol for each number 0–9. ‘0’ is a circle, ‘1’ is a vertical line, ‘2’ looks like a swan, etc. But once we get the number past 9 (to the quantity that is equivalent to 9 + 1) we run out of symbols, and we instead group all of those together into one group, called a ‘ten’, and we say we have ‘one ten’. Since we don’t have a symbol for this quantity, we represent it by using a ‘1’, but moving it over to the left. We use ‘10’ to show that we have ‘one ten’ and ‘zero ones’. Once we have ten 10's, we group them together as ‘one hundred’, and write it as 100.
However, there is no reason that the number that is equivalent to 9 + 1 is special. We could easily make a system based around the quantity 5, instead. We would count 0,1,2,3,4, and then jump to 10. But 10 would mean something more like ‘one group of five’. And 100 would mean something more like ‘(one group of) five groups of five’ (aka twenty-five, in our system).
So binary is based on ‘base 2’. This means that we count 0,1, and then 10. But 10 means ‘one group of 2’, and 100 means ‘(one group of) two groups of two’ (aka ‘four’, in our system). 10,000 = ‘(one group of) two groups of two groups of two groups of two’ = 2 * 2 * 2 * 2 = 2⁴ = ‘sixteen’.
Starting to get confused — just imagine we had two fingers instead of ten. How would our system be different? We would count ‘0, 1, 10’. But ‘10’ would mean what we usually mean when we say ‘two’.
Binary in Javascript
So, if we’re doing computation in Javascript, we can assign a variable to the integer 9. If we’re doing normal computation, we will find it easiest to think of that 9 as being in base 10.
But that number can ALSO be thought of as the series of bits 1001 in base 2 (and all I mean by “bit” is one digit or place value — one of the individual 0s or 1s in the above number). This is where binary operators come in. If we apply the NOT operator (~) to the number 9, it will flip each bit — from 1001 to 0110. Speaking in base 10 terms, ~9 is equal to 6.
If we are working with bitwise operators, we should think about our numbers in base 2, rather than in base 10. This is because it is easier to recognize how ~1001 relates to 0110 (base 2) than how ~9 relates to 6.
By this point, you might be saying something like “but Paul, I just tried running ~9 in my browser, and it absolutely not returning 6!”. If you were to say that, you would be right, and I would be wrong. I just wanted to keep things simple. But keep reading for the explanation!
The problem is that (and this is one part of MDN’s definition that was initially lost on me), insofar as these numbers are treated as a binary representation, they are treated as existing in 32 bits — as 32 digits strung together. So when we use bitwise operators, 9 will be treated as 000000000000000000000000000001001. Therefore, ~9 will be equivalent to 1111111111111111111111110110 (which, you were right, is not the same thing as 6).
Still following? We’re almost to a full understanding of binary in JS. But there’s still one more aspect of binary representation that I have been intentionally concealing from you. This is that, in modern computing, the negative of a number is represented by its two’s complement of that number. Though I may be missing some of the intricacies of what this means, what I think I do understand is that the leftmost (greatest) bit/place value is used to help represent negative numbers. Allow me to explain.
Normally, we find the total value of a number by adding together the sum of its digits. In base ten, we can find what the number 1973 represents by taking each place value, and adding together the sums they represent. So in base 10:
base 10: 1973 = 1000 + 900 + 70 + 3Similarly, in base 2, 1110 is equivalent to 8 + 4+ 2 + 0, which is the same thing as 14 in base 10.
base 2: 1110 = 1000 + 100 + 10 + 0 aka: 14 = 8 + 4 + 2 + 0
However, in modern computing, the left-most bit in a series is used to represents the negative component of a number. If we were working in only 4 bits, 1110 would represent -8 + 4 + 2, which is equal to -2. If we wanted to represent, say, -7, we could use 1001 (-8 + 0 + 0 + 1).
base 2: 1001 = 1000 + 000 + 00 + 1 aka: -7 = -8 + 0 + 0 + 1
Similarly, in 32 bits, if the leftmost bit is a one, it represents -2³², which is equal to -4,294,967,296. Using the other bits as the positive component of our number, we can produce any negative number we want, provided that it has an absolute value of less than 4,294,967,296. We can represent a slightly less wide range of positive numbers: since the 32nd bit is reserved for our negative component, the largest place value we can use represents 2³¹. If we line up 31 ones in a row, and leave the leftmost bit as a zero, we can represent up to positive 4,294,967,295 (one less than the largest negative number).
The implication for applying a negative transformation to bits when using this system is interesting. Look for the pattern. In five bits, the negative of 01001 (8 + 1 = 9) is 10111(-16 + 4 + 2 + 1 = -9). The negative of 10011 (-16 + 2 + 1= -13) is 01101 (8 + 4 + 1 = 13). In both cases, you might observe that the negative is obtained by flipping each bit, and then adding one. The negative of 01001 (9) becomes 10110 + 1 = 10111. Similarly, to find the negative of -13: -10011 => 01100 + 1 => 01101. See below
Algorithm for finding the negative of a binary number using two's complement:
1) flip the bits
2) then add onebase 2 : neg (01001) = 10110 + 1 = 10111
/ | \
aka: neg (9) = -16 + 4 + 2 + 1 = -9
Bitwise Operators in Javascript
In Javascript bitwise operators can be used to quickly manipulate these binary numbers in interesting ways. We’ve already discussed the negative operator (-) and the NOT operator (~) — remember, the (~) operator flips each bit, and the (-) operator flips each bit and then adds one. Let’s learn about some others.
One important note, however (and this was alluded to above) is that javascript tends to communicate with the user in base 10. So it will anticipate that all the numbers we type into the system are in base 10, and it will return all results to the console in base 10. So if I type ‘10010’ in javascript, JS will NOT interpret it as binary/base two. Instead, JS will interpret it as the number 10,010 in base 10 (ten thousand and ten). So if you want to use these binary operators, you will have to write your numbers in base 10, and use the binary operators to act on them AS IF they were the base 2 equivalent.
So if I want to use ~1010 to flip the bits and produce 0101, I CANNOT simply write “~1010”. Instead I will need to find the base 10 equivalent of my number (in this case 1010 = 12), and put my operator in front of that number. So I would write “~12”, instead. And instead of printing out the result as ‘0101’, JS will print it in base 10, as ‘5’.
If you would like to enter your code as base 2 instead, you can simply use the parseInt operator. ParseInt’s first argument is the characters that you want interpreted as a number, and the second argument is the base system you want them interpreted in. So if you write (1010, 2), it will interpret ‘1010’ as being in base 2, and will return the data that represents this number. So if you want to simulate ~1010, instead of writing ~12, you could write ~parseInt(1010, 2).
ES6 Update: You can also use binary literals to enter binary numbers! Just write ‘0b’ and then the binary number you want to use. ‘0b101’ can be used to represent the binary number ‘101’ aka the decimal number ‘5’.
AND, OR, and XOR (&, |, ^)
Note that ALL the examples below will use base 2 notation for clarity. But remember —as per the explanation above, you’ll have to use base 10 numbers as your inputs, or parseInt, if you want to replicate these examples in a javascript environment.
The AND, OR, and XOR operators take in two binary numbers, compare EACH BIT (each place value), and produce a new number based on what they see in each place values.
For example, 1010 & 1000 would compare each place value of each number to each other. If it finds two ones, it will produce a 1 in the output place value. If it finds two 0s, or a 1 and a 0, it will output 0 in that place value of the output. So it can ONLY produce a 1 if BOTH input bits are 1. If either is a 0, it will produce a 0. Scroll below for an example.
This should line up with our intuitions about normal speech. If I say that “Elijah ate a sandwich AND Makhi ate a sandwich”, my resulting statement can only be thought of as true (1) if BOTH of the input statements are true (1). If either party did not eat a sandwich, our statement is false (0). So 1 AND 1 = 1, but 1 AND 0 = 0.
Here’s an example of the AND operator in action:
& Operator (AND)example: 1100 & 1001 = 10001100
1001 &
--------
1000
The OR operator (|), will similarly compare two numbers, and produce an output number by lining up each bit in the two input numbers. If it sees two 0s, it will output a 0 for that bit. However, if it sees a 1 and a 0, or two 1s, it will output a 1.
This is comparable to a statement like “You must be crazy or you must be stupid”. We would say the speaker is correct (1) as long as one or both of the sub-conditions are true. ONLY if the interlocutor is neither crazy nor stupid would we say the statement is false (a 0).
| Operator (OR)example: 1100 | 1001 = 11011100
1001 |
--------
1101
Finally, the XOR operator (^) is used for an “exclusive or”. This will only produce true for a given bit if one of the input bits is a 1, and the other is a 0.
This is similar to a statement like “You can have ice cream OR you can have pie”. We are taking the speaker to be asserting that only ONE of these things can be true. If both turned out to be true, or both turned out to be false, we might say that the speaker’s statement was wrong.
^ Operator (XOR)example: 1100 ^ 1001 = 01011100
1001 ^
--------
0101
Left shift (<<), sign-propagating right shift (>>), and zero-fill right shift (>>>)
These useful operators shift the place value of our base-2 numbers over by a certain number of bits/digits. The way this operates should be relatively familiar to us from our experience with base 10, in which we can shift place values by multiplying or dividing by 10.
Let’s start with the left shift (<<). If I take a binary number — say 1011 (aka 11) and I apply the << once, it will shift each number over by one place value, producing 10110 (22). This is similar when we multiply a number by 10 in our base 10 system (3130 * 10 = 31300). In both cases, we fill a 0 into the bottom place value. You might notice that applying one left shift is equivalent to multiplying our number by two. To left shift a number once, we would write [number] << 1.
As you can probably guess, the number on the right of the sign indicates the number of times we want to left shift our number. So 19 << 2, would mean that we want to left shift the binary equivalent of 19 (10011) two times. This would produce 1001100, aka 76. This is also equivalent to multiplying our number by two twice (aka 2², aka 4).
<< Operator (Left shift)example: 1101 << 2 = 110100
The right shift operator (>>) shifts our number to the right by two place values. So 010100 >> 2 (aka 20 >> 2), results in 000101 (aka 5). This is equivalent to dividing our number by two, twice. You can observe in the example below, that if we operate on a number like 01101 (13) that will not divide evenly, the remainder is discarded.
Where this gets strange is if we are right-shifting a negative number. Suppose we are using two’s complement, and we have a number like 1010 (-8 + 0 + 2 + 0 = -6). If we right-shift it once, do we want the computer to fill in a 1 or a 0 in the leftmost bit?
If we fill in a zero, then left-shifting 1010 yields 0101. So it goes from -6 to 5 — quite different from the result we might have anticipated given our earlier conclusion that this operation is similar to dividing by two. This sort of operation is known as “zero-fill right shift”, and is represented by the sign “>>>”.
On the other hand, if we fill in a 1 for our leftmost bits, then 1010 >> 1 becomes 1101, which is equivalent to -8 + 4 + 1 = -3. This is more similar to the result we might have expected right-shifting to have. This is know as “sign-propagating right-shift”, and is represented by the sign “>>”.
However, as you can observe below, if we are operating on positive numbers (which will have a zero in their leftmost bit), then either sign will fill a zero in, and will have identical results.
>> (Sign-Propagating Right shift)example1: 110100 >> 2 = 111101example2: 0101 >> 2 = 0001
Compare to:
>>> (Zero-Fill Right shift)example1: 110100 >>> 2 = 001101example2: 0101 >> 2 = 0001
Not (~) and negative (-) Operators
These are discussed more above, but are included for reference.
~ (NOT)example: ~1001 = 0110
For negative, recall that if we’re using the two’s complement, we can find the negative by flipping the bits and then adding one.
- (NEGATIVE)example: -1001 = 0111
Why would I ever want to use these operators?
It may occur to a savvy reader that many of these operations can be performed easily enough without resorting to bitwise operators, thinking in binary, or reading extraordinarily long Medium articles. Why, for example, should we want to do 3 >> 5 instead of 3 * 2⁵, which is fully equivalent?
If you are thinking this, you certainly have a point! However, these operators really start to shine when you realize that you can use binary to store information that you might otherwise use an array or an object for.
Imagine, for example, you have a list of students, each one of whom you are waiting to turn in their mathematics homework (maths, in England). If you want to track this information in javascript, you might initially decide to make an array, where each element in the array is a student. Being the savvy storage-space-stingy programmer you are, instead of representing each student as a separate object, you might represent each student as a simple boolean — true if they have turned it in, false if they haven’t. So you start off with an array full of falses: [false, false, false, false, false, false]. On the day before the homework is due, some of the students turn in their homework early, so you iterate through the array and change some of the falses to trues: [true, false, true, false, false, false]. Depending on how you do this, you’ll have to iterate through the array at least once, giving this operation a worst-case time complexity of O(n) (if you’re familiar with that kind of thing). The next day, some more students come in late, so you again iterate through the array, and flip some more of the falses to trues: [true, true, true, false, true, true].
This works well enough. But think about how you might be able to use binary and bitwise operators to store and manipulate this same information. First of all, you wouldn’t need a whole array full of elements to represent the class. Instead of an array full of falses, start with the series of bits 000000. This takes up much less space, as you are replacing an array of size n with a single number! After the first day, it will be 101000 — the equivalent of the number 40. It should be surprising and pleasing that the mere number 40 is sufficient to encode all of the information you need about the state of the class! And the next day it becomes 111011, aka 59.
This should demonstrate how binary operators can help you optimize for space. But it will also help us update our digital representation of the class much more efficiently. After the first day, we see that the students stored in positions 1 and 3 (0 and 2 if you prefer 0-indexing) have turned in their homework. We can update our storage easily with the OR operator (|). 00000 | 101000 = 101000. The next day we take the result, and add the 3 additional students to turn in the homework: 101000 | 010011 = 111011. In both cases, the first number represents the current state of the class, the second number represents the additional submissions, and the third number combines both to find the new state of the class.
Note how much more time-efficient this is. Each OR operation is a constant time operation on two integers, similar to any normal mathematical operation like 6 + 5. While our previous method needed to go through EACH element in the array, and decide whether to update it or not (and O(n) efficiency operation), we can now do the same thing in one step (a particularly quick O(1) operation). We will also end up writing much less code using these operators than if we were using loops, etc.
But this is only one example — there are many convenient, quick, and easy ways we can use our operators to manipulate our data. If we want a list of which students did NOT turn in their homework, we can do ~111011 to get 000100 (although be cognizant of what this will do to any zeros to the left if we are working in 32 bits). However, If we want to add an additional student to our class (and if we are working in 32 bits and have bits to the left to spare), we can simply do 111011 << 1 and get 1110110 with a new student on the end. And so on.
Imagine how you could use binary and bitwise operators to represent the vacancies in a hotel. Or you could use two binary numbers to represent the state of a tic tac toe board: one number could represent the squares with x’s, and the other number could represent the squares with o’s. Then you could do spacesX | spacesO to yield all filled squares on the board, or ~(spacesX | spacesO) to yield any spaces available to play on.
Now that you’ve learned about binary computation and bitwise operators, keep an eye out for opportunities to use them. Not only will you save time and space, but you are likely to find solutions to problems that are fun and surprising. Plus, your friends and family will be impressed by your mastery of time-efficient operations. Happy coding!
