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