Faster IntSet by using BitMaps in the lower branches

Henning Thielemann lemming at
Sun Sep 18 23:05:25 CEST 2011

On Sun, 18 Sep 2011, Joachim Breitner wrote:

> I’d like to avoid the binary search, as it is more expensive for dense
> sets. Milan’s suggestion of shifts by 6 might be a good compromise.
> Another approach might be to first use lowestBitSet to start with the
> lowest bit. In case of only one bit set, it will not iterate further
> then.

If lowestBitSet is a fast CPU instruction you can iterate through all bits 
by clearing the lowest set bit after visit and call lowestBitSet again. 
However, I am not aware of such a machine instruction on x86.

More information about the Libraries mailing list