Is there a way to get the inverse of a bitset?

[arnoldrobbins]

Looking at the headers, I don't see an easy way to invert a bitset. The equivalent of the C ~ operator.

We have an application that needs to do LHS |= RHS and also LHS |= ~ RHS. The latter doesn't look doable with CRoaring. Can that be added?

Thanks!

[Dr-Emann]

There is roaring_bitmap_flip (and closed/in place versions), which take a range, so to roaring_bitmap_t *inverted_rhs = roaring_bitmap_flip_closed(RHS, 0, UINT32_MAX) may be what you want.

[lemire]

@Dr-Emann has the correct answer:

/**
 * Compute the negation of the bitmap in the interval [range_start, range_end).
 * The number of negated values is range_end - range_start.
 * Areas outside the range are passed through unchanged.
 */
roaring_bitmap_t *roaring_bitmap_flip(const roaring_bitmap_t *r1,
                                      uint64_t range_start, uint64_t range_end);

/**
 * Compute the negation of the bitmap in the interval [range_start, range_end].
 * The number of negated values is range_end - range_start + 1.
 * Areas outside the range are passed through unchanged.
 */
roaring_bitmap_t *roaring_bitmap_flip_closed(const roaring_bitmap_t *x1,
                                             uint32_t range_start,
                                             uint32_t range_end);

so to roaring_bitmap_t *inverted_rhs = roaring_bitmap_flip_closed(RHS, 0, UINT32_MAX) may be what you want.

I suspect not because this full range up to UINT32_MAX might insert 4 billions 1-bits in your bitmap... which is a lot. Typically, if a bit reversal is what you really need, you have a reasonable universe size... E.g., in the case of the C operator, the universe size might be 32 or 64. So if your bitmaps are in the range from 0 to 1000000, you do roaring_bitmap_flip(RHS, 0, 1000000). That's sensible.

I am going to close this issue as the functionality is already present.

[Dr-Emann]

Will also note, thanks to range containers, fully inverting an empty bitmap will "only" involve 65k full range containers, but yeah, you can do a lot better if you have a defined max that you actually care about.

Will also also note, LHS |= ~RHS is much less common than LHS &= ~RHS, which is available as a single efficent operation, roaring_bitmap_andnot_inplace

[arnoldrobbins]

@Dr-Emann and @lemire Thank you both for this. This is exactly what I need. The range I'm working on is 0 to less than 1,200,000, so I don't need anywhere near UNIT32_MAX.

I'm hoping that CRoaring will be useful; I plan to try to try it out today. Thanks again!