BitSet.js
BitSet.js is an infinite Bit-Array (aka bit vector, bit string, bit set) implementation in JavaScript. Infinite means that if you invert a bit vector, the leading ones get remembered. As far as I can tell, BitSet.js is the only library which has this feature. It is also heavily benchmarked against other implementations and is the most performant implementation to date.
Examples
###Basic usage
let bs = new BitSet;
bs.set(128, 1);
console.log(bs.toString(16));
###Flipping bits
let bs = new BitSet;
bs
.flip(0, 62)
.flip(29, 35);
let str = bs.toString();
if (str === "111111111111111111111111111000000011111111111111111111111111111") {
console.log("YES!");
}
###Range Set
let bs = new BitSet;
bs.setRange(10, 18, 1);
###User permissions
If you want to store user permissions in your database and use BitSet for the bit twiddling, you can start with the following Linux-style snippet:
let P_READ = 2;
let P_WRITE = 1;
let P_EXEC = 0;
let user = new BitSet;
user.set(P_READ);
user.set(P_WRITE);
let group = new BitSet(P_READ);
let world = new BitSet(P_EXEC);
console.log("0" + user.toString(8) + group.toString(8) + world.toString(8));
##Installation
npm install bitset
or
bower install bitset.js
##Using BitSet.js with the browser
<script src="bitset.js"></script>
<script>
console.log(BitSet("111"));
</script>
##Using BitSet.js with require.js
<script src="require.js"></script>
<script>
requirejs(['bitset.js'],
function(BitSet) {
console.log(BitSet("1111"));
});
</script>
##Constructor
The default BitSet
constructor accepts a single value of one the following types :
- String
- Binary strings :
new BitSet("010101")
- Binary strings with prefix :
new BitSet("0b010101")
- Hexadecimal strings with prefix
new BitSet("0xaffe")
- Array
- The values of the array are the indices to be set to 1 :
new BitSet([1,12,9])
- Uint8Array
- A binary representation in 8 bit form
- Number
- BitSet
- A BitSet object, which get copied over
##Functions
The data type Mixed can be either a BitSet object, a String or an integer representing a native bitset with 31 bits.
###BitSet set(ndx[, value=1])
Mutable; Sets value 0 or 1 to index ndx
of the bitset
int get(ndx)
Gets the value at index ndx
###BitSet setRange(from, to[, value=1])
Mutable; Helper function for set, to set an entire range to a given value
###BitSet clear([from[, to]])
Mutable; Sets a portion of a given bitset to zero
- If no param is given, the whole bitset gets cleared
- If one param is given, the bit at this index gets cleared
- If two params are given, the range is cleared
###BitSet slice([from[, to]])
Immutable; Extracts a portion of a given bitset as a new bitset
- If no param is given, the bitset is getting cloned
- If one param is given, the index is used as offset
- If two params are given, the range is returned as new BitSet
###BitSet flip([from[, to]])
Mutable; Toggles a portion of a given bitset
- If no param is given, the bitset is inverted
- If one param is given, the bit at the index is toggled
- If two params are given, the bits in the given range are toggled
###BitSet not()
Immutable; Calculates the bitwise complement
###BitSet and(Mixed x)
Immutable; Calculates the bitwise intersection of two bitsets
###BitSet or(Mixed x)
Immutable; Calculates the bitwise union of two bitsets
###BitSet xor(Mixed x)
Immutable; Calculates the bitwise xor between two bitsets
###BitSet andNot(Mixed x)
Immutable; Calculates the bitwise difference of two bitsets (this is not the nand operation!)
###BitSet clone()
Immutable; Clones the actual object
###Array toArray()
Returns an array with all indexes set in the bitset
###String toString([base=2])
Returns a string representation with respect to the base
###int cardinality()
Calculates the number of bits set
###int msb()
Calculates the most significant bit (the left most)
###int ntz()
Calculates the number of trailing zeros (zeros on the right). If all digits are zero, Infinity
is returned, since BitSet.js is an arbitrary large bit vector implementation.
###int lsb()
Calculates the least significant bit (the right most)
###bool isEmpty()
Checks if the bitset has all bits set to zero
###bool equals()
Checks if two bitsets are the same
###BitSet.fromBinaryString(str)
Alternative constructor to pass with a binary string
###BitSet.fromHexString(str)
Alternative constructor to pass a hex string
###BitSet.Random([n=32])
Create a random BitSet with a maximum length of n bits
##Iterator Interface
A BitSet
object is iterable. The iterator gets all bits up to the most significant bit. If no bits are set, the iteration stops immediately.
let bs = BitSet.Random(55);
for (let b of bs) {
console.log(b);
}
Note: If the bitset is inverted so that all leading bits are 1, the iterator must be stopped by the user!
##Coding Style
As every library I publish, BitSet.js is also built to be as small as possible after compressing it with Google Closure Compiler in advanced mode. Thus the coding style orientates a little on maxing-out the compression rate. Please make sure you keep this style if you plan to extend the library.
##Building the library
After cloning the Git repository run:
npm install
npm run build
##Run a test
Testing the source against the shipped test suite is as easy as
npm run test
Copyright and licensing
Copyright (c) 2025, Robert Eisele
Licensed under the MIT license.