Finding consecutive run from a starting point

[grovesNL]

Hi! 👋 Is there a way to find consecutive runs of 1 or 0 given a starting point? It looks like I could implement this manually by indexing bits one at a time, but I was wondering if there was a more efficient way to do this (especially taking of instructions like trailing/leading zeros or population count while iterating through blocks for example).

Ideally it could search lower, higher, or bidirectionally (the case I'm most interested in).

For example, starting at bit 4, search lower and higher bits to find how many consecutive 1s we can find in this run. If bit 4 is set to 0, then the run length is 0. If bits 3, 4, 5, 6, 7 are all set to 1, then the run length would be 5.

In case it's helpful for context, the same idea was requested in roaring-rs #274.

[grovesNL]

Here's what I have so far:

master...grovesNL:fixedbitset:count-consecutive-ones

It seems like it's working well so far, but I'll be testing it a lot more over the next couple days. The idea is to scan each block using (trailing/leading zeros/ones) with some careful handling around the end depending on the search direction. Any feedback would be great!

I'd also like to allow these runs to use branchless u64::leading_zeros when lzcnt isn't explicitly enabled (https://www.reddit.com/r/rust/comments/1dmprs0/branchless_u64leading_zeros_on_x86/) so I could include that if there's interest.

[grovesNL]

Probably not going to pursue this for now because I couldn't get this to run as fast as I'd like, will reopen if I revisit it later