fast-bitset



A fast bitset with some nice methods.

##Features
- Outperforms all other bitset packages in terms of speed and space
- All bit operations execute in O(1) time (does not iterate through bits)
- Useful methods for graph algorithms
- Any array that stores booleans can safely be replaced by a bitset for improved speed
- Uses 64x less space than a nontyped array

##Installation
npm install fast-bitset --save

##License
MIT

##API

* BitSet
* new BitSet(nBitsOrKey)
* .get(idx) ⇒ boolean
* .set(idx) ⇒ boolean
* .setRange(from, to) ⇒ boolean
* .unset(idx) ⇒ boolean
* .unsetRange(from, to) ⇒ boolean
* .toggle(idx) ⇒ boolean
* .toggleRange(from, to) ⇒ boolean
* .clear() ⇒ boolean
* .clone() ⇒ BitSet
* .dehydrate() ⇒ string
* .and(bsOrIdx) ⇒ BitSet
* .or(bsOrIdx) ⇒ BitSet
* .xor(bsOrIdx) ⇒ BitSet
* .forEach(func)
* .getCardinality() ⇒ number
* .getIndices() ⇒ Array
* .isSubsetOf(bitset) ⇒ Boolean
* .isEmpty() ⇒ boolean
* .isEqual(bs) ⇒ boolean
* .toString() ⇒ string
* .ffs(_startWord) ⇒ number
* .ffz(_startWord) ⇒ number
* .fls(_startWord) ⇒ number
* .flz(_startWord) ⇒ number
* .nextSetBit(idx) ⇒ number
* .nextUnsetBit(idx) ⇒ number
* .previousSetBit(idx) ⇒ number
* .previousUnsetBit(idx) ⇒ number

$3

Create a new bitset. Accepts either the maximum number of bits, or a dehydrated bitset

| Param | Type | Description |
| --- | --- | --- |
| nBitsOrKey | number | string | Number of bits in the set or dehydrated bitset. For speed and space concerns, the initial number of bits cannot be increased. |

$3

Check whether a bit at a specific index is set

Kind: instance method of BitSet
Returns: boolean - true if bit is set, else false

| Param | Type | Description |
| --- | --- | --- |
| idx | number | the position of a single bit to check |

$3

Set a single bit

Kind: instance method of BitSet
Returns: boolean - true if set was successful, else false

| Param | Type | Description |
| --- | --- | --- |
| idx | number | the position of a single bit to set |

$3

Set a range of bits

Kind: instance method of BitSet
Returns: boolean - true if set was successful, else false

| Param | Type | Description |
| --- | --- | --- |
| from | number | the starting index of the range to set |
| to | number | the ending index of the range to set |

$3

Unset a single bit

Kind: instance method of BitSet
Returns: boolean - true if set was successful, else false

| Param | Type | Description |
| --- | --- | --- |
| idx | number | the position of a single bit to unset |

$3

Unset a range of bits

Kind: instance method of BitSet
Returns: boolean - true if set was successful, else false

| Param | Type | Description |
| --- | --- | --- |
| from | number | the starting index of the range to unset |
| to | number | the ending index of the range to unset |

$3

Toggle a single bit

Kind: instance method of BitSet
Returns: boolean - true if set was successful, else false

| Param | Type | Description |
| --- | --- | --- |
| idx | number | the position of a single bit to toggle |

$3

Toggle a range of bits

Kind: instance method of BitSet
Returns: boolean - true if set was successful, else false

| Param | Type | Description |
| --- | --- | --- |
| from | number | the starting index of the range to toggle |
| to | number | the ending index of the range to toggle |

$3

Clear an entire bitset

Kind: instance method of BitSet
Returns: boolean - true

$3

Clone a bitset

Kind: instance method of BitSet
Returns: BitSet - an copy (by value) of the calling bitset

$3

Turn the bitset into a comma separated string that skips leading & trailing 0 words.
Ends with the number of leading 0s and MAX_BIT.
Useful if you need the bitset to be an object key (eg dynamic programming).
Can rehydrate by passing the result into the constructor

Kind: instance method of BitSet
Returns: string - representation of the bitset

$3

Perform a bitwise AND on 2 bitsets or 1 bitset and 1 index.
Both bitsets must have the same number of words, no length check is performed to prevent and overflow.

Kind: instance method of BitSet
Returns: BitSet - a new bitset that is the bitwise AND of the two

| Param | Type | Description |
| --- | --- | --- |
| bsOrIdx | BitSet | Number | a bitset or single index to check (useful for LP, DP problems) |

$3

Perform a bitwise OR on 2 bitsets or 1 bitset and 1 index.
Both bitsets must have the same number of words, no length check is performed to prevent and overflow.

Kind: instance method of BitSet
Returns: BitSet - a new bitset that is the bitwise OR of the two

| Param | Type | Description |
| --- | --- | --- |
| bsOrIdx | BitSet | Number | a bitset or single index to check (useful for LP, DP problems) |

$3

Perform a bitwise XOR on 2 bitsets or 1 bitset and 1 index.
Both bitsets must have the same number of words, no length check is performed to prevent and overflow.

Kind: instance method of BitSet
Returns: BitSet - a new bitset that is the bitwise XOR of the two

| Param | Type | Description |
| --- | --- | --- |
| bsOrIdx | BitSet | Number | a bitset or single index to check (useful for LP, DP problems) |

$3

Run a custom function on every set bit. Faster than iterating over the entire bitset with a get()
Source code includes a nice pattern to follow if you need to break the for-loop early

Kind: instance method of BitSet

| Param | Type | Description |
| --- | --- | --- |
| func | function | the function to pass the next set bit to |

$3

Get the cardinality (count of set bits) for the entire bitset

Kind: instance method of BitSet
Returns: number - cardinality

$3

Get the indices of all set bits. Useful for debugging, uses forEach internally

Kind: instance method of BitSet
Returns: Array - Indices of all set bits

$3

Checks if one bitset is subset of another. Same thing can be done using _and_ operation and equality check,
but then new BitSet would be created, and if one is only interested in yes/no information it would be a waste of memory
and additional GC strain.

Kind: instance method of BitSet
Returns: Boolean - true if provided bitset is a subset of this bitset, false otherwise

| Param | Type | Description |
| --- | --- | --- |
| bs | BitSet | a bitset to check |

$3

Quickly determine if a bitset is empty

Kind: instance method of BitSet
Returns: boolean - true if the entire bitset is empty, else false

$3

Quickly determine if both bitsets are equal (faster than checking if the XOR of the two is === 0).
Both bitsets must have the same number of words, no length check is performed to prevent and overflow.

Kind: instance method of BitSet
Returns: boolean - true if the entire bitset is empty, else false

| Param | Type |
| --- | --- |
| bs | BitSet |

$3

Get a string representation of the entire bitset, including leading 0s (useful for debugging)

Kind: instance method of BitSet
Returns: string - a base 2 representation of the entire bitset

$3

Find first set bit (useful for processing queues, breadth-first tree searches, etc.)

Kind: instance method of BitSet
Returns: number - the index of the first set bit in the bitset, or -1 if not found

| Param | Type | Description |
| --- | --- | --- |
| _startWord | number | the word to start with (only used internally by nextSetBit) |

$3

Find first zero (unset bit)

Kind: instance method of BitSet
Returns: number - the index of the first unset bit in the bitset, or -1 if not found

| Param | Type | Description |
| --- | --- | --- |
| _startWord | number | the word to start with (only used internally by nextUnsetBit) |

$3

Find last set bit

Kind: instance method of BitSet
Returns: number - the index of the last set bit in the bitset, or -1 if not found

| Param | Type | Description |
| --- | --- | --- |
| _startWord | number | the word to start with (only used internally by previousSetBit) |

$3

Find last zero (unset bit)

Kind: instance method of BitSet
Returns: number - the index of the last unset bit in the bitset, or -1 if not found

| Param | Type | Description |
| --- | --- | --- |
| _startWord | number | the word to start with (only used internally by previousUnsetBit) |

$3

Find first set bit, starting at a given index

Kind: instance method of BitSet
Returns: number - the index of the next set bit >= idx, or -1 if not found

| Param | Type | Description |
| --- | --- | --- |
| idx | number | the starting index for the next set bit |

$3

Find first unset bit, starting at a given index

Kind: instance method of BitSet
Returns: number - the index of the next unset bit >= idx, or -1 if not found

| Param | Type | Description |
| --- | --- | --- |
| idx | number | the starting index for the next unset bit |

$3

Find last set bit, up to a given index

Kind: instance method of BitSet
Returns: number - the index of the next unset bit <= idx, or -1 if not found

| Param | Type | Description |
| --- | --- | --- |
| idx | number | the starting index for the next unset bit (going in reverse) |

$3

Find last unset bit, up to a given index

Kind: instance method of BitSet
Returns: number - the index of the next unset bit <= idx, or -1 if not found

| Param | Type | Description |
| --- | --- | --- |
| idx | number | the starting index for the next unset bit (going in reverse) |