Encontrar cadena de bits consecutiva de 1 o 0

¿Cómo encontrar la longitud de la cadena de bits consecutiva más larga (1 o 0)?

00000000 11110000 00000000 00000000 -> Si es 0, la longitud será 20

11111111 11110000 11110111 11111111 -> Si es 1, la longitud será 12

Lo siguiente se basa en el concepto de que si usted AND una secuencia de bits con una versión modificada de sí mismo, está eliminando efectivamente el 1 final de una fila de 1 consecutivos.

  11101111 (x) & 11011110 (x << 1) ---------- 11001110 (x & (x << 1)) ^ ^ | | trailing 1 removed 

La repetición de este N veces reducirá cualquier secuencia con N consecutivos de 1 a 0x00 .

Entonces, para contar el número de 1 consecutivos:

 int count_consecutive_ones(int in) { int count = 0; while (in) { in = (in & (in << 1)); count++; } return count; } 

Para contar el número de 0 consecutivos, simplemente invierte y la misma rutina.

 int count_consecutive_zeros(int in) { return count_consecutive_ones(~in); } 

Prueba de concepto: http://ideone.com/Z1l0D

 int main(void) { printf("%d has %d consecutive 1's\n", 0, count_consecutive_ones(0)); printf("%d has %d consecutive 0's\n", 0, count_consecutive_zeros(0)); /* 00000000 11110000 00000000 00000000 -> If it is 0 then length will be 20 */ printf("%x has %d consecutive 0's\n", 0x00F00000, count_consecutive_zeros(0x00F00000)); /* 11111111 11110000 11110111 11111111 -> If it is 1 then length will be 12 */ printf("%x has %d consecutive 1's\n", 0xFFF0F7FF, count_consecutive_ones(0xFFF0F7FF)); } 

Salida:

 0 has 0 consecutive 1's 0 has 32 consecutive 0's f00000 has 20 consecutive 0's fff0f7ff has 12 consecutive 1's 

Una forma simple sería simplemente hacer un bucle en los bits, y hacer un seguimiento del número de bits en una fila que han tenido el mismo valor, y el máximo que este valor ha alcanzado.

Aquí hay una función C simple que hace esto:

 int num_conseq_matching_bits(int n) { int i, max, cur, b, prevb; prevb = n & 1; /* 0th bit */ cur = 1; max = 1; for(i=1; i<32; i++) { b = (n >> i) & 1; /* get the i'th bit's value */ if(b == prevb) { cur += 1; if(cur > max) max = cur; } else { cur = 1; /* count self */ prevb = b; } } return max; } 

Puedes formar una tabla de consulta para hacerlo rápidamente por ti. Cuanto más grande sea la mesa, más rápida será la búsqueda. Las tablas de entrada de 2×256 pueden hacer 8 bits a la vez con un poco de twiddling. Agregue una versión 1s de la tabla y comience a agregar entradas. Probablemente así es como lo haría.

Para usar la idea de la mesa, necesitas algo como

 static struct { int lead; /* leading 0 bits */ int max; /* maximum 0 bits */ int trail; /* trailing 0 bits */ } table[256] = { ....data.... }; int mostConsecutiveBits(unsigned char *str, int length, bool count_ones) { int max = 0; /* max seen so far */ int trail = 0; /* trailing 0s from previous bytes */ while (length-- > 0) { int byte = *str++; if (count_ones) byte ^= 0xff; if (table[byte].max > max) max = table[byte].max; if (trail + table[byte].lead > max) max = trail + table[byte].lead; if (byte) trail = table[byte].trail; else trail += 8; } return max; } 

la inicialización de la tabla es sencilla, pero depende de su ordenación de bits y bytes (little endian o big endian).

Ya que no escribió qué es una cadena de bits (int regular, matriz de bytes o cadena de caracteres, asumí que es una matriz de caracteres).

 int maxConsBits(char *pStr,char cChar) { char curChar; int curMax = 0; int max = 0; while (pStr) { if (*pStr == cChar) { curMax++; if (curMax > max) { max = curMax; } } else { curMax = 0; } pStr++; } return max; } 

Publicación desde iPhone con grandes dedos.

Si son unos, entonces inviertan.

Bucle sobre la entrada utilizando una función de leadz. Para cada iteración, desplace la entrada hacia la izquierda. Continúa hasta llegar al final de la entrada. Tenga en cuenta que necesita comparar la longitud de entrada original con los conteos acumulados de leadz.

Además, como optimización, puede abortar pronto cuando la longitud de entrada restante sea menor que la mayor ventaja que haya visto.

Hay muchos algoritmos de leadz rápidos en línea.

No estoy de acuerdo con la idea de las tablas, porque la estaba probando y me di cuenta de que aunque “BA” en ASCII contendría 5 0 consecutivos para ‘B’ y 5 0 consecutivos para ‘A’, no se sumrán para 10 0 consecutivos. De hecho, habría 5 máximos consecutivos. (Esto fue en referencia a un simple “recuento de bits en una idea de tabla”. Chris Dodd ha expuesto desde entonces cómo se puede usar una tabla con precisión).

Yo usaría un algoritmo como este:

 #include  #include  using namespace std; // Assumes Little Endian architecture int mostConsecutiveBits(char str[], int length) { int currentConsecutiveBits=0; int maxConsecutiveBits=0; char currentBit; char lastBit=0; char currentChar=str[0]; int charCtr,bitCtr; for (charCtr=length-1; charCtr>=0; charCtr--) { currentChar=str[charCtr]; for (bitCtr=0; bitCtr<8; bitCtr++) { currentBit=currentChar & 1; if (currentBit!=lastBit) { maxConsecutiveBits=max(maxConsecutiveBits,currentConsecutiveBits); currentConsecutiveBits=1; lastBit=currentBit; } else { currentConsecutiveBits++; } currentChar=currentChar>>1; } maxConsecutiveBits=max(maxConsecutiveBits,currentConsecutiveBits); } return maxConsecutiveBits; } int main (int argc, char * const argv[]) { cout << mostConsecutiveBits("AB",2); return 0; } 

En este algoritmo, asumo que el flujo de bits se representa como caracteres de 8 bits. Para cada personaje, veo el último bit con un bit AND. Si es el mismo que el último bit, entonces subo el conteo de bits consecutivos, de lo contrario, reinicio el conteo porque los bits ya no son consecutivos. Luego uso una operación de cambio a nivel de bits para mover el siguiente bit en el carácter para observación. ¡Espero que esto ayude!

Mi respuesta es efectivamente un duplicado de la respuesta de David Underhill. 🙂

Si solo está buscando una cadena de bytes de cuatro bytes, puede empaquetarlos en un unsigned long y usar un algoritmo como este:

 int CountConsecutiveOnes(unsigned long n) { unsigned long m = n; int k = 0; while (m) { ++k; n >>= 1; m &= n; } return k; } 

Para el conteo de ceros, primero se toma el complemento bit a bit.

Si necesita contar cadenas de bytes más largas que cuatro, simplemente puede implementar las operaciones x >>= 1 y x & y directamente en las cadenas de bytes o puede ser más eficiente usar cadenas de caracteres unsigned long por lo que el control de arrastre en el La implementación de x >>= 1 no es demasiado costosa.

Puede ayudarlo … Primero convierta su número binario a String, digamos bits. Te dará el número máximo de 1 consecutivos (en java)

 String[] split = bits.split("0"); Arrays.sort(split); int maxLength = split[split.length - 1].length(); 
 public static int maxConsecutiveOneInBinaryNumber(int number) { int count = 0; int max = 0; while (number != 0) { if ((number & 1) == 1) { count++; } else { max = Math.max(count, max); count = 0; } number = number >> 1; } return Math.max(count, max); } 

Puede obtener este código aquí: https://github.com/VishalSKumar/DSFiddle/blob/master/src/main/java/com/vishalskumar/hackerrank/MaxConsecutiveOneInBinary.java