How do I create bit array in Javascript?

Question

What is the best way of implementing a bit array in JavaScript?

Answer 1

Here's one I whipped up:

UPDATE - something about this class had been bothering me all day - it wasn't size based - creating a BitArray with N slots/bits was a two step operation - instantiate, resize. Updated the class to be size based with an optional second paramter for populating the size based instance with either array values or a base 10 numeric value.

(Fiddle with it 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; }; 

CREDIT TO @Daniel Baulig for asking for the refactor from quick and dirty to prototype based.

Answer 2

I don't know about bit arrays, but you can make byte arrays easy with new features.

Look up typed arrays. I've used these in both Chrome and Firefox. The important one is Uint8Array.

To make an array of 512 uninitialized bytes:

var arr = new UintArray(512); 

And accessing it (the sixth byte):

var byte = arr[5]; 

For node.js, use Buffer (server-side).

EDIT:

To access individual bits, use bit masks.

To get the bit in the one's position, do num & 0x1