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

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.

Apologies for raising this from the dead, but I actually needed the generic algo where you know the number of bits, M, ahead of time.

The comments in a very good answer: (https://stackoverflow.com/a/12053749/2963099) led me to realize that a C++ recursive solution would be sufficient to calculate a O(log(M)) where M is the number of consecutive bits being searched as follows:

#include <bit> #include <cstdint> template <int BITS> struct consecutive_bits { static int ones(uint64_t b) { b &= b >> BITS/2; return consecutive_bits<BITS-BITS/2>::ones(b); } static int zeros(uint64_t b) { return ones(~b); } }; template <> struct consecutive_bits<1> { static int ones(uint64_t b) { return std::countr_zero(b); } static int zeros(uint64_t b) { return ones(~b); } }; 

(You can see it on Compiler Explorer: https://godbolt.org/z/9PWbYWYoW )

The asm is quite simple, using 7 as an example (and setting -march=haswell):

mov rax, rdi shr rax, 3 and rax, rdi mov rdx, rax shr rdx, 2 and rdx, rax mov rax, rdx shr rax and rax, rdx tzcnt rax, rax ret 

From the line breaks I added, it seems clear that it is O(M) with K being 3 asm lines: MOV, SHR, AND

The link posted by Qnan shows an elegant solution to the general case.

For particular values of m it could be further optimized.

For instance, for m == 4, you can just do:

x &= (x >> 1); x &= (x >> 2); // at this point, the first bit set in x indicates a 4 bit set sequence. 

For m == 6 :

x &= (x >> 1); x &= (x >> 1); x &= (x >> 3); 

In the end, that just reduces to factoring m.

update

Note also, that for high values of, it may actually be cheaper to just check for the bit sequence at every possible position.

For instance, for m = 23, the pattern can only start at positions from 0 to 9.

I checked this question and answers and came up with following idea.

int i = n-1; uint32_t y = x; while(y && i--) { y = y & (y << 1); }; 

After above operation y is nonzero if there is n consecutive set bits. The next thing to do is to find the least significant value set there. The following code will strip all the set bits except the least significant.

z = y - (y & (y-1)); 

Now that we have only one bit set, we need to find the position of the bit. We can use switch statement with 32 cases.

static inline int get_set_position(const uint32_t z) { switch(z) { case 0x1: return 0; case 0x2: return 1; .... .... // upto (1<<31) total 32 times. } return -1; } 

Finally to get the result we need to reduce n-1. So the total procedure is the following.

static inline int get_set_n_position(const uint32_t x, const uint8_t n) { if(!n) return -1; int i = n-1; uint32_t y = x; while(y && i--) { y = y & (y << 1); }; if(!y) return -1; uint32_t z = y - (y & (y-1)); if(!z) return -1; int pos = get_set_position(z); if(pos < 0) return -1; assert(pos >= (n-1)); return pos - (n-1); } 

Now there is concern for big-endian. I think I just need to change the get_set_position() for big-endian to make it work(assuming the consecutive set bits definition changes based on endian-ness).

Let me share a tested code that uses builtin_ctzl provided by gcc.

OPP_INLINE int get_set_n_position(BITSTRING_TYPE x, const uint8_t n) { if(!n || n > BIT_PER_STRING) return -1; int i = n-1; while(x && i--) { x = x & (x << 1); }; if(!x) return -1; int pos = __builtin_ctzl(x); return pos - (n-1); } 

The code works in O(1) time because 32 is constant(as @Qnan noticed). Again it works in O(n) if the size of register vary.

Note: I fixed the bugs, thanks to comments and unit-testing.