Bitwise Operators in JavaScript
Bitwise Operators are rarely used in JavaScript whereas you would commonly see it being in used in languages like Objective-C or Java. Do other languages just have more resource constraints or have problems that need hyper performance more? That’s not really what I’m here to talk about, this is more of a fun blog on what Bitwise Operators can do in your JavaScript application.
Crash Course #
Here is a short recap of your CS 101 class on Bitwise Operators:
- Bitwise AND returns a one if the two bits are both one
- Bitwise OR returns a one if one of the two bits is a one
- Bitwise XOR returns a one if either bit is a one or zero but not both
- Bitwise NOT inverts the bits
- Shift Operators shifts bits a specified number of bit positions
- Zero-filling Shift Operators so the result is always a 32-bit unsigned integer
Applications #
Bitwise AND ( & ) #
- Determining if a number is odd or even
((x & 1) === 0)
Bitwise OR ( | ) #
- Number truncation (floats)
x | 0
- Math.floor for positive numbers
(3.14 | 0) === 3
- Masking a bitwise flag
const customFlag = flag | mask;
Bitwise XOR ( ^ ) #
- Toggle a bitwise switch
x ^= 1
- Variable swap (redundant with ES6 swap
[a, b] = [b, a]
)
a ^= b, b ^=a, a ^= b;
Bitwise NOT ( ~ ) #
- Array includes
!!~arr.indexOf(x)
- Truncation when doubled (floats)
~~(3.14) === 3
Shift operators ( >> and <<) #
- Math.pow
Math.pow(2, 17) === 1 << 17
- Float to Integer conversion
(3.14 >> 0) === 3
- Hex to RGB and RGB to Hex
const dec = parseInt(HEX, 16);
const RGB = {};
RGB.r = (dec >> 16) & 0xFF;
RGB.g = (dec >> 8) & 0xFF;
RGB.b = (dec) & 0xFF;
const HEX = ('#' + (1 << 24) + (RGB.r << 16) + (RGB.g << 8) + RGB.b).toString(16).substr(1);
Zero-filling Shift Operators ( >>> and <<< ) #
- Converting decimal to binary
(decimal >>> 0).toString(2);
Applications When Mixed Together #
Finding the smaller (or larger) of two integers #
const x = 7;
const y = 31;
const smaller = y ^ ((x ^ y) & -(x < y));
console.log(smaller); // 7
or the larger …
const x = 7;
const y = 31;
const larger = x ^ ((x ^ y) & -(x < y));
console.log(larger); // 31
Bit Mask Config #
Rather than having a separate boolean parameter for each case and having a cascading if/else statements (as well as existence checking), a bitmask configuration is an option. A bitmask is a sequence of bits that can manipulate and/or read flags. Each placement of a bit represents a configuration of either true or false (1 or 0). A layman way of explaining this is represented by how 2 which is 0010
is different from 1 which is 0001
but not 3 which is 0011
since they share the same 2nd to last placement.
const flags = 5; // 0101 from config
const FLAG_A = 1; // 0001
const FLAG_B = 2; // 0010
const FLAG_C = 4; // 0100
const FLAG_D = 8; // 1000
// If we own a Boggart or Chimaera
const mask = FLAG_B | FLAG_C; // 0010 | 0100 => 0110
if (flags & mask) { // 0101 & 0110 => 0100 => true
// The same thing as (flags & FLAG_B) || (flags & FLAG_C)
// Take care of magical beasts (Boggart or Chimaera)
}
if (flags & ~mask) {
// ~mask equals ~(0110) = 1001
// Essentially an else since we flipped the mask
}
Adapted source
As you can see bitmask can be very powerful by making configuration requirements into compact statements. There are also plenty of options in automating the creation of the flags
configuration such as using arguments
or an actual array.
Other uses for masks are also: error flags, permission flags, etc.
Automated Bitmask Config from Arguments #
If we wanted to make use of bitmasks for configurations, we need to find an efficient way to manage configurations, here is a method
that handles the creation of the bitmask.
The first argument acts as the first placement i.e. 2^0
for the bitmask.
The nth argument acts as the nth placement i.e. 2^(n - 1)
since we start at 0.
function createBitMask(...states) {
// Overflows at 32-bits and wraps around
const len = (states.length > 32) ? 32 : states.length;
const mask = states.reduce((mask, state, index) => {
return mask |= state << index;
}, 0);
return mask;
}
createBitMask(false, true, false, true); // 10 === 1010
createBitMask(true, true, true); // 7 === 0111
createBitMask(false, true); // 2 === 0010
createBitMask(true); // 1 === 0001
Bit/Byte-Based Data Structures #
Using bits (or bytes) instead of types that take on more memory such as Strings, Objects, or what not, allows us to be able to search, sort, and store data more efficiently. Imagine a bit/byte-based data structure versus a traditional one with respect to sorting Integers, the byte array would allow us to implement Bucket Sort with little memory consumption.
Bucket sort works as follows:
- Set up an array of initially empty “buckets”.
- Scatter: Go over the original array, putting each object in its bucket.
- Sort each non-empty bucket.
- Gather: Visit the buckets in order and put all elements back into the original array.
Encoding Decoding #
Not to go in deep into security topics, but encoding and decoding algorithms use bitwise operations. See Base64 encoding and decoding. Or MD5 algorithm.
Hash Code Calculation #
When using a custom hash function for cases such as memoization, bitwise operators would be useful to generate the unique hash key from the parameters provided with little computational time (you’re using memoize
so we know you need every little millisecond!).
Use Case for xor #
xor
is quite useful in situations where you want to check if one of the two configurations (a
or b
) are active but not neither nor both. For reference, a XOR b
results are displayed as the following:
a | b | a XOR b |
---|---|---|
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 0 |
With bitwise operations …
const RAVENCLAW = true;
const GRYFFINDOR = false;
if (RAVENCLAW ^ GRYFFINDOR) {
// Either is RAVENCLAW or GRYFFINDOR but not both
} else {
// Neither RAVENCLAW nor GRYFFINDOR and not both
}
Without bitwise operations …
if ((RAVENCLAW || GRYFFINDOR) && RAVENCLAW !== GRYFFINDOR) {
// Either is RAVENCLAW or GRYFFINDOR but not both
} else {
// Neither RAVENCLAW nor GRYFFINDOR and not both
}
TLDR #
Bit operators add complexity and less readability to your code in exchange for faster processing speed and less memory taken. However does the increase in performance warrant the technical debt bit operators produce? Right tools for the job is always the default answer but just as es2015 is here to stay, so too would very efficient javascript application use cases such as trading or medical scenarios. But on the other hand, so too does more powerful JIT compilers become standard to optimize your code possibly negating the benefits.