¿Cómo encontrar si hay n bits establecidos consecutivos en un búfer de 32 bits?

Tal vez pueda ayudarme con el siguiente problema que puede ayudarme a acelerar un administrador de memoria en el que estoy pensando (no estoy seguro de que exista una solución, no encontré una).

Tengo un registro de 32 bits y necesito encontrar si hay n bits establecidos consecutivos en él y, de ser así, cuál es su compensación. Por ejemplo, si el registro tiene el siguiente valor 1111000000000000000000001111111000 y n es igual a 4, se acepta cualquiera de las siguientes respuestas (las compensaciones comienzan desde 0):

3, 4, 5, 6, 28

Las operaciones atómicas que tengo son todas las operaciones bit a bit regulares (&, |, ~, …) y también encontrar el desplazamiento de bit menos significativo (3 en el registro anterior). El algoritmo (suponiendo que exista) no debe tomar más de 5 operaciones atómicas.

Solución del problema

Si hay un algoritmo que hace eso, entonces la complejidad del peor de los casos es al menos O(m-n), donde mes el número de bits en el registro y nes el número de bits de conjunto consecutivos que está buscando. Esto es fácil de ver porque si todos los bits están configurados, su algoritmo tendrá que generar m-nelementos exactos, por lo que su complejidad no puede ser menor.

EDITAR

Hay una solución elegante para un problema similar aquí Recorriendo bits en un número entero, ruby ​​, encontrando la longitud de la 1secuencia longes.

Si sabe nde antemano la duración de la carrera que está buscando, este algoritmo requerirá solo npasos. Luego, el desplazamiento se puede recuperar a partir del número de ceros finales en el preúltimo paso del algoritmo en aproximadamente 5 pasos más. Eso no es extremadamente eficiente, pero probablemente sea mejor que la solución de bucle, especialmente para un pequeño archivo n.

EDITAR 2

Si nse conoce de antemano, podemos calcular una secuencia de turnos necesarios para ello. Por ejemplo, si estamos buscando ejecuciones de 7 bits, entonces tendríamos que hacer

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

El punto es que cambiamos los n/2bits a la derecha si nes par o por 1 si nes impar, luego actualizamos nen consecuencia (cualquiera n = n - 1 or n = n / 2), como sugiere @harold. Estimar estos valores sobre la marcha sería costoso, pero si los calculamos previamente, será bastante eficiente.

EDITAR 3

Aún mejor, para cualquier n, se requerirían pasos exactos ceil(log(2,n)), sin importar el turno que tomemos, siempre que sea entre floor(n/2)y 2^floor(log(2,n-1)). Vea los comentarios a continuación.