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

Answer 3

The Stanford Javascript Crypto Library (SJCL) provides a Bit Array implementation and can convert different inputs (Hex Strings, Byte Arrays, etc.) to Bit Arrays.

Their code is public on GitHub: bitwiseshiftleft/sjcl. So if you lookup bitArray.js, you can find their bit array implementation.

A conversion from bytes to bits can be found here.

Answer 4

Something like this is as close as I can think of. Saves bit arrays as 32 bit numbers, and has a standard array backing it to handle larger sets.

class bitArray {
  constructor(length) {
    this.backingArray = Array.from({length: Math.ceil(length/32)}, ()=>0)
    this.length = length
  }
  get(n) {
    return (this.backingArray[n/32|0] & 1 << n % 32) > 0
  }
  on(n) {
    this.backingArray[n/32|0] |= 1 << n % 32
  }
  off(n) {
    this.backingArray[n/32|0] &= ~(1 << n % 32)
  }
  toggle(n) {
    this.backingArray[n/32|0] ^= 1 << n % 32
  }
  forEach(callback) {
    this.backingArray.forEach((number, container)=>{
      const max = container == this.backingArray.length-1 ? this.length%32 : 32
      for(let x=0; x<max; x++) {
        callback((number & 1<<x)>0, 32*container+x)
      }
    })
  }
}
let bits = new bitArray(10)
bits.get(2) //false
bits.on(2)
bits.get(2) //true

bits.forEach(console.log) 
/* outputs:
false
false
true
false
false
false
false
false
false
false
*/

bits.toggle(2)

bits.forEach(console.log) 
/* outputs:
false
false
false
false
false
false
false
false
false
false
*/

bits.toggle(0)
bits.toggle(1)
bits.toggle(2)

bits.off(2)
bits.off(3)
bits.forEach(console.log) 
/* outputs:
true
true
false
false
false
false
false
false
false
false
*/

Answer 5

2022

As can be seen from past answers and comments, the question of "implementing a bit array" can be understood in two different (non-exclusive) ways:

• an array that takes 1-bit in memory for each entry
• an array on which bitwise operations can be applied

As @beatgammit points out, ecmascript specifies typed arrays, but bit arrays are not part of it. I have just published @bitarray/typedarray, an implementation of typed arrays for bits, that emulates native typed arrays and takes 1 bit in memory for each entry.

Because it reproduces the behaviour of native typed arrays, it does not include any bitwise operations though. So, I have also published @bitarray/es6, which extends the previous with bitwise operations.

I wouldn't debate what is the best way of implementing bit array, as per the asked question, because "best" could be argued at length, but those are certainly some way of implementing bit arrays, with the benefit that they behave like native typed arrays.

import BitArray from "@bitarray/es6"

const bits1 = BitArray.from("11001010");
const bits2 = BitArray.from("10111010");
for (let bit of bits1.or(bits2)) console.log(bit) // 1 1 1 1 1 0 1 0

Answer 6

You can easily do that by using bitwise operators. It's quite simple. Let's try with the number 75.

Its representation in binary is 100 1011. So, how do we obtain each bit from the number? You can use an AND "&" operator to select one bit and set the rest of them to 0. Then with a Shift operator, you remove the rest of 0 that doesn't matter at the moment.

Example:

Let's do an AND operation with 4 (000 0010)

0100 1011 & 0000 0010 => 0000 0010

Now we need to filter the selected bit, in this case, was the second-bit reading right to left.

0000 0010 >> 1 => 1

The zeros on the left are no representative. So the output will be the bit we selected, in this case, the second one.

var word=75;
var res=[];
for(var x=7; x>=0; x--){
  res.push((word&Math.pow(2,x))>>x);
}
console.log(res);

The output:

Expected:

In case you need more than a simple number, you can apply the same function for a byte. Let's say you have a file with multiple bytes. So, you can decompose that file in a ByteArray, then each byte in the array in a BitArray.

Good luck!

Answer 7

@Commi's implementation is what I ended up using .

I believe there is a bug in this implementation. Bits on every 31st boundary give the wrong result. (ie when index is (32 * index - 1), so 31, 63, 95 etc.

I fixed it in the get() method by replacing > 0 with != 0.

get(n) {
    return (this.backingArray[n/32|0] & 1 << n % 32) != 0
}

The reason for the bug is that the ints are 32-bit signed. Shifting 1 left by 31 gets you a negative number. Since the check is for >0, this will be false when it should be true.

I wrote a program to prove the bug before, and the fix after. Will post it running out of space.

for (var i=0; i < 100; i++) {
  var ar = new bitArray(1000);
  
  ar.on(i);

  for(var j=0;j<1000;j++) {

    // we should have TRUE only at one position and that is "i". 
    // if something is true when it should be false or false when it should be true, then report it.

    if(ar.get(j)) {
      if (j != i) console.log('we got a bug at ' + i);
    } 

    if (!ar.get(j)) {
      if (j == i) console.log('we got a bug at ' + i);
    }
  }
}

Answer 8

2022

We can implement a BitArray class which behaves similar to TypedArrays by extending DataView. However in order to avoid the cost of trapping the direct accesses to the numerical properties (the indices) by using a Proxy, I believe it's best to stay in DataView domain. DataView is preferable to TypedArrays these days anyway as it's performance is highly improved in recent V8 versions (v7+).

Just like TypedArrays, BitArray will have a predetermined length at construction time. I just include a few methods in the below snippet. The popcnt property very efficiently returns the total number of 1s in BitArray. Unlike normal arrays popcnt is a highly sought after functionality for BitArrays. So much so that Web Assembly and even modern CPU's have a dedicated pop count instruction. Apart from these you can easily add methods like .forEach(), .map() etc. if need be.

class BitArray extends DataView{

  constructor(n,ab){
    if (n > 1.5e10) throw new Error("BitArray size can not exceed 1.5e10");
    super(ab instanceof ArrayBuffer ? ab
                                    : new ArrayBuffer(Number((BigInt(n + 31) & ~31n) >> 3n))); // Sets ArrayBuffer.byteLength to multiples of 4 bytes (32 bits)
  }

  get length(){
    return this.buffer.byteLength << 3;
  }

  get popcount(){
    var m1  = 0x55555555,
        m2  = 0x33333333,
        m4  = 0x0f0f0f0f,
        h01 = 0x01010101,
        pc  = 0,
        x;
    for (var i = 0, len = this.buffer.byteLength >> 2; i < len; i++){
       x = this.getUint32(i << 2);
       x -= (x >> 1) & m1;             //put count of each 2 bits into those 2 bits
       x = (x & m2) + ((x >> 2) & m2); //put count of each 4 bits into those 4 bits
       x = (x + (x >> 4)) & m4;        //put count of each 8 bits into those 8 bits
       pc += (x * h01) >> 56;
    }
    return pc;
  }

  // n >> 3 is Math.floor(n/8)
  // n & 7 is n % 8

  and(bar){
    var len = Math.min(this.buffer.byteLength,bar.buffer.byteLength),
        res = new BitArray(len << 3);
    for (var i = 0; i < len; i += 4) res.setUint32(i,this.getUint32(i) & bar.getUint32(i));
    return res;
  }

  at(n){  
    return this.getUint8(n >> 3) & (1 << (n & 7)) ? 1 : 0;
  }
  
  or(bar){
    var len = Math.min(this.buffer.byteLength,bar.buffer.byteLength),
        res = new BitArray(len << 3);
    for (var i = 0; i < len; i += 4) res.setUint32(i,this.getUint32(i) | bar.getUint32(i));
    return res;
  }
  
  not(){
    var len = this.buffer.byteLength,
        res = new BitArray(len << 3);
    for (var i = 0; i < len; i += 4) res.setUint32(i,~(this.getUint32(i) >> 0));
    return res;
  }

  reset(n){
    this.setUint8(n >> 3, this.getUint8(n >> 3) & ~(1 << (n & 7)));
  }

  set(n){
    this.setUint8(n >> 3, this.getUint8(n >> 3) | (1 << (n & 7)));
  }

  slice(a = 0, b = this.length){
    return new BitArray(b-a,this.buffer.slice(a >> 3, b >> 3));
  }

  toggle(n){
    this.setUint8(n >> 3, this.getUint8(n >> 3) ^ (1 << (n & 7)));
  }

  toString(){
    return new Uint8Array(this.buffer).reduce((p,c) => p + ((BigInt(c)* 0x0202020202n & 0x010884422010n) % 1023n).toString(2).padStart(8,"0"),"");
  }
  
  xor(bar){
    var len = Math.min(this.buffer.byteLength,bar.buffer.byteLength),
        res = new BitArray(len << 3);
    for (var i = 0; i < len; i += 4) res.setUint32(i,this.getUint32(i) ^ bar.getUint32(i));
    return res;
  }
}

Just do like

var u = new BitArray(12);

I hope it helps.

Answer 9

Probably [definitely] not the most efficient way to do this, but a string of zeros and ones can be parsed as a number as a base 2 number and converted into a hexadecimal number and finally a buffer.

const bufferFromBinaryString = (binaryRepresentation = '01010101') =>
    Buffer.from(
        parseInt(binaryRepresentation, 2).toString(16), 'hex');

Again, not efficient; but I like this approach because of the relative simplicity.

Answer 10

Thanks for a wonderfully simple class that does just what I need.

I did find a couple of edge-case bugs while testing:

get(n) {
    return (this.backingArray[n/32|0] & 1 << n % 32) != 0
    // test of > 0 fails for bit 31
}

forEach(callback) {
    this.backingArray.forEach((number, container)=>{
        const max = container == this.backingArray.length-1 && this.length%32
            ? this.length%32 : 32;
            // tricky edge-case: at length-1 when length%32 == 0,
            // need full 32 bits not 0 bits
    for(let x=0; x<max; x++) {
        callback((number & 1<<x)!=0, 32*container+x) // see fix in get()
    }
})

My final implementation fixed the above bugs and changed the backArray to be a Uint8Array instead of Array, which avoids signed int bugs.