8
$\begingroup$

A well-known trick for storing bit vectors using uninitialized memory can allocate a bit vector of size $n$ in which all of the bits are set to $0$ by allocating $(2 n + 1)\lceil \lg n \rceil$ bits of memory and initializing only $\lceil \lg n \rceil$ of them. This representation supports setting and unsetting any bit in constant time.

This dates back to "Alfred Aho, John Hopcroft, and Jeffrey Ullman's 1974 book The Design and Analysis of Computer Algorithms . . . Chapter 2, exercise 2.12", "Jon Bentley's 1986 book Programming Pearls . . .Column 1, exercise 8; exercise 9 in the Second Edition", and "Preston Briggs and Linda Torczon's 1993 paper, 'An Efficient Representation for Sparse Sets'".

Dodis et al.'s "Changing Base without Losing Space" brings the space requirement down slightly to $\lceil (2 n + 1) \lg n \rceil + 1$ bits, though this algorithm requires the precomputation of $\Theta(\lg n)$ constants with $\Theta(\lg n)$ bits each.

How much space can be saved? Is there a representation of bit vectors in which

  • Bits can be set or unset in $O(1)$ time
  • Initializing a new bit vector of $0$s uses $o(n \lg n)$ bits of uninitialized memory and $O(\lg n)$ initialized memory
$\endgroup$
2
$\begingroup$

Yes, this can be done through bucketing. The representation in Briggs and Torczon can be used to store not just bits, but values associated with any set bits, by storing them next to the values in the dense array. For $k$-bit values, this leads to a total storage cost of $(2n+1)\lceil \lg n \rceil + kn$.

Now pick $k=\lceil \lg n \rceil$. Each $k$-bit value will represent a set of $\lceil \lg n \rceil$ contiguous bits in the bit array. We thus only need to track $\lceil n/\lceil \lg n \rceil \rceil$ of them with the dense and sparse arrays. This leads to a total cost of $\Theta(n)$ bits of storage, with $\Theta(\lg n)$ initialized bits.

Like the basic solution, this requires $O(1)$ operations on words of length $\Theta(\lg n)$ to set a single bit.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.