BooleanArray

💡 Ideas
1

ECMAScript has a good number of typed arrays now but I do not see one for working with a bits.

There mention of such in some meeting notes years ago but I haven't found more details on why it wasn't implemented (or maybe it was under a different name?):

MM: A Uint1Array or BooleanArray, where each element is one bit.

I'd like something to use like a BitSet in Java, etc. for finding first set bits, etc. as well as general purpose array of booleans.

1 Like
2

For dense resizable boolean arrays (C++ has a STL specialization of vector<bool> that's essentially just that and nothing else), you can usually get away with using a bigint and a few simple, relatively standard bit hacks to back such an array. (For fixed arrays, it's slightly more complicated, but only slightly, and in my experience the use cases are always somewhat niche.)

  • Read: (array >> BigInt(offset) & 1n) !== 0n
  • Set: array | (1n << BigInt(offset))
  • Clear: array & ~(1n << BigInt(offset))
  • Toggle: array ^ (1n << BigInt(offset))
  • Update: array & ~(1n << BigInt(offset)) | (BigInt(Boolean(value)) << BigInt(offset))
  • Push: update bit array + update length
  • Pop: extract value + clear bit array + update length
  • Shift: (array & 1n) !== 0n to extract + array >> 1n + update length to update length
  • Unshift: array << 1n | BigInt(Boolean(value)) + update length
  • Flip: ~array & ((1n << BigInt(length)) - 1)
    • Extra mask operation is to keep the main bit array normalized to positive.

And more advanced things also of course have their own relatively straightforward algorithms (though it'd be a great idea to add spec proposals for these), like for counting true values or finding the offset of the first true value.

2 Likes