By allocating from a different block for different sizes. This means the bitmap only needs one bit per element, not per byte and reduces fragmentation. You can

By allocating from a different block for different sizes. This means the bitmap only needs one bit per element, not per byte and reduces fragmentation. You can keep the number of blocks small by limiting the allocation sizes to a number of pre-defined buckets. From what I remember jemalloc uses bitmaps for small allocations (below the 4 KiB page size) but switches to different data structures for medium and large allocations.