Needless Patchouli Manufacture

    bitset

    5.1.1 • Public • Published

    BitSet.js

    NPM Package

    Build Status MIT license

    BitSet.js is an infinite Bit-Array (aka bit vector, bit string, bit set) implementation in JavaScript. That 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); // Set bit at position 128
    console.log(bs.toString(16)); // Print out a hex dump with one bit set

    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); // Set a 1 between 10 and 18, inclusive

    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; // Bit pos
    let P_WRITE = 1;
    let P_EXEC  = 0;
     
    let user = new BitSet;
    user.set(P_READ); // Give read perms
    user.set(P_WRITE); // Give write perms
     
    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
      • A binary value
    • 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=0])

    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.

    Build the library

    Gulp is optional for minifying with Google Closure Compiler. After cloning the Git repository, do:

    npm install
    gulp
    

    Run a test

    Testing the source against the shipped test suite is as easy as

    npm test
    

    Copyright and licensing

    Copyright (c) 2014-2018, Robert Eisele Dual licensed under the MIT or GPL Version 2 licenses.

    Install

    npm i bitset

    DownloadsWeekly Downloads

    3,791

    Version

    5.1.1

    License

    MIT OR GPL-2.0

    Unpacked Size

    71.5 kB

    Total Files

    11

    Last publish

    Collaborators

    • infusion