Add find_first_unset_bit function

[fuine]

trafficstars

Hello, i would like to implement a function which would yield me the offset of the first unset bit. Something like find_first_unset_bit(&self) -> Option<usize>. I thought about making it more generic (giving it a binary value for which to search, but then i think it will end up as two different functions under the hood, because you want to test entire blocks with an if statement at the beginning -- something like

// we are searching for the first unset bit
for block in &self.data {
    if block != BLOCK::max_value() {
        // find exact id here
    }
}

in order to search for first set bit you'd need to change the value you are comparing block against to 0. I also thought that maybe this function could take a Range and try to find the first bit that is set/unset within the given range.

Simple example for the version without range/custom bit value:

let mut fb = FixedBitSet::with_capacity(30);
for i in 0..20 {
    fb.insert(i);
}
let next = fb.find_first_unset_bit();
assert_eq!(next, Some(20));

[mneumann]

@fuine Take a look at https://github.com/bluss/fixedbitset/pull/8. This is very similar, but iterates over the bits which are "set". Finding unset bits can be accomplished very similar. Basically you could take my code and simply invert the bits of each block. Care has to be taken for the last block, as it might contain bits which are not in the bitset. In general, I would recommend you to implement it as an iterator, which can be used like this:

let next = fb.unset_bit_iter().next();
assert_eq!(next, Some(20));

Also the u32::leading_zeros functions might be of interest to you.

[james7132]

This has moved quite a bit since 2016. As @mneumann mentioned, one can now use fb.zeroes().next() to get the first unset bit.