This content originally appeared on DEV Community and was authored by Oleg GROMOV
Computer science is full of magic, which is often obscured from our eyes these high-level days. And rightly so: usually to implement features needed by our users we don't need any fancy CS knowledge.
Yet sometimes you may get something from knowing basics of computer science, such as bitwise operations and binary code in general.
I won't go into much detail about how decimal, binary and other numeral systems work. Instead, I'll show you how to compactly store small values needed by our web applications in a single 32-bit unsigned integer.
32 bits as a cap aren't selected randomly. This is the limit for a JS interpeter to perform binary operations.
Why store something in a compact form?
Let's start with a typical single page web application. For instance, a spreadsheet editing app with multiple panels and windows sprinkled all over the screen.
We will also assume our users may benefit from sharing links to the documents they create and restoring exact UI configuration so that it's easier to resume work from the state we left it off at.
So our app has 10 panels, and we need to encode state of these panels (open or closed for simplicity) in URLs they share.
You typically would create a URL similar to this: ?panel1=on&panel2=off&panel3=on and so on. It's easy to see how wordy this becomes even with 10 panels, and what if other parts of our URLs are important too? So we don't want to end up sharing something like this:
What if instead, we could use a single URL parameter, say ?panels=626 to encode all these values at once, in a single number?
This is possible, thanks to the bitwise operations magic, and I'll show you how exactly.
Basics of bitwise operations
If you paste parseInt('1001110010', 2) into a JavaScript interpeter prompt and hit enter, you'll see the decimal number - 626. This is how these 10 bits are encoded into a numeric value in decimal numeral system.
By definition, a bit is a value represented by two possible states - 1 and 0. Exactly what we need to encode a true or false in the most compact form. So we can use these mechanics to store panel states (visible or hidden)!
Let's try doing so by hand.
We will count bits from right to left, first bit having the index of 0 and last having 9. These are, not coincidentally, powers to which you have to raise the binary base 2^n or Math.pow(2, n) to get numbers represented by these bits.
Using exponentiation and binary shifts to store and restore values
So to store the state of panels, we may use the following code:
const panelStates = [
false,
true,
false,
false,
true,
true,
true,
false,
false,
true,
];
let result = 0;
for (let i = 0; i < panelStates.length; i++) {
result = result | panelStates[i] ? Math.pow(2, i) : 0;
}
console.log(result);
You may paste the code above into any JS interpreter and see that this code, indeed, prints the expected number 626.
But why? In the loop, we applied the binary OR operation represented in JavaScript by the pipe sign | to the result. As the second operand, we used 2 raised to the power of index, which is, not coincidentally, the number of bit when counting from right to left, starting from zero.
Magic? No, it's binary encoding in all its beauty.
But hey, you should say now, we don't need to only to encode, we need to get our values back too! Let's do so.
const panelStatesEncoded = 626;
const panelStates = [];
for (let i = 0; i < 10; i++) {
const mask = panelStatesEncoded & Math.pow(2, i);
const bitValue = mask >> i;
panelStates.push(Boolean(bitValue));
}
console.log(panelStates);
So the last line of this code will expectedly print an array with the same values we started from.
Why? Well, this code includes a few more binary operations we have to understand. But there is nothing impossible for a computer science magician, isn't it?
First, we start with looping from 0 to 9, inclusive, as we know exactly how many boolean values we're looking for in a number.
The operation we need to perform next is binary masking using a logical AND operator represented by & in JavaScript. So we know that a particular bit in our panelStatesEncoded number represents state of an N-th panel. Therefore, we need to somehow choose it and only it.
This is done by the AND operator: when we do Math.pow(2, 3) for the 3rd panel state, for example, we get 8, which is 1000 in binary code. 1000 & 1011, where the first number is a mask and the second one is our encoded panels state's first 4 bits, we get 1000.
This is because logical AND only leaves the bits that are present in both values on. Had we used 0011 as our second operand, AND would yield 0000, which is simply 0.
But then 1000 we get from the operation is 8, not true or false, or anything else meaningful. So we have to shift it to the right using binary shift operator >> 3 times (our index, the power of 2 that is 8) to get a single bit.
A single bit, a 0 or 1, is easily converted into a boolean value using the Boolean conversion, and we can push it to the array of values.
Our puzzle is now complete. We can toggle right bits by doing Math.pow(2, n) or actually simply doing binary shift to the left 1 << n, which is the exact equivalent of raising 2 to the power of n. Then we can decode, applying a bitmask and shifting it back to the right n times.
Abstracting complexity away
Hopefully at this point you're as much thrilled as I am. Even decades after getting into computers, I am still excited to make them do what I want speaking the same language they do. The allmighty binary.
But isn't it too tedious to write by hand and, perhaps, even too error-prone and complicated to be used in production-ready applications?
Indeed, it is! So I created a library to abstract unnecessary complexity away (yet I'd still argue you have to know how it works under the hood). Make some noise for bitwise-options. Yay!
Not only does it allow you name your options and then read them from and write to a single 32-bit integer, it also makes it possible to store multiple unsigned integer values in a single number.
For example:
import BitwiseOptions from 'bitwise-options';
// Configure available options
const options = new BitwiseOptions([
{name: 'boolean'}, // single-bit boolean by default
{name: 'uint_single', type: 'uint'}, // single-bit unsigned int
{name: 'uint_3bit', type: 'uint', size: 3}, // 3-bit unsigned integer in range of [0, 7]
]);
options.read(26); // 11010 in binary
console.log(
options.get('boolean'), // false
options.get('uint_single'), // 1
options.get('uint_3bit'), // 6
);
options.set('uint_3bit', 0);
console.log(
options.get('uint_3bit'), // 0
);
console.log(
options.toNumber(), // 2
);
You can find the library on GitHub and npm.
Yes, I was too lazy to implement signed integer support but will be happy to do so if you:
- enjoyed reading the article as much as I enjoyed writing it
- give the library a star on github so that more people get to know about it
- follow me on Twitter, where I write about things worth knowing as a software person if you seek independence and satisfaction
Thank you for you attention and let me know in the comments if you found this useful and why?
This content originally appeared on DEV Community and was authored by Oleg GROMOV
Oleg GROMOV | Sciencx (2021-05-14T12:08:23+00:00) How to use bitwise operations to compactly store small values in a single number. Retrieved from https://www.scien.cx/2021/05/14/how-to-use-bitwise-operations-to-compactly-store-small-values-in-a-single-number/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.