How to find if there are n consecutive set bits in a 32 bit buffer?

Question

Maybe you can help me with the following problem that can help me speed a memory manager I am thinking of (I am not sure a solution exists – I did not find one).

I have a 32 bits register and I need to find if there are n consecutive set bits in it, and if so what is their offset. For example if the register holds the following value 111100000000000000000001111111000 and n equals to 4 – any of the following answer is accepted (offsets starts from 0):

3, 4, 5, 6, 28

The atomic operations I have are all the regular bitwise operations (&, |, ~, …) and also finding the least significant bit offset (3 in the register above). The algorithm (assuming one exists) – should take no more than 5 atomic operations.

Answer 1

If there is an algorithm that does that, then the worst case complexity is at least O(m-n), where m is a the number of bits in the register and n is the number of consecutive set bits you are looking for. This is easy to see because if all bits are set, your algorithm will have to output exactly m-n items, so it's complexity cannot be any lower.

EDIT

There's an elegant solution to a similar problem here Looping through bits in an integer, ruby, finding the length of the longes 1 sequence.

If you know the length n of the run you're looking for in advance, this algorithm will require only n steps. The offset can then be recovered from the number of trailing zeroes in the pre-last step of the algorithm in about 5 more steps. That's not extremely efficient, but probably better than the loop-through solution, especially for a small n.

EDIT 2

If the n is known in advance, we can figure out a sequence of necesary shifts for it. E.g. if we are looking for 7 bit runs, then we'd have to do

x &= x >> 1
x &= x >> 3
x &= x >> 1
x &= x >> 1

The point is that we shift right n/2 bits if n is even or by 1 if n is odd, then update n accordingly (either n = n - 1 or n = n / 2), as @harold suggests. Estimating these values on the fly would be expensive, but if we pre-calculate them then it's going to be pretty efficient.

EDIT 3

Even better, for any n, exactly ceil(log(2,n)) steps would be required, no matter which shift we take, as long as it is between floor(n/2) and 2^floor(log(2,n-1)). See comments below.