Nombre de zéros dans la représentation binaire d'un entier

Le moyen simple de le faire est d'itérer chaque bit de la représentation binaire du nombre, de tester la valeur de chaque bit et de compter le nombre d'entre eux zéro. Une boucle serait beaucoup plus claire que la récursion pour cela.

Il existe de nombreuses méthodes plus optimisées pour le faire, cependant. Vous pouvez trouver certaines des meilleures dans les réponses à cette question, " meilleur algorithme pour compter le nombre de bits définis dans un entier 32 bits " (évidemment, le nombre de bits zéro est le nombre de bits définis soustraits du nombre total des bits).

Ce n'est pas vraiment une réponse à votre question principale, mais vous devez réécrire votre fonction récursive comme ceci:

int num_of_zero(int num)
{
    int left_part_zeros;

    if (num == 0)
        return 0;

    left_part_zeros = num_of_zero(num >> 1);
    if ((num & 1) == 0)
        return left_part_zeros + 1;
    else
        return left_part_zeros;
}

manière rapide et muette - il existe des implémentations plus exotiques dans la question en double, mais j'ai utilisé quelque chose de similaire à celui-ci sans beaucoup d'effet malade dans le passé.

Nous utilisons une table de grignotins ici pour réduire le nombre de fois la boucle est exécutée - si vous faites une charge de bateau de ces calculs, il pourrait être plus efficace de construire un tableau beaucoup plus grand, dites, au niveau des octets, couper la boucle de la boucle en deux. P>

/* How many bits are set in every possible nibble. */
static size_t BIT_TABLE[] = {
    0, 1, 1, 2,     /* 0, 1, 2, 3 */
    1, 2, 2, 3,     /* 4, 5, 6, 7 */
    1, 2, 2, 3,     /* 8, 9, A, B */
    2, 3, 3, 4      /* C, D, E, F */
};

size_t num_of_bits(int num) {
    /* Little reworking could probably shrink the stack space in use here. */
    size_t ret = 0, i;
    register int work = num;

    /* Iterate every nibble, rotating the integer in place. */
    for(i = 0; i < (sizeof(num) * 2); i++) {
        /* Pointer math to get a member of the static array. */
        ret += *(BIT_TABLE + (work & 0xF));
        work >>= 4;
    }
    return ret;
}

Récursion est définitivement surkill - et d'ailleurs, votre buggy de votre code (il ne comptera pas l'un des leader zéros de num !!!). Une simple itération, telle que: xxx

est correct et plus rapide (peut être codé plus concis, mais je pense que c'est l'expression la plus claire).

Si vous devez Faites ce calcul à plusieurs reprises, envisagez de préciser un tableau de (dire) 256 "Compte de zéros" (chaque valeur donnant le compte pour son indice de 0 à 255 incluse, en tant que nombre de 8 bits). Ensuite, vous pouvez faire une boucle seulement 4 fois (masquage et déplacement de 8 bits à la fois), et dérouler facilement la boucle - si votre compilateur n'est pas assez intelligent pour le faire en votre nom; -).