# Bit compressing in JavaScript

I have an bit array var data = []; ... and I have the following function:

jsPerf

function getBit(n) {
return (data[~~(n / 32)] >> (n % 32)) & 1;
}


Because this is a bottleneck, I need the fastest cross-browser solution in my code, can anybody help make it any faster?

Also, ~~(n / 32) === Math.floor(n / 32)

It can be algorithm optimization or syntax optimization (such as asm.js) or something else. Should I change the array type (typedArray or similar)?

-

## migrated from stackoverflow.comJul 16 '14 at 15:52

This question came from our site for professional and enthusiast programmers.

You're right that a TypedArray is generally much faster for such things. Have you tried using one and compared speeds? – Mike C Jul 14 '14 at 14:16
No, one sec, i will create tests. – Sukhanov Niсkolay Jul 14 '14 at 14:16
How are you using getBit (is there a way to process whole words at once more efficiently)? – Cameron Jul 14 '14 at 14:19
"PS: ~~(n / 32) === Math.floor(n / 32)" Only if n isn't negative. ;-) And only if n / 32 is also <= 32,767 (e.g., won't get truncated when it does its round-trip through being a 32-bit integer). – T.J. Crowder Jul 14 '14 at 14:19
The JS optimizers are really quite good. They certainly do constant expression folding (use a random number in your tests, not 3), and seem to simplify based on type information too, probably resulting in the same assembly code for all of the tested versions so far (which is why the timing is so close). – Cameron Jul 14 '14 at 14:50

I tried to speed up your formula :

return (data[n >> 5] >> (n & 31)) & 1;


.... All results are very close anyway : jsperf.com/fastest-bit-compressing/7.

• notice that you can inline the function by yourself (replace function call by direct computation).

• you might wan to cache latest array access by yourself during your computations.

• Or you might want to do the caching in the function. Efficiency will depends on the 'randomness' of your use of the bits.

function getBit(n) {
var itemIndex = n >> 5;
if (itemIndex != lastItemIndex ) {
lastItem = data[itemIndex];
lastItemIndex = itemIndex ;
}
return lastItem >> (n & 31)) & 1;
}
var lastItemIndex = -1, lastItem = 0;

-
I'm afraid that this checking will cost as much as all calculations. – Sukhanov Niсkolay Jul 14 '14 at 15:06
Yes the last function might be faster for a big array / continuos access, but i doubt a bit also. Useless to test it with jsperf so not that easy / fast to test as other ways. – GameAlchemist Jul 14 '14 at 15:17
Your solution is the fastest. (without caching) Tested in product code, render time decreased from 3s to 2500ms. See jsperf. – Sukhanov Niсkolay Jul 14 '14 at 15:21