Succinct data structure for "bookkeeping problem"
Let's suppose that there the occupancy rate is 25%. Then given an array of $n$ elements, there are ${ n \choose 0.25n}$ possible bitmaps. The theoretical minimum number of bits per entry that you need is, then:

$$\lim_{n \rightarrow \infty}\frac{1}{n} \log_2 { n \choose 0.25n } \approx 0.81$$

At 5%, the minimum number is:

$$\lim_{n \rightarrow \infty}\frac{1}{n} \log_2 { n \choose 0.05n } \approx 0.29$$

Note that I didn't actually calculate it this way. I used the binomial entropy function:

$$B(p) = -\left(p \log_2 p + (1-p) \log_2 (1-p)\right)$$

Then $B(0.05) \approx 0.29$.

So given a 25% occupancy rate, there is no data structure which compresses better than 80% of the size of the uncompressed bitmap.

Given that it sounds like you have a real problem to solve, does shaving 20% off the size of the bitmap seem like a reasonable benefit, given that the cost is likely to be a much higher-constant-factor data structure?

Besides, 1kB just isn't that big. It's a fraction of a page in size, and likely to be in cache most of the time if this is really your inner loop.

EDIT

OK, if you really need this, I suspect that succinct hashing might be your best bet. There are dynamic bitmap data structures which support the rank operation, but none of them have constant time queries to my knowledge.