¿Cómo creo una matriz de bits en Javascript?

Question

¿Cuál es la mejor forma de implementar una matriz de bits en JavaScript?

Answer 1

Aquí hay una que nos prepararon rápidamente:

ACTUALIZACIÓN - algo acerca de esta clase me había estado molestando todo el día - que no era el tamaño basándose - la creación un BitArray con N ranuras/bits era una operación de dos pasos: creación de instancias, cambio de tamaño. Se actualizó la clase según el tamaño en función de un segundo parámetro opcional para rellenar la instancia basada en el tamaño con valores de matriz o un valor numérico de base 10.

(jugar con él here)

/* BitArray DataType */ 

// Constructor 
function BitArray(size, bits) { 
    // Private field - array for our bits 
    this.m_bits = new Array(); 

    //.ctor - initialize as a copy of an array of true/false or from a numeric value 
    if (bits && bits.length) { 
     for (var i = 0; i < bits.length; i++) 
      this.m_bits.push(bits[i] ? BitArray._ON : BitArray._OFF); 
    } else if (!isNaN(bits)) { 
     this.m_bits = BitArray.shred(bits).m_bits; 

    } 
    if (size && this.m_bits.length != size) { 
     if (this.m_bits.length < size) { 
      for (var i = this.m_bits.length; i < size; i++) { 
       this.m_bits.push(BitArray._OFF); 
      } 
     } else { 
      for(var i = size; i > this.m_bits.length; i--){ 
       this.m_bits.pop(); 
      } 
     } 
    } 
} 

/* BitArray PUBLIC INSTANCE METHODS */ 

// read-only property - number of bits 
BitArray.prototype.getLength = function() { return this.m_bits.length; }; 

// accessor - get bit at index 
BitArray.prototype.getAt = function (index) { 
    if (index < this.m_bits.length) { 
     return this.m_bits[index]; 
    } 
    return null; 
}; 
// accessor - set bit at index 
BitArray.prototype.setAt = function (index, value) { 
    if (index < this.m_bits.length) { 
     this.m_bits[index] = value ? BitArray._ON : BitArray._OFF; 
    } 
}; 

// resize the bit array (append new false/0 indexes) 
BitArray.prototype.resize = function (newSize) { 
    var tmp = new Array(); 
    for (var i = 0; i < newSize; i++) { 
     if (i < this.m_bits.length) { 
      tmp.push(this.m_bits[i]); 
     } else { 
      tmp.push(BitArray._OFF); 
     } 
    } 
    this.m_bits = tmp; 
}; 

// Get the complimentary bit array (i.e., 01 compliments 10) 
BitArray.prototype.getCompliment = function() { 
    var result = new BitArray(this.m_bits.length); 
    for (var i = 0; i < this.m_bits.length; i++) { 
     result.setAt(i, this.m_bits[i] ? BitArray._OFF : BitArray._ON); 
    } 
    return result; 
}; 

// Get the string representation ("101010") 
BitArray.prototype.toString = function() { 
    var s = new String(); 
    for (var i = 0; i < this.m_bits.length; i++) { 
     s = s.concat(this.m_bits[i] === BitArray._ON ? "1" : "0"); 
    } 
    return s; 
}; 

// Get the numeric value 
BitArray.prototype.toNumber = function() { 
    var pow = 0; 
    var n = 0; 
    for (var i = this.m_bits.length - 1; i >= 0; i--) { 
     if (this.m_bits[i] === BitArray._ON) { 
      n += Math.pow(2, pow); 
     } 
     pow++; 
    } 
    return n; 
}; 

/* STATIC METHODS */ 

// Get the union of two bit arrays 
BitArray.getUnion = function (bitArray1, bitArray2) { 
    var len = BitArray._getLen(bitArray1, bitArray2, true); 
    var result = new BitArray(len); 
    for (var i = 0; i < len; i++) { 
     result.setAt(i, BitArray._union(bitArray1.getAt(i), bitArray2.getAt(i))); 
    } 
    return result; 
}; 

// Get the intersection of two bit arrays 
BitArray.getIntersection = function (bitArray1, bitArray2) { 
    var len = BitArray._getLen(bitArray1, bitArray2, true); 
    var result = new BitArray(len); 
    for (var i = 0; i < len; i++) { 
     result.setAt(i, BitArray._intersect(bitArray1.getAt(i), bitArray2.getAt(i))); 
    } 
    return result; 
}; 

// Get the difference between to bit arrays 
BitArray.getDifference = function (bitArray1, bitArray2) { 
    var len = BitArray._getLen(bitArray1, bitArray2, true); 
    var result = new BitArray(len); 
    for (var i = 0; i < len; i++) { 
     result.setAt(i, BitArray._difference(bitArray1.getAt(i), bitArray2.getAt(i))); 
    } 
    return result; 
}; 

// Convert a number into a bit array 
BitArray.shred = function (number) { 
    var bits = new Array(); 
    var q = number; 
    do { 
     bits.push(q % 2); 
     q = Math.floor(q/2); 
    } while (q > 0); 
    return new BitArray(bits.length, bits.reverse()); 
}; 

/* BitArray PRIVATE STATIC CONSTANTS */ 
BitArray._ON = 1; 
BitArray._OFF = 0; 

/* BitArray PRIVATE STATIC METHODS */ 

// Calculate the intersection of two bits 
BitArray._intersect = function (bit1, bit2) { 
    return bit1 === BitArray._ON && bit2 === BitArray._ON ? BitArray._ON : BitArray._OFF; 
}; 

// Calculate the union of two bits 
BitArray._union = function (bit1, bit2) { 
    return bit1 === BitArray._ON || bit2 === BitArray._ON ? BitArray._ON : BitArray._OFF; 
}; 

// Calculate the difference of two bits 
BitArray._difference = function (bit1, bit2) { 
    return bit1 === BitArray._ON && bit2 !== BitArray._ON ? BitArray._ON : BitArray._OFF; 
}; 

// Get the longest or shortest (smallest) length of the two bit arrays 
BitArray._getLen = function (bitArray1, bitArray2, smallest) { 
    var l1 = bitArray1.getLength(); 
    var l2 = bitArray2.getLength(); 

    return l1 > l2 ? smallest ? l2 : l1 : smallest ? l2 : l1; 
}; 

CRÉDITO A @ Daniel Baulig para pedir la refactor de rápida y sucia para prototipo basado.

Answer 2

No sé acerca de las matrices de bits, pero puede hacer arreglos de bytes fáciles con nuevas características.

Busque typed arrays. Los he usado tanto en Chrome como en Firefox. El más importante es Uint8Array.

crear una matriz de 512 bytes sin inicializar:

var arr = new UintArray(512); 

Y para acceder a él (el sexto byte):

var byte = arr[5]; 

Para Node.js, utilice Buffer (del lado del servidor).

EDIT:

Para acceder a los bits individuales, máscaras uso de bits.

Para obtener el bit en la posición de la una, hacer num & 0x1

Answer 3

El Stanford Javascript Crypto Library (SJCL) proporciona una implementación de arreglo de bits y puede convertir diferentes entradas (cadenas hexadecimales, matrices de bytes, etc.) en matrices de bits.

Su código es público en GitHub: bitwiseshiftleft/sjcl. Entonces, si busca bitArray.js, puede encontrar su implementación de arreglo de bits.

Se puede encontrar una conversión de bytes a bits here.