Share on FacebookShare on Google+Tweet about this on TwitterShare on LinkedIn

Suite à la lecture de l’article écrit par Soumiyajit Chowdhury sur ITtoolbox, au sujet d’une méthode permettant de compter le nombre de 1 présents dans la forme binaire d’un nombre, j’ai cherché à améliorer le code qu’il proposait.

Le résultat est une optimisation qui permet de rendre le code environ 35 % plus rapide.

Le code original est le suivant :

#include <stdio.h>
 
main() {
int n, a;
int c = 0 ;
 
    printf( "enter a number", n );
    scanf( "%d", &n );
 
    while( n >= 1 ) {
        a = n % 2;
 
        if ( a == 1 ) {
            c = c + 1;
        }
 
        n = n / 2;
    }
 
    printf( "%d \n", c );
 
    return -1;
}

Voici les optimisations que j’ai apporté au code ci-dessus :

  1. La condition n >= 1 est remplacée par n != 0
    Les conditions sont équivalentes dans ce cas puisque la boucle doit être effectuée tant que le nombre positif n’est pas égal à 0.
  2. La suite d’instructions a = n % 2; if ( a == 1 ) c = c + 1; est remplacée par c += ( n & 1L );
    La détection d’un nombre impair est réalisée en testant si le nombre modulo 2 est égal à 1. Si tel est le cas, le compteur est incrémenté. L’optimisation proposée réalise la même chose en masquant le bit de poids le plus faible avec la valeur 1L. Le résultat est 1L s’il y a un 1 à la position testée et 0L dans le cas contraire. Cette valeur 1L ou 0L sert donc incrémenter le compteur comme il convient.
  3. L’instruction n = n / 2; est remplacée par n >>= 1;
    La division d’un nombre entier par 2 revient à un décalage des bits de ce nombre d’une position vers la gauche. La forme compacte n >>= 1 est préférée à la forme classique n = n >> 1.

Nous obtenons donc le code ci-dessous :

while( n != 0 ) {
    c += ( n & 1L );
    n >>= 1;
}

Le gain de vitesse a été mesuré à l’aide du programme ci-après :

#include "stdafx.h"
#include <ctime>
#include <limits.h>
 
int count_simple( unsigned long n, float *duration ) {
clock_t start = clock();
int a;
int c = 0;                
 
    while ( n >= 1 ) {
        a = n % 2;                
 
        if ( a == 1 ) {
            c = c + 1;
        }                
 
        n = n / 2;
    }                
 
    clock_t end = clock();
    *duration += (float) ( end - start ); 
 
    return c;
}      
 
int count_optimized( unsigned long n, float *duration ) {
clock_t start = clock();
int c = 0;                
 
    while ( n != 0 ) {
        c += ( n & 1L );
        n >>= 1;
    }                
 
    clock_t end = clock();
    *duration += (float) ( end - start ); 
 
    return c;
}      
 
int _tmain(int argc, _TCHAR* argv[]) {
float duration_simple = 0.0;
float duration_optimized = 0.0;                 
 
    for ( unsigned long n = 0; n < 100000000L; n++ ) {
        if ( count_simple( n, &duration_simple ) != count_optimized( n, &duration_optimized )) {
            printf( "Error\n" );               
 
            return 1;
        }
    }                 
 
    printf( "simple done in %.2f seconds.\n", duration_simple / (float) CLOCKS_PER_SEC );
    printf( "optimized done in %.2f seconds.\n", duration_optimized / (float) CLOCKS_PER_SEC );              
 
    return 0;
}