Create a large bit field?

Question

I want to create a large bit field in JavaScript that will effectively represent a multi-dimensional array of markers (uses indexing to jump to various dimensions in the physical "1D" structure).

Rather than a bunch of numbers, I'm considering how I might use a string as bits, so I can allocate a string of the appropriate length first. Considerations such as data types, Unicode and conversions come into play (also no Unicode support before JavaScript 1.3).

However I'm open about other suggestions how to use JavaScript to achieve a large bit field.

Update:
Just for informational purposes: On average I might be using ~2187 bits/markers (274 bytes), but would like a generic answer than can accommodate many more bits.

Answer 1

One problem with strings is that they are immutable, so if you want to change anything, you would need to rebuild the string.

I would just stick to using numbers. Using the bitwise operators, you can fit 32 bits in each number.

You could fit up to 53 bits, since JavaScript numbers are double-precision floating point, but the bitwise operators convert their operands to 32-bit integers, so you wouldn't be able to use them to get at the individual bits (if you wanted to, you could accomplish the same thing with combinations of division, Math.pow, etc. but it would be more complicated).

Here's a basic implementation that lets you get, set, and unset individual bits:

function BitField() {
    this.values = []; // You could set the length here, but it's not necessary
}

BitField.prototype.get = function(i) {
    var index = (i / 32) | 0; // | 0 converts to an int. Math.floor works too.
    var bit = i % 32;
    return (this.values[index] & (1 << bit)) !== 0;
};

BitField.prototype.set = function(i) {
    var index = (i / 32) | 0;
    var bit = i % 32;
    this.values[index] |= 1 << bit;
};

BitField.prototype.unset = function(i) {
    var index = (i / 32) | 0;
    var bit = i % 32;
    this.values[index] &= ~(1 << bit);
};

Answer 2

In recent browsers, efficient numeric array types are available. There is no bit-array, but you might use Uint8Array or Uint32Array and pack the bits yourself (in a similar fashion to Matthew Crumley's answer; just use a numeric array instead of []).

---

Obselete but equivalent answer (CanvasPixelArray has been replaced by Uint8ClampedArray):

If the browser you're targeting supports <canvas>, then you might borrow a CanvasPixelArray object (canvas.getContext("2d").createImageData(...).data; note that this need not be the same size as the canvas) to (hopefully) memory-efficiently store the data (each element is an octet). And if your data is 2D, you can get a visualization for free!