How do I create bit array in Javascript?

Question

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

Huntingdon

Can you please describe the problem you're facing? – Sard

there's no problem. it's just for learning purposes. – Huntingdon

You might be able to mimic a bit array, but I believe each array element is still stored in bytes, thus you won't get the memory benefit. – Aurie

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.

Philology

+1. But could you,please, comment your methods?? and what is .ctor?? – Huntingdon

You should absolutely add the methods to BitArray.prototype instead of this. – Fouts

and you shouldn't reassign all this each time the constructor function is invoked. See the edit I submitted. – Fouts

@DrStrangeLov - .ctor is just the code that fires when the instance is constructed - kind of a pseudo quick and dirty constructor. Goes with the quick and dirty nature of the whole class ... – Philology

@Daniel Baulig - just giving the guy something quick and useful to make his life easier, though I appreciate your attention to detail. Can you point me in the right direction for viewing the edits you submitted? I'd be glad to incorporate them if they improve the code but I'm unclear on what edits/where they were submitted... – Philology

In the alert you should probably put the MyBitArray.toNumber() before the .toString(), since the user is going from dec to bin. – Aurie

Since I do not have edit privileges, my edits must be peer reviewd before they are mad publicly available. I edited your post to use proper object oriented javascript patterns, somebody will have to review the edit. My first edited seems to have been lost (propably due to conflicting edits by yourself), so I made the changes again. – Fouts

@Daniel Baulig - check this fiddle jsfiddle.net/GTVAy/36 - is this what you're talking about? maybe I should start a new question though about why prototyping matters if the class will not be subclassed ... :) – Philology

Yes, that is what I mean. It matters because else each BitArray will have it's own set of functions, which will be created with each calll to the constructor function. This will have impact on performance in various ways (eg. memory usage, worse JIT compilation, etc). Additionally I don't think you can know if anyone who uses your code might want to augment it's prototype or inherit from it, which both won't be easily possible when using this wrong object oriented patern. – Fouts

@Daniel Baulig - I just created a question for this - you should post your answer for others to see - esp if there's a perf consequence. Updating my code w/ your recommendations now ... – Philology

I am not able to find your question, please be so kind and provide me a direct link. – Fouts

@Daniel Baulig - here it is - #6974565 – Philology

@DanielBaulig let us continue this discussion in chat – Philology

in this line this.m_bits = BitArray.shred(bits).m_bits; You invoke BitArray.shred(bits) but why BitArray.shred(bits).m_bits; ?? how does this work?? – Huntingdon

@Huntingdon - because I'm invoking that within an instance's constructor. Since I can't say "this = BitArray.shred(x)" I say my private bit array is the same as the bit array (m_bits) that would be created by creating a new BitArray from number x. Make sense? – Philology

So, what is assigned to this.m_bits?? the result of BitArray.shred(bits) or value of m_bits ?? – Huntingdon

The value of m_bits FROM the result - BitArray.shred(bits).m_bits is not the same as this.m_bits. I'm assigning the array within result of the conversion to this.m_bits. – Philology

Would it be complicated to define 2 dimension bit array? Please advice. – Hastate

I know this answer is very old, but I feel that it's important to point out that this is not a bit array, but rather an array of "bits" – Losing

A bit array traditionally packs bits efficiently into memory, not storing boolean values which typically take 4 bytes = 3100% memory wasted. @Commi's answer handles this. – Voltmer

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

Closed

How would you handle it in widespread browsers like IE or Firefox 3.6? – Kirt

Firefox 3.6 should work fine. For IE, use a regular array and ensure that only integers go in. The bit masking would still work. – Closed

I would totally just ignore old browsers. If they are using an older browser, just tell the user, "Sorry, please download a real browser. Here are a couple links...". That would do the whole world some good =D – Closed

Should this be Uint8Array? You need to specify how many bits per element. UintArray doesn't exist today in Chrome. – Voltmer

Maybe Uint8ClampedArray would be better: it clamps numbers :) Just a note – Olenolin

Answer 3

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

Mannino

Answer 4

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.

Eure

Answer 5

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
*/

Growler

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. 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. – Anthelmintic

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!

Lorineloriner

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);
    }
  }
}

Anthelmintic

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.

Boxthorn

Kudos on the continued updates (I much prefer your approach to the other answers)! Any chance you could add Boolean operations to the array? And(), Not(), Or(), and Xor(), seem like pertinent additions. – Pyrotechnic

@Pyrotechnic Thanks. A big benefit of employing DataView is the flexibity to access data. If you employ BigInts you can even access in 64 bits at once and do any logical operation very efficiently though BigInts are somewhat slow in JS so I use 32 bit ops in popcnt and the ArrayBuffer size is arranged to be a multiple of 32 bits in size to begin with. However your request is a little ambigious. If you would like to apply a logical operation among two same sized BitArrays then just iterate over them 32 (or 64) bits apply the operator and store in a new BitArray instance. – Boxthorn

See en.wikipedia.org/wiki/Bit_array#Basic_operations. Boolean operations like and can be especially useful for quickly finding where two arrays have the same value. Likewise, an or will tell you if any of the bits is positive. This kind of operation is one of the reasons Matt Parker saw a 4 million percent speedup in his wordle challenge (see youtube.com/watch?v=c33AZBnRHks) – Pyrotechnic

@Pyrotechnic OK I have added the .and(), .or(), .xor() and .not() methods under the influence of a liter of cheap wine. Hopefully i haven't broken anything. :) My initial approach was 64 bits but as tested that at BitArray sizes like 1e5~1e6 the BigInt operations slow it down like ~7 times compared to 32 bits. Honestly I really can't really tell what's the big deal BigInts in JS. However, whatever... we best stay 32 bits in this quest. – Boxthorn

@Pyrotechnic One other point to mention is, once this mock up gets mature enough one can extend the BitArray to fixed size BitVector128, BitVector256 or BitVector512` classes having .leftShift(), .rightShift() methods and whatnot. It's performance is adequate. – Boxthorn

@Redu: Thank you, again, for composing this. I've been testing your code and have been making updates as I go. The first thing that pops out at me is that it doesn't support arbitrarily large arrays (currently locked to multiples of 32). As I make a habit to employ source control, I've started a repo on GitHub if you'd like to collaborate (github.com/Atriace/JSBitArray). I've included the commit history you made here, so if you parse the history you should see what I've changed. Currently, I think the popcount() is broken. – Pyrotechnic

@Pyrotechnic Yes, logical operations like and etc. also popcnt require 32 bits access for high performance. So it was handy to set the size at a multiple of 32 bits. However that's not my biggest concern. I was working on some other issues those manifest once the BitArray is huge. Too much bit twiddling is causing some issues once the size grows. Will be in touch on the repo side once i fix these. – Boxthorn

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.

Robison

This wouldn't work for very long strings of bits, only integers. – Polysyllable

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.

Manse