BitSet.js: Arbitrary-Size Bit Vectors

BitSet.js is a compact bit-vector library for JavaScript. It stores bits in an array of 32-bit words, grows beyond the range of native bitwise operators, and preserves an infinite run of leading ones after a complement. The package works in Node.js and browsers and includes CommonJS, ESM, and TypeScript declarations.

Why Native Bitwise Operators Are Not Enough

JavaScript numbers are normally IEEE-754 double-precision values, but the ordinary bitwise operators first convert their operands to signed 32-bit integers. All 32 bits participate in the operation; the sign bit is not lost. The practical limitation is that the result is still a fixed-width signed integer, and shift counts are reduced modulo 32:

1 << 8;   // 256
1 << 40;  // 256 again, because 40 modulo 32 is 8
1 << 31;  // -2147483648

That behavior is useful for compact flags, but it cannot address bit 40, 128, or 10,000 independently. BitSet.js maps index i to word i >>> 5 and bit i & 31. A high index therefore selects another 32-bit word instead of wrapping into the first one.

Installation

npm install bitset

The npm package is named bitset. Version 5.2.3 provides equivalent ESM and CommonJS entry points:

import BitSet from 'bitset';

const bits = new BitSet();

const BitSet = require('bitset');

const bits = new BitSet();

The browser build is available as dist/bitset.min.js in the package and exposes the global BitSet constructor.

Set and Read Bits

Indexes start at zero. set() defaults to one and returns the same object, so several mutations can be chained:

const flags = new BitSet()
  .set(0)
  .set(31)
  .set(32)
  .set(128);

console.log(flags.get(128));       // 1
console.log(flags.cardinality());  // 4
console.log(flags.toArray());      // [0, 31, 32, 128]

Setting a bit to zero is equivalent to clearing it:

flags.set(31, 0);
flags.clear(32);

console.log(flags.toArray()); // [0, 128]

setRange(from, to, value), clear(from, to), and flip(from, to) use inclusive endpoints. Omitting both arguments from clear() empties the set; omitting them from flip() complements every bit, including the infinite leading region.

const window = new BitSet();

window.setRange(10, 18);
window.clear(14);
window.flip(18);

console.log(window.toArray());
// [10, 11, 12, 13, 15, 16, 17]

Constructor Input

The constructor accepts binary or hexadecimal strings, an array of set indexes, a byte array, a native number, or another BitSet:

new BitSet('101001');          // Binary string
new BitSet('0b101001');        // Explicit binary string
new BitSet('0x29');            // Hexadecimal string
new BitSet([0, 3, 5, 128]);    // Set these indexes
new BitSet(new Uint8Array([0x29]));
new BitSet(41);                // The numeric value 41
new BitSet(existingBits);      // Clone another BitSet

The distinction between a numeric value and an index is important. new BitSet(128) represents the number 128 and therefore sets bit 7. To set bit 128, use new BitSet([128]) or new BitSet().set(128).

Boolean Set Operations

Bitwise operations correspond directly to set operations. Unlike the mutation methods above, these methods return a new BitSet and leave both operands unchanged:

const left = new BitSet([1, 3, 5]);
const right = new BitSet([2, 3, 4]);

console.log(left.and(right).toArray());    // [3]
console.log(left.or(right).toArray());     // [1, 2, 3, 4, 5]
console.log(left.xor(right).toArray());    // [1, 2, 4, 5]
console.log(left.andNot(right).toArray()); // [1, 5]

console.log(left.toArray());               // Still [1, 3, 5]

Infinite Complements

A normal finite array cannot distinguish between "all unallocated high bits are zero" and "all unallocated high bits are one." BitSet.js stores that state separately. Complementing a finite set flips its stored words and changes the leading-bit state to one:

const selected = new BitSet([0, 2]);
const excluded = selected.not();

console.log(excluded.get(0));        // 0
console.log(excluded.get(1));        // 1
console.log(excluded.get(10000));    // 1
console.log(excluded.cardinality()); // Infinity
console.log(excluded.toString());    // Begins with "...1111"

This is a genuine infinite set of non-negative bit indexes, not merely a finite word mask. Consequently, cardinality() and msb() return Infinity. The iterator over an inverted set also never terminates unless the caller stops it. Avoid spreading such a set into an array or using an unbounded for...of loop.

Queries and Serialization

slice(from, to) creates a new zero-based BitSet from an inclusive source range. Both fromBinaryString() and fromHexString() are explicit alternatives to prefixed strings, and Random(n) creates at most n random bits. For an empty set, msb() and ntz() return Infinity.

const packetFlags = BitSet.fromHexString('a501');
const lowByte = packetFlags.slice(0, 7);

console.log(lowByte.toString(16)); // 1
console.log(packetFlags.toString(2));
// 1010010100000001

The default iterator yields each bit value from index zero through the highest meaningful bit; it does not yield only the set indexes:

console.log([...new BitSet('101')]); // [1, 0, 1]

Example: Permissions Beyond 32 Flags

A bit vector is useful when every permission has a stable integer index and the set is dense enough to justify a compact bitmap:

const permission = {
  read: 0,
  write: 1,
  exportData: 75,
};

const editor = new BitSet([
  permission.read,
  permission.write,
]);

const exporter = editor.clone().set(permission.exportData);

function can(role, capability) {
  return role.get(capability) === 1;
}

console.log(can(editor, permission.exportData));   // false
console.log(can(exporter, permission.exportData)); // true

Persist a finite set as a binary or hexadecimal string when the storage layer must preserve indexes beyond its native integer width. Keep a stable mapping from permission names to indexes, and never interpret a client-supplied bitmap as authorization without checking it against server-side policy.

Example: A Small Sieve

Bit vectors also represent dense membership tables efficiently. Here a set bit means "composite":

function primesUpTo(limit) {
  const composite = new BitSet();

  for (let candidate = 2; candidate * candidate <= limit; candidate++) {
    if (composite.get(candidate) === 0) {
      for (
        let multiple = candidate * candidate;
        multiple <= limit;
        multiple += candidate
      ) {
        composite.set(multiple);
      }
    }
  }

  const primes = [];
  for (let value = 2; value <= limit; value++) {
    if (composite.get(value) === 0) primes.push(value);
  }
  return primes;
}

console.log(primesUpTo(30));
// [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

The same dense-membership idea appears in a Bloom filter, where several hash functions map values to bit positions and membership is probabilistic.

Complexity and Limits

BitSet.js is a dense bit vector. Access to an already allocated word is constant time, while first setting a distant index must grow and initialize every intervening 32-bit word. Storage through index n is therefore proportional to n / 32, and whole-set Boolean operations are proportional to the larger allocated word count. A sparse set of a few enormous indexes is better represented by a Set or another sparse structure.

The implementation coerces indexes through JavaScript's 32-bit integer operations, so use non-negative integer indexes and avoid values near the language and array limits. BitSet.js is not a replacement for BigInt arithmetic: it models independently addressable bits and set operations, while BigInt models an integer value with arithmetic operators.

References

• [ECMA262]Ecma International, ECMAScript Language Specification: Number Type and numeric bitwise operations.
• [Warren2013]Henry S. Warren, Jr., Hacker's Delight, 2nd edition, Addison-Wesley, 2013.