Understanding Bitwise Operations in Javascript
Bitwise operations, while uncommon in Javascript, can come in handy in a variety of scenarios. Before I lose you, here’s a quick example for a common scenario:
const isOdd(num) {
return !!(num & 1);
}
Yup! Rather than using modulus, you can use the bitwise AND operator to determine if a number is odd or not. Not only that, this method is faster than using modulus.
From the beginning
Before we go into each bitwise operator and sample use cases, let’s think about how bits work:
Computers create numbers using either 32 bits or 64 bits. So “0” would be represented as either:
32-bit: 00000000000000000000000000000000
64-bit: 0000000000000000000000000000000000000000000000000000000000000000
Javascript, by the way, converts all your numbers to 32-bit whenever it does a bitwise operation and then turns it back to 64-bit, so for the rest of examples, we’ll be using 32-bit.
Each bit can be either a 0 or a 1. To represent the number 1, we just flip the rightmost number from 0 to 1, becoming:
00000000000000000000000000000001
To represent 2, we flip the second bit to the right:
00000000000000000000000000000010
In fact, the value of each bit is the previous bit times 2. So 8 would be:
00000000000000000000000000001000
So what’s the biggest number we can represent? It is actually 2³¹-1. First off, the leftmost bit is reserved for representing the sign (-/+). Second, why -1 ? Go into your calculator and see for yourself. Here’s how I did it:
1 + 2 + 4 + 8 + 16 + 32 + 64 + 128 + 256 + 512 + 1024 + 2048 + 4096 + 8192 + (8192 * 2) + (8192 * 4) + (8192 * 8) + (8192 * 16) + (8192 * 32) + (8192 * 64) + (8192 * 128) + (8192 * 256) + (8192 * 512) + (8192 * 1024) + (8192 * 2048) + (8192 * 4096) + (8192 * 8192) + ((8192 * 8192) * 2) + ((8192 * 8192) * 4) + ((8192 * 8192) * 8) + ((8192 * 8192) * 16)
You can also prove it at a smaller scale by asking, what is the biggest number you can represent in a 1-bit number? 2¹ is 2 but the biggest number is really 1, so 2¹-1.
Each bitwise operator
Now that we’ve cleared up the game field, let’s look at each available operator:
Bitwise AND: &
To help myself understand this operator, I like to view it as a two-step process:
- Do both numbers share at least one 1-bit? So 5 & 3 do because 5 is 101 and 3 is 011. Meanwhile, 4 & 3 do not (100 & 011). If no 1-bit is shared, the return value is 0.
- What is the value for the result when you just take the shared 1-bits. 5 & 3 again only share a 1-bit at the rightmost spot, so the value is 1.
Bitwise OR: |
For this operator, I like to imagine a new empty 32-bit number and then just go through each number and put a 1 at each bit where the given number has a 1-bit. So take 4 | 3:
We start off: 00000000000000000000000000000000
Then we place the 1’s from the number 4: 00000000000000000000000000000100
And then place the 1's from the number 3:
00000000000000000000000000000111
The result is 7!
Bitwise XOR: ^
For this operator, I once again start off with a new empty 32-bit number. I place all the 1’s from the first number. For the second number, however, if I need to place a 1 where a 1 has already been placed, I have to flip it back to 0. The X, I believe, is short for Exclusive, so Exclusive OR. Let’s do 5 & 3:
We start off: 00000000000000000000000000000000
We place the 1’s from the number 5: 00000000000000000000000000000101
We place the 1's from the number 3, and convert the rightmost 1 to 0 because 3 also has a 1 at that position: 00000000000000000000000000000110
So the result is 6!
Bitwise NOT: ~
To understand how this operator works, we need to first dive into how negative numbers work in binary.
Look at this function that converts a decimal into binary:
/**
* @param {number} n
*/
decimal_to_binary = function(n) {
if (n < 0) {
n = 0xFFFFFFFF + n + 1;
}
return n.toString(2);
}
Up until now, we’ve just been dealing with positive numbers, so we could skip over that n < 0 portion. First off, 0xFFFFFFFF is a way of representing 2³² — 1. By doing 2³² rather than 2³¹, we have flipped the sign to negative (-). This looks like:
11111111111111111111111111111111
The smallest negative number (-1) is represented with all 32 bits being equal to 1.
Consequently, -2 is:
11111111111111111111111111111110
and -3 is:
11111111111111111111111111111101
At first this seems counterintuitive, but
- Remember that 0 can’t be negative, so it’s more efficient to have
11111111111111111111111111111111
represent the smallest negative number (-1) rather than 0.
2. At this point, we are actually doing the same procedure for generating positive numbers except:
i. we add 1 due to 1111111… being equal to -1 rather than 0, and we flip 1’s to 0’s rather than 0’s to 1’s. Let’s take -6. If we add 1, that’s -5. If that were positive that would be:
00000000000000000000000000000101
If we flip that, that becomes
11111111111111111111111111111010
Double-check that this is the case with our handy function above.
Going back to the bitwise NOT operator, what we’re doing is simply flipping all 0’s to 1’s and all 1’s to 0’s. ~-6 is equal to 5 because, as we now can visualize, we flipped the rightmost bit from 1 to 0, making it positive, and the 0’s turn into 1’s, resulting in:
00000000000000000000000000000101
Zero Fill Bitwise Left Shift: <<
This operator shifts each bit to the left n times. It is called “Zero Fill” because we fill n bits on the right with 0’s. So 5 << 2 means going from
00000000000000000000000000000101
to
00000000000000000000000000010100
which is equal to 20. Note: The 2 leftmost bits from the original binary representation of 5 are discarded as we are still representing the number with 32 bits rather than 34 (32 + 2).
Zero Fill Bitwise Right Shift: >>>
This operator shifts each bit to the right n times, and n bits on the left are filled with 0's. 2 >>> 2 becomes 0 because the two rightmost bits from the original binary representation of 2 are discarded.
Sign Preserving Bitwise Right Shift: >>
This operator shifts each to the right n times, and n bits on the left take on the values they had before the shift. This is titled “Sign Preserving” because the sign is preserved rather than being flipped to a 0 as in a Zero Fill Bitwise Right Shift. -5 >> 2 means going from
11111111111111111111111111111011
to
11111111111111111111111111111110
which is -2.
Examples
Now that we have seen the bitwise operators available in Javascript, let’s look at some uses:
/*
* @param {number} decimal
* @returns {string}
*/
function decimal2binary(decimal){
return (decimal >>> 0).toString(2);
}
While positive numbers can always be converted to binary using .toString(2), and a positive number >>> 0 has no effect other than returning that same value as no bits shifted, when you run a negative number through >>> 0, while no bits are shifted, the number is automatically converted to its binary representation. Consequently:
(-1 >>> 0) === 0xFFFFFFFF
A more real example
Alright, that last example is more of a party trick than something practical. However, let’s say you had the task to find all the subsets you could generate from an array.
So if your array is [1,2,3]
It should generate: [1], [1,2], [1,3], [1,2,3], etc.
Take a look at this solution:
function subsets(array) {
const result = [];
result.push([]);
for (let i = 1; i < (1 << array.length); i++) {
const subset = [];
for (let j = 0; j < array.length; j++) {
if (i & (1 << j)) {
subset.push(array[j]);
}
}
result.push(subset);
}
return result;
}
There’s a bitwise AND and a Zero Fill Bitwise Left Shift! Let’s delve into those:
1 << array.length: Shifting 1 to the left three times creates “1000” which is equal to 8. If you stop and imagine an array of length 2, 1 << 2 === 4. Another one: 1 << 4 === 16. What’s going on here? The number of possible subsets for an array of length n is 2^n. Since each bit is equal to 2^something, we can take advantage of those overlapping properties for an elegant solution. One final way of looking at this is 1 << array.length is also equal to:
Math.pow(2, array.length)
This second bit is more thorny:
i & (1 << j)
Provided an input [1,2,3], when the function first runs and i = 1 and j = 0, this essentially becomes i & 1 which is the same function from the beginning of the tutorial to determine odd numbers! So at the end of the loop where j = 0, we have:
[
[], [ 1 ], [],
[ 1 ], [], [ 1 ],
[], [ 1 ]
]
Now when j = 1, we are checking i & 2. Indexes 2, 3, 6, and 7 all match because they have a 1-bit one from the right. After this second run we now have:
[
[], [ 1 ],
[ 2 ], [ 1, 2 ],
[], [ 1 ],
[ 2 ], [ 1, 2 ]
]
A third and final run with j = 2 ends up:
[
[], [ 1 ],
[ 2 ], [ 1, 2 ],
[ 3 ], [ 1, 3 ],
[ 2, 3 ], [ 1, 2, 3 ]
]
Unrelated PSA: Looking for a new high paying software development job? Send me your resume to alexleondeveloper@gmail.com and I’ll get back to you!
Conclusion
As you can see, we can make use of bitwise operations to create an elegant solution for subsets and other scenarios. While use cases for bitwise operations are certainly rare, it is always a good tool to keep in your toolkit! Thanks for reading and catch you later.