Skip to content

Instantly share code, notes, and snippets.

@binarymax
Last active October 24, 2023 11:08
Show Gist options
  • Star 4 You must be signed in to star a gist
  • Fork 2 You must be signed in to fork a gist
  • Save binarymax/ab3e917c170ca95268e5 to your computer and use it in GitHub Desktop.
Save binarymax/ab3e917c170ca95268e5 to your computer and use it in GitHub Desktop.
Javascript bitmap data structure
//------------------------------------------
//Compact bitmap datastructure
//Memory efficient array of bool flags
var Bitmap = function(size){
this._cols = 8;
this._shift = 3;
this._rows = (size>>this._shift)+1;
this._buf = new ArrayBuffer(this._rows);
this._bin = new Uint8Array(this._buf);
};
//Gets the bool at offset
Bitmap.prototype.get = function(off){
var row = off>>this._shift;
var col = off%this._cols;
var bit = 1<<col;
return (this._bin[row]&bit)>0;
};
//Sets a bit at offset to bool
Bitmap.prototype.set = function(off,bool){
var row = off>>this._shift;
var col = off%this._cols;
var bit = 1<<col;
if (bool) {
this._bin[row] |= bit;
} else {
bit = 255 ^ bit;
this._bin[row] &= bit;
}
};
//Flip a single bit at offset
Bitmap.prototype.flip = function(off){
var row = Math.floor(off/this._cols);
var col = off%this._cols;
var bit = 1<<col;
this._bin[row] ^= bit;
};
//Reset to all 1's
Bitmap.prototype.fill = function() {
for(var i=0;i<this._rows;i++) {
this._bin[i] = 255;
}
};
//Reset to all 0's
Bitmap.prototype.clear = function() {
for(var i=0;i<this._rows;i++) {
this._bin[i] = 0;
}
};
//Example - gets a list of Primes using the Sieve of Eratosthenes
//Returns a function to check if a number is prime or not
var getSieveOfEratosthenes = function(size) {
var bits = new Bitmap(size);
bits.fill();
bits.set(0,0);
var lim = Math.ceil(Math.sqrt(size));
for(var i=2;i<=lim;i++) {
if(bits.get(i)){
for(var j=i*i;j<=size;j+=i) {
bits.set(j,0);
}
}
};
return function(n){ return bits.get(n); };
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment