infusion/bitset.js

An arbitrary size Bit-Vector implementation in JavaScript

bitset.js's Issues

NPM is pointing to the old version 3.1.0 instead of 4.0.0

Bower installs the old version of this library due to the npm repository having the 3.1 version. You're bower and package files are updated to 4, so I think you just need to republish to npm.

A `size()` method

Thanks for this library! In my testing, it is almost as fast as the one shipped with Java.

I need a way to know how big the bitset is. size() or count() or something like that.

This might be because the forEach() is still lacking, but I am not sure

Benchmarks

Hey, the README mentions that this library has been benchmarked against other libraries:

[this library] is also heavily benchmarked against other implementations and is the most performant implementation to date.

The benchmarks don't seem to be included in the repository. Is there some way to find the source code for the benchmarks, and the results from them?

The typescript type declaration does not match the structure of the actual module

In the typescript declaration, BitSet is declared as a class inside the module :

https://github.com/infusion/BitSet.js/blob/master/bitset.d.ts#L202

Which would mean it would have to be used this way :

import { BitSet } from "bitset";

However, in the code itself, BitSet is declared as the module itself :

https://github.com/infusion/BitSet.js/blob/master/bitset.js#L1002

import BitSet from "bitset";

So, the result is that :

• import { BitSet } from "bitset" results in a runtime error (SyntaxError: The requested module 'bitset' does not provide an export named 'BitSet') and
• import BitSet from "bitset" results in a type error at new BitSet (This expression is not constructable. Type 'typeof import(".../node_modules/bitset/bitset")' has no construct signatures.).

How to use this most efficiently?

Hi,

I want to store 214 bits in a BitSet.
When i do that it's data array is 10 elements. That's 10x 32bit int (320 bit).
Ideally it would use the bare minimum in bit overhead. If that were to be done in 32 bit ints then 7 ints (224 bit) would suffice.
More ideal would be an array of chars (8 bit each) where i'd need 27 chars giving me 216 bits of room.

Are there arguments i can set in this class to get that more ideal behavior (ints or chars, both work)?

New Functions

• forEach((value, index, bitset) => foo)

Usabiliity...

For the most part, I like BitSet however, (taking a clue from "Prototype the User Experience"), I think the usability could be increased if you made the following changes:

1. All mathematical operations are immutable operations, which return back a new BitSet object.
2. All other function, those that changes the object, are mutable. (E.g. Set(), SetRange(), Clear(), and (perhaps) Flip()).

The reason for this is simple, I want to change the actual BitSet when I'm performing an operation directly on the object. However, like Math, operations like: 'and', 'or', "not' etc don't change the lhs or the rhs operands; they just return a new result value. Likewise, BitSet should do the same.

I just spent 20 minutes tracking down a very subtle but because I forget to assign the return value from a Set operation to itself.

This code feel very natural: permissions.set(Read)
This doesn't feel natural: permissions = permission.set(Read)

Hope that helps.

Length of the bitset

Hello,

How "long" so to speak can the bitset be? I am considering a leap into JavaScript, React, Node, etc, and along with that, will need some sort of extensible bitset. Should be able to support arbitrary length bitsets, complete with bitwise operations, serialization to/from string, bit as well as hex or even base-n representation. Serialization might be pushing it, but it does need to be extensible. Wondering if this is that?

Might be similar along these lines. I see, for instance, that there are to/fromHex methods.

Thank you...

Minification tool

Hi!

I want to extend your lib, and here is my question: how you minify it?
To be clear, I know how to minify code, but i want to be consistent with how you do it with your lib. You are not providing any building script.

Base 36 constructor

Hello, For input, you have 0b101010101010 and 0xa6e etc etc..

You have the ability to do const b36 = BitSet('10101010110101010101010101010').toString(36)
But not sure how to get it back in const bs = BitSet(b36)

I am sure you are gonna say it's not possible.. but I just wanted to confirm that something like BitSet(b36, 36) didn't exist?

Misleading comments on [im]mutable functions

In bitset.js, and the .d.ts in #27, the comments for the bitwise operators include "The result is stored in-place".

I see that the Readme.md does show the correct immutable description, but the inline documentation should either be kept up to date, too, or remove it.

affected functions: and, or, andNot, not, xor

Memory usage

Hello,

First of all, bitset.js is a really useful tool. Thanks for your efforts.

My question is about memory usage of a BitSet. I assume that a BitSet is as large as of its MSB. Let's say we have a BitSet whose 300,000,000th bit is set as 1, remaining are zero. We need to allocate 300M bits, right? If so, total size should be around ~35.7 MB. However, when I execute this scenario (set 300Mth bit as 1), BitSet size is calculated as 194.5 MB. I use an npm package object-sizeof to do that. I naturally don't expect it to allocate exactly 300M bits, instead a close number which is better for memory management. But the difference is huge. So, which is correct? Do I misunderstand something?

Thanks.

Webpack compatible version

Hi,

This is a great lib, especially the infinite length feature.

Is it possible to get a published version that is compatible with webpack using ES5 exports?

Many thanks!

Feature request -- inline mutable version of bit vector

I understand that the current version of bitset returns a new copy of bitset for every bit op. Isn't it costly, especially for large bitsets to get a new object? Can we have an inline version please...?

iterator: syntax error in IE

• OS: Windows 10 Pro
• Browser: Internet Explorer 11 (and emulation back through 7 and 5)

Error encountered:

SCRIPT1028: Expected identifier, string or number
bitset.js (911,5)

which points to the following line:

[Symbol.iterator]: function () {

I wasn't familiar with this as valid JS syntax, but some Googling helped me discover it's called a "computed property name" and that IE doesn't support it. I'm aware that IE is largely obsolete with Microsoft's promotion of Edge, but it still exists and does function as a modern browser for the most part. Could you switch to alternate syntax for adding the iterator? Many thanks!

As we can construct a bitset object by a Buffer, Can we convert the bitset to Buffer

As we can construct a bitset object by a Buffer, Can we convert the bitset to Buffer

let bitset = require("bitset");
let buf = Buffer.from([100, 97, 98]);
let bs = bitset(buf);
bs.toString();
'11000100110000101100100'

Can we convert a bitset into buffer?
let bs1 = new bitset();
bs1.setRange(4,9,1);
{ data: [ 1008, 0, 0, 0, 0, 0, 0, 0, 0, 0 ], _: 0 }
bs1.toString();
'1111110000'

Now can this be converted into the buffer?
eg. add the padding 0's left and make it's size multiple of 8 then convert to byte array or Buffer.

It Appears that a Simple Test is Failing...

We are trying to understand your library, so we wrote a very simple test and didn't get the results we were expecting. Are we doing something wrong?

_The Test:_

var bs1 = new BitSet("101");
var ss = bs1.toString(); // expecting "101", actual "101" Note: bs1 = {length=1, [0]=5}
var a = bs1.get(1);      // expecting 0, actual 0
var b = bs1.get(2);      // expecting 1, actual 1

var bs2 = new BitSet("111");
ss = bs2.toString();    // expecting "111", actual "111" Note: bs2 = {length=1, [0]=7}

var bs3 = bs2.clear(1);
ss = bs3.toString();     // expecting "101", actual "1" Note: bs3 = {length=2, [0]=1,[1]=0}
var c = bs3.get(1);      // expecting 0, actual 0
var d = bs3.get(2);      // expecting 1, actual 0
var t = bs3.equals(bs1); // expecting true, actual false

Why is bs3's length equal to 2? If we understand things correctly, we believe length should be 1 and [0] should be 5.

Shifts

Would you consider adding or accepting a PR with bit shifts? Or am I missing it?

Initializing a new BitSet using a byte[]

We have permission data stored as a byte[], can BitSet be initialized with a byte[]? If so, what would the syntax look like? something like: var bs = new BitSet(bitarray);

And if not, how would we implement it?

Q: TypeScript Definition file?

Do you have a TypeScript Definition file? If not, I have a good start on one.

Also, any plans on porting to TypeScript? If so (or not) my guys are thinking about porting it anyway. If they end up porting it, would you like a pull request?

Unexpected Results

I was trying to use this library to push to the client-side a few things that were being done server-side with either Java's BitSet or C#'s BitArray. Unfortunately, I've found some of the results did not match the values I'd expect.

For example, I have a Uint8Array of [ 240, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 127, 255, 31 ,0 ,0]. When I check the toArray() it shows the first 'flipped' bit to be at index 8 (should be 4) and the indices 13, 14, and 15 to be set to 0 with quite a few more down the line that don't match the Java or C# response to the dame byte array.

If the data is completely zero, then count leading zeros and count trailing zeros should return the word size

I'm working on fixed size bitsets, and I create a 64 bit bitset by doing: new BitSet(new Uint8Arrray(4)).

When calling ntz() on this object, it returns Infinity, IMO it should return the size of the bitmap which in this case is 64.

If the word is zero (no bits set), count leading zeros and count trailing zeros both return the number of bits in the word, while ffs returns zero. Both log base 2 and zero-based implementations of find first set generally return an undefined result for the zero word.
https://en.wikipedia.org/wiki/Find_first_set#Algorithms

While ffs is something that could return Infinity.

Documentation problem with "set" function

The README for the set function says that if the value is not specified, it defaults to zero. In fact, the value defaults to 1.
I think the implementation is correct, given the name of the function, and the documentation should be changed.

fromHex() and toHex() util methods

Hi, it would be nice to have fromHex() and toHex() methods as once we've the BitSet instance, sometimes we may want to persist that into Hex and decode that hex into BitSet later.

Array parser

I might be mis-reading the documentation, but as I understand, the following two objects should be equivalent:

let a = new BitSet([34]).not()
let b = new BitSet().set(34,1).not()

however they are not:

a.get(80)  // returns 0, not what I expected
b.get(80)  // returns 1

[Question] Optimized for large ranges of the same value?

Does this library optimize large ranges of the same value?

For example, if 1 million bits are marked true, then 1 million false, then one million true, is this internally represented using ranges to compress the information and optimize lookups?

Can such a format be exported/imported to/from JSON?

Perhaps there is another better suited data structure for this purpose?

Thank you.

Symbol.iterator is missing from the TypeScript types

[Symbol.iterator] is missing from the .d.ts file, which meaning that

[...BitSet()]

results in a type error.

Why is isEmpty false even when all bits are set to 0?

a = new bs(new Uint8Array(32 / 8 - 1)).flip()
for (i = 0; i < 32; ++i) {
  a.set(i, 0);
}
a.isEmpty() // false?