Skip to main content

Integer math in JavaScript

You may know that all numbers in JavaScript are 64 bit double-precision floating point values. This is sometimes convenient and it works pretty well as a default for novice programmers, who are often confused by integer math, and rightfully so when 1 / 2 = 0. Unfortunately, it makes things slow. Doubles take a lot of memory and floating point math is slower than integer math on CPUs. It's also inconvenient if you want to port existing code to JavaScript, because existing code usually expects to use integer math.

Fortunately, there is a way to make JavaScript do integer math, and it works remarkably well!

TL;DR​

Add | 0 after every math operation to get a 32-bit signed integer result, and >>> 0 for a 32-bit unsigned integer result. And store all your numbers in typed arrays instead of JavaScript arrays.

The background​

JavaScript turns out to have a full set of bit manipulation instructions. The bitwise and/or/xor/not/shift operators are just like C, and I have no idea why JavaScript originally had them because they don't seem very useful for web development. Also that's weird when all numbers are double precision floating point, right? Nobody does bitwise operations on floating point numbers. And neither does JavaScript. In fact, JavaScript will (conceptually) first round your 64-bit double to a 32-bit signed integer, do the bitwise operation, and then convert it back to a double precision value. Weird!

All this conversion sounds expensive! And it probably was, back in the days before asm.js. The asm.js people were porting C code to JavaScript, and the weird casting performed by JavaScript's weird bitwise operators was just what they needed to emulate C's integer arithmetic.

The trick​

In C if x and y are integers then x / y will do integer division, rounding the result down. In JavaScript x / y will always be a floating point division with a floating point result. But if you apply a bitwise operator right afterward, then the result will be rounded down, converted to integer, and you'll get the same number as C did! With a lot more work. Of course you don't want your bitwise operator to change the result, so you can do a no-op bitwise operation such as >> 0 or | 0. No-op in C, of course, but not in JavaScript, because of the integer conversion.

Once asm.js started doing | 0 everywhere, people started being very interested in optimizing it. Obviously you can easily just skip running the OR instruction since it does nothing. But the real work is in all that slow conversion to and from floating point. It turns out that if you add a | 0 after every operation, your JavaScript JIT compiler can skip the redundant conversions too, and just keep your numbers as integers the whole time. When the inputs to a division are known to be integers, and | 0 converts it to integer again afterward, then instead of emitting two conversions to floating point, a floating point division instruction, and then a conversion to integer, the JIT can emit a single integer division instruction, just like a C compiler would, without changing the result at all. This is pretty miraculous!

The details​

All of JavaScript's bitwise operators inherited from C convert their operands and results to 32-bit signed integers. But there's a trick for unsigned integers too. JavaScript has one extra bitwise operator that C doesn't have: >>>. This is essentially an "unsigned right shift" operator, and it is special because its result is an unsigned 32-bit integer. So when you want a signed integer you append | 0 after your arithmetic operations, and for unsigned you use >>> 0.

So this all works great for 32-bit integer math, both signed and unsigned. What about other sizes? Unfortunately if you want 64-bit integer math, you're out of luck. These tricks work for 32-bit numbers because double precision floating point can represent every 32-bit integer exactly, and doing a floating-point division of two integers less than 232 and then converting the result to an integer gives the exact same result as an integer division instruction in every case. But the full range of 64 bit integers isn't representable in double precision floating point. Integers larger than 253 may not be represented exactly, and JavaScript numbers always have to behave as if they are represented by double precision floating point values even when that isn't true. The JIT compiler can't just do 64-bit integer math under the covers and pretend that it's floating point, because it would get different results when the integers are large enough.

Unfortunately, multiplication of two 32-bit numbers can produce results up to 264. When the result is greater than 253 then double precision floating point multiplication may produce different answers than integer multiplication, even when subsequently truncated back to a 32 bit integer. This prevents the JavaScript JIT from using integer multiplication instructions. To solve this problem Math.imul() was introduced. So for integer multiplication, you have to use that instead of the * operator followed by | 0.

OK, 64-bit doesn't work, how about 16-bit and 8-bit? Well, on the one hand you can't do those either, all your integer math is going to be 32 bits wide. But on the other hand that isn't so bad, because CPUs add 32-bit numbers just as fast as 8-bit numbers. Where smaller types really matter is in memory usage. If you want an array of bytes, but you use a JavaScript array to store JavaScript numbers instead, it will use 8 times the memory (and 8 times the memory bandwidth, and 8 times the cache space) because every JavaScript number is 8 bytes. Thankfully JavaScript has a solution for this too: typed arrays. Typed arrays can hold 8-bit, 16-bit, and 32-bit values in both signed and unsigned varieties. As an added benefit, since typed arrays can't hold object references, the garbage collector doesn't need to scan their contents, which also helps performance.

Bonus question: what about 32-bit floating point? It's faster than 64-bit floating point, and used a lot in 3D graphics. Can we use a similar trick to make the JavaScript JIT emit 32-bit float math instructions? The answer is yes, there's a function Math.fround used for this purpose by asm.js. I've never tried using it myself.

Putting it all together​

Asm.js uses these techniques to translate C code to JavaScript and gets impressively close to the performance of native C compilers. But you don't have to use asm.js to benefit. Anytime you want good performance in JavaScript, you can store your data in typed arrays and use | 0 manually to make sure your values stay in integer form. Your code can run fast without resorting to Web Assembly or Emscripten.


Share: