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

Question

Perhaps you can help me with the following problem, which can help me speed up the work of the memory manager that I think about (I'm not sure if there is a solution - I did not find it).

I have a 32 bit register, and I need to find if there are n consecutive bits in it, and if so, what is their offset. For example, if the register has the following value 11110000000000000000000111111111000, and n is 4, any of the following answers will be accepted (offsets begin from 0):

3, 4, 5, 6, 28

The atomic operations that I have are all the usual bitwise operations (&, |, ~, ...), as well as the search for the least significant bit offset (3 in the register above). The algorithm (if it exists) - should occupy no more than 5 atomic operations.

Answer 1

for each possible byte value (0-255) calculates the number of bits at the beginning, the number of bits at the end and the largest number of consecutive bits within the byte and the offset of this sequence. For example, for 0x11011101 at the beginning there are 2 bits, 1 bit at the end and a sequence of 3 consecutive bits in it.

Store these values ​​in 4 arrays, for example start , end , longest , longest_offset .

Then, consider a 32-bit number as an array of 4 bytes and move on to the following bytes as follows:

 int search_bit_sequence(uint32 num, int desired) { unsigned char *bytes = (unsigned char *)&num; int i, acu; for (acu = i = 0; i < 4; i++) { int byte = bytes[i]; acu += start[byte]; if (acu >= desired) return (i * 8 - (acu - start[byte])); if (longest[byte] >= desired) return ( i * 8 + longest_offset[byte]); if (longest[byte] < 8) acu = end[byte]; } return -1; /* not found */ } 

update : note that the endpoint of your processor may require a change in the direction of the loop.

Answer 2

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

EDIT

Here is an elegant solution to a similar problem Quoting through bits into an integer, ruby, finding the length of a sequence of longes 1 .

If you know the length n race that you are looking for in advance, for this algorithm only steps n required. Then the offset can be restored from the number of trailing zeros in the previous step of the algorithm in about 5 steps. This is not very efficient, but probably better than an end-to-end solution, especially for small n .

EDIT 2

If n known in advance, we can determine the sequence of necessary shifts for it. For instance. if we are looking for 7-bit runs, then we will have to do

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

The fact is that we shift the right n/2 bits if n is equal to or 1, if n is odd, and then update n accordingly (either n = n - 1 or n = n / 2 ), as @harold suggests. It would be expensive to evaluate these values ​​on the fly, but if we pre-calculate them, it will be quite effective.

EDIT 3

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

Answer 3

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

For specific values ​​of m, it can be further optimized.

For example, for m == 4, you can simply 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, it just comes down to factorization of m.

Update

Please also note that at higher values ​​it may be cheaper to just check the sequence of bits in any possible position.

For example, for m = 23, a pattern can start only from positions 0 to 9.

Answer 4

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

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

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

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

Now that we have only one bit, we need to find the position of the bit. We can use the 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 . Thus, the general procedure is as follows.

 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 about the big endian. I think I just need to change get_set_position () for big-endian to make it work (assuming that changes to the definition of consecutive bit sets are based on endian-ness).

Let me share the verified 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 runs O (1) times because 32 is constant (as @Qnan noted). Again, it works in O (n) if the register size changes.

Note. I fixed bugs thanks to comments and unit testing.