¿Crear un campo de bit grande?

Question

Quiero crear un campo de bits de gran tamaño en JavaScript que represente eficazmente una matriz multidimensional de marcadores (usa la indexación para saltar a varias dimensiones en la estructura física "1D").

En lugar de un montón de números, estoy considerando cómo podría usar una cadena como bits, por lo que primero puedo asignar una cadena de la longitud adecuada. Consideraciones tales como tipos de datos, Unicode y conversiones entran en juego (tampoco compatibilidad con Unicode antes de JavaScript 1.3).

Sin embargo, estoy abierto a otras sugerencias sobre cómo usar JavaScript para lograr un campo de bit grande.

Actualizar:
Sólo con fines informativos: En promedio que podría estar utilizando ~ 2187 bits/marcadores (274 bytes), pero me gustaría una respuesta genérica que puede acomodar muchos más bits.

Answer 1

Un problema con las cadenas es que son inmutables, por lo que si desea cambiar algo, deberá reconstruir la cadena.

Me limitaría a usar números. Usando los operadores bit a bit, puede caber 32 bits en cada número.

Puede colocar hasta 53 bits, ya que los números de JavaScript son de coma flotante de precisión doble, pero los operadores bit a bit convierten sus operandos a enteros de 32 bits, por lo que no podría usarlos para llegar al individuo bits (si quisieras, podrías lograr lo mismo con combinaciones de división, Math.pow, etc. pero sería más complicado).

Aquí es una implementación básica que le permite obtener, configurar, y los bits individuales no definidas:

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

En Chrome, obtengo unos 10.000 bits.

var bitfield = 0; 
var flag1 = 2 << 1; 
var flag2 = 2 << 2; 
var flagmax = 2 << 10000; 
bitfield |= flagmax 
if (bitfield & flagmax) { 
    doSomething(); 
} 

Answer 3

En los últimos navegadores, los tipos de matriz numéricos eficientes están disponibles. No hay una matriz de bits, pero puede usar Uint8Array o Uint32Array y empaquetar los bits usted mismo (de manera similar a la respuesta de Matthew Crumley, simplemente use una matriz numérica en lugar de []).

---

Obselete pero equivalentes respuesta (CanvasPixelArray ha sido sustituido por Uint8ClampedArray):

Si el navegador que está apuntando soportes <canvas>, entonces usted podría pedir prestado un objeto CanvasPixelArray (canvas.getContext("2d").createImageData(...).data, tenga en cuenta que esto no es necesariamente del mismo tamaño que el lienzo) para (con suerte) memoria: almacenar de manera eficiente los datos (cada elemento es un octeto). Y si sus datos son 2D, ¡puede obtener una visualización gratis!

Answer 4

Esta es una extensión para Matthew Crumley's post a partir de 2010:

Me tomó código de Matthew, añade antes de la asignación y la comparó con mecanografiado implementaciones de matriz.

This jsperf muestra que Chrome es el más rápido y más seguro (esperaría Uint32Array para realizar el más rápido) y que IE solo definió las interfaces pero no se preocupó por optimizar las matrices tipadas. Los resultados de Firefox están oscurecidos porque la consola está inundada de advertencias sobre cómo JSPerf "compila" el código de prueba.

("otro" es (a mi parecer muy privado) IE 11.)

Uint8Array Implementación

function BitField8(nSize) { 
    var nBytes = Math.ceil(nSize/8) | 0; 
    this.values = new Uint8Array(nBytes); 
} 

BitField8.prototype.get = function(i) { 
    var index = (i/8) | 0; 
    var bit = i % 8; 
    return (this.values[index] & (1 << bit)) !== 0; 
}; 

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

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

Uint32Array Implementación

function BitField32(nSize) { 
    var nNumbers = Math.ceil(nSize/32) | 0; 
    this.values = new Uint32Array(nNumbers); 
} 

BitField32.prototype.get = function(i) { 
    var index = (i/32) | 0; 
    var bit = i % 32; 
    return (this.values[index] & (1 << bit)) !== 0; 
}; 

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

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