cuenta el número de bits de grupo cero en un número

Question

¿Cómo se cuenta el número de bits de un grupo cero en un número? los bits de grupo son cualquier cero o uno consecutivos, por ejemplo, 2 se representa como como ... 0000000000000000010 tiene dos grupos de cero bits el menor bit significativo y el grupo comienza después de uno. Además, estoy en una mala necesidad de algoritmos de bits de manipulación en su caso uno tiene una referencia, por favor compartir

Answer 1

Aquí hay algunas maneras divertidas de hacerlo. Los # define-s al principio son solo para poder expresar las entradas de funciones en notación binaria. Las dos funciones que hacen el trabajo son variaciones sobre un tema: el primero usa una secuencia de Bruijn y una tabla de búsqueda para averiguar cuántos ceros finales hay en el parámetro, y hace el resto en consecuencia.El segundo usa una tabla Mod37 para hacer lo mismo, que es muy similar en concepto pero implica una operación de módulo en lugar de una multiplicación y un cambio de bit. Uno de ellos es más rápido. Demasiado perezoso para descubrir cuál.

Este es un código mucho más que la solución obvia. Pero esto puede ser muy eficaz si tiene principalmente ceros en la entrada, ya que solo requiere una iteración de bucle (solo una rama, en realidad) para cada 1 bit, en lugar de una iteración de bucle para cada bit.

#define HEX__(n) 0x##n##LU 

#define B8__(x) ((x&0x0000000FLU)? 1:0) \ 
       +((x&0x000000F0LU)? 2:0) \ 
       +((x&0x00000F00LU)? 4:0) \ 
       +((x&0x0000F000LU)? 8:0) \ 
       +((x&0x000F0000LU)? 16:0) \ 
       +((x&0x00F00000LU)? 32:0) \ 
       +((x&0x0F000000LU)? 64:0) \ 
       +((x&0xF0000000LU)?128:0) 

#define B8(d) ((unsigned char)B8__(HEX__(d))) 

#define B16(dmsb,dlsb) (((unsigned short)B8(dmsb)<<8) + B8(dlsb)) 

#define B32(dmsb,db2,db3,dlsb) (((unsigned long)B8(dmsb)<<24) \ 
           + ((unsigned long)B8(db2)<<16) \ 
           + ((unsigned long)B8(db3)<<8) \ 
           + B8(dlsb)) 

unsigned int count_zero_groups_debruijn(unsigned int v) 
{ 
    // number of zero-bit groups (set to 1 if high-bit is zero) 
    unsigned int g = (~(v & 0x80000000)) >> 31; 

    // lookup table for deBruijn 
    static const int _DeBruijnTable[32] = 
    { 
     0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 
     31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9 
    }; 

    do { 
     // get number of trailing zeros in v 
     int tz = _DeBruijnTable[((v & -v) * 0x077CB531U) >> 27]; 
     // increment zero group count if more than 1 trailing zero 
     g += (tz > 0) * 1; 
     // shift out trailing zeros and the preceding 1 
     v = v >> (tz+1); 
    } while (v); 

    return g; 
} 

unsigned int count_zero_groups_mod37(unsigned int v) 
{ 
    // number of zero-bit groups (set to 1 if high-bit is zero) 
    unsigned int g = (~(v & 0x80000000)) >> 31; 

    // lookup table for mod37 
    static const int _Mod37Table[] = 
    { 
     0, 0, 1, 26, 2, 23, 27, 0, 3, 16, 24, 30, 28, 11, 0, 13, 4, 
     7, 17, 0, 25, 22, 31, 15, 29, 10, 12, 6, 0, 21, 14, 9, 5, 20, 
     8, 19, 18 
    }; 

    do { 
     // get number of trailing zeros in v 
     int tz = _Mod37Table[(v & -v) % 37]; 
     // increment zero group count if more than 1 trailing zero 
     g += (tz > 0) * 1; 
     // shift out trailing zeros and the preceding 1 
     v = v >> (tz+1); 
    } while (v); 

    return g; 
} 

int main(int argc, char* argv[]) 
{ 
    printf("zero groups: %d (should be 6)\n", count_zero_groups_debruijn(B32(10011001,10000000,00001001,00010011))); 
    printf("zero groups: %d (should be 6)\n", count_zero_groups_debruijn(B32(10011001,10000000,00001001,00010000))); 
    printf("zero groups: %d (should be 6)\n", count_zero_groups_debruijn(B32(00011001,10000000,00001001,00010001))); 
    printf("zero groups: %d (should be 6)\n", count_zero_groups_debruijn(B32(00011001,10000000,00001001,00010000))); 
    printf("zero groups: %d (should be 0)\n", count_zero_groups_debruijn(B32(11111111,11111111,11111111,11111111))); 
    printf("zero groups: %d (should be 1)\n", count_zero_groups_debruijn(B32(00000000,00000000,00000000,00000000))); 
    printf("zero groups: %d (should be 6)\n", count_zero_groups_mod37 (B32(10011001,10000000,00001001,00010011))); 
    printf("zero groups: %d (should be 6)\n", count_zero_groups_mod37 (B32(10011001,10000000,00001001,00010000))); 
    printf("zero groups: %d (should be 6)\n", count_zero_groups_mod37 (B32(00011001,10000000,00001001,00010001))); 
    printf("zero groups: %d (should be 6)\n", count_zero_groups_mod37 (B32(00011001,10000000,00001001,00010000))); 
    printf("zero groups: %d (should be 0)\n", count_zero_groups_mod37 (B32(11111111,11111111,11111111,11111111))); 
    printf("zero groups: %d (should be 1)\n", count_zero_groups_mod37 (B32(00000000,00000000,00000000,00000000))); 
    return 0; 
} 

Answer 2

Usted puede utilizar repetidamente división entera y el operador de módulo para extraer los bits, y realizar un seguimiento de los grupos dentro de tu lazo Suena como una pregunta para la tarea, por lo que no estoy seguro de la cantidad de un servicio que le hace para darle una solución completa? Tenga en cuenta que puede utilizar este algoritmo para obtener la representación en base 2 de un entero positivo (De hecho, funciona con cualquier base> = 2):

int example = 40; 
while (example > 0) { 
    printf("%d\n", example % 2); 
    example /= 2; 
} 

Esto imprimirá los bits en orden inverso (es decir , comenzando desde el menos significativo). A partir de aquí no hay mucho trabajo por hacer para contar los grupos que desea contar. ¿Debo ir más lejos o puedes tomarlo desde aquí?

Answer 3

Éstos son algunos consejos para usted:

• if (x & 1) {...} comprueba si se establece el bit menos significativo de x;
• x >>= 1 desplaza el valor de x un bit hacia la derecha;
• tenga en cuenta los números negativos cuando realiza la manipulación de bits.

Answer 4

La manera más simple es contar el número de transiciones de uno a cero en el bucle utilizando el desplazamiento de una máscara de bits junto con la operación de bit `y '. También es necesario verificar el primer bit y aumentar la cantidad obtenida en uno si es 0.

Answer 5

La solución de Andrew es sin duda la más simple de diseñar e implementar, pero no puedo evitar preguntarme si hay una solución más rápida usando Máscaras de bits más grandes.

En una entrevista de trabajo me pidieron que escribiera un código para identificar el bit más significativo. Después de pasar unos minutos con una búsqueda binaria ultrarrápida ultra rápida utilizando máscaras de bits cada vez más pequeñas, que de repente me di cuenta de que podía optimizar aún más y obtener una gran cantidad de garabatos en muchos trozos de papel, el examinador me miró en blanco y me preguntó si sabía cómo usar un bucle for.

Tal vez debería haberme pedido que use un bucle for para resolver el problema.

De todos modos no es imposible que exista una solución similar similar aquí.

Answer 6

probar este código prueba Didnt ella .. así que me dejó saber si usted encuentra algún error

num es la entrada.

int main() 
{ 
    int count = 0; 

    int num = 0xF0000000, mask = 1; /*size of mask and num should be same. */ 

    int i; 
    int flag= 1; 


    i = sizeof(num) * 8; 

    while(--i) { 
     if(flag && !(num & mask)) { 
      count++; 
      flag = 0; 
     } 
     else if(num & mask) 
      flag = 1; 

    mask = mask<<1; 
} 

printf("\n%d\n",count); 
} 

Thanks 
cexpert 
http://learnwithtechies.com