Calculer la première puissance de deux supérieure à un nombre

Cet article provient de mon ancien site Internet.

Introduction

Parfois, il peut être utile d’arrondir un nombre à la puissance de 2 supérieure (par exemple, certaines tables de hachage sont plus efficace avec une taille en puissance de 2). C’est quelque chose d’assez simple à faire, en revanche pour le faire efficacement, il faut faire du touillage de bits (bit twiddling).

Petite remarque importante : les fonctions suivantes seront définies, pour un nombre sur N bits, sur l’intervalle ]0; 2^N-1].
La borne supérieure est évidente, si un nombre (non signé) est codé sur N bits le plus grand nombre représentable est 2^N-1, donc si le nombre en entrée est supérieure à 2^N-1 la solution (2^N) n’est pas représentable.
La borne inférieure résulte d’un choix d’implémentation. Si le nombre en entrée est 0, il suffit de renvoyer 1. Cependant, j’ai décidé de renvoyer 0 (car cela simplifie un peu mon code), donc ma fonction n’est pas définie pour 0.

Approche naïve

La fonction suivante est l’implémentation la plus simple pour résoudre ce problème. On teste les puissances de deux de 2⁰ jusqu’à 2^N (où N est le nombre de bits utilisé pour coder un int) et on renvoie la première qui est supérieure à n.

1
2
3
4
5
6
7
8
9
10
11

unsigned next_highest_power_of_2(unsigned n)
{
    unsigned res = 1;
    if(!n || n > (UINT_MAX >> 1) + 1)
        return 0;

    while(res < n)
        res <<= 1;

    return res;
}

Le premier test permet de vérifier si le nombre en entrée est dans l’intervalle ]0; 2^N-1]. Si ce n’est pas le cas, la fonction renvoie 0.

Le problème avec cette fonction c’est que, dans le pire des cas, elle fera N itérations (si le nombre est codé sur N bits). Donc à moins de connaître la distribution des entrées, il vaut mieux faire attention en utilisant cette fonction car elle sera « lente » (tout est relatif) si on doit traiter beaucoup de grands nombres.

On peut aussi l’implémenter de manière à ce qu’elle parcourt les puissances de deux de 2^N à 2⁰, mais le problème reste le même (sauf que cette fois ce sont les petits nombres qui demandent plus d’itérations).

Optimisation

Il existe une autre approche, que l’on retrouve dans le livre Hacker’s Delight, qui est bien plus efficace (mais moins évidente au premier abord).

La technique cette fois‑ci, c’est de mettre à 1 tous les bits à droite du bit à 1 de poids le plus fort. Une fois que l’on a fait ça, il suffit d’ajouter 1 et on obtient la première puissance de deux supérieure à notre nombre.

1
2
3
4
5
6
7
8

unsigned next_highest_power_of_2(unsigned n)
{
    unsigned i;
    --n;
    for(i = 1; i < sizeof n * CHAR_BIT; i <<= 1)
        n |= n >> i;
    return ++n;
}

L’avantage de cet algorithme, c’est qu’il n’y a pas de pire cas. On fera toujours log₂(N) itérations, où N est le nombre de bits sur lequel est codé le nombre, indépendamment de la valeur de ce nombre.

Pour essayer de clarifier les choses, voilà une trace pas à pas de cet algorithme pour un nombre codé sur 8 bits (on fera donc log₂(8)=3 itérations).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

00101010 // 42
// Initialisation
00101001 // --n
// Iteration 1
00010100 // n >> 1
00111101 // n | (n >> 1)
// Iteration 2
00001111 // n >> 2
00111111 // n | (n >> 2)
// Iteration 3
00000011 // n >> 4
00111111 // n | (n >> 4)
// Finalisation
01000000 // ++n
// Fin de l’algo, n = 64.

On pourrait aussi écrire le code d’une autre manière, en déroulant la boucle (loop unrolling) pour l’optimiser encore un peu plus. Le code ci-dessous est un exemple pour le cas où le type int est codé sur 32 bits.

1
2
3
4
5
6
7
8
9
10

unsigned next_highest_power_of_2(unsigned n)
{
    --n;
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;
    return ++n;
}

L’avantage de cette forme c’est qu’elle ne contient aucune instruction de branchement, le processeur n’a donc pas besoin d’utiliser le prédicteur de branchements. Du coup, aucun risque de vider le pipeline ou d’y insérer des « bulles » (instructions NOP) en cas de mauvaises prédictions lors du calcul (même si ce risque est, de toute manière, faible étant donné l’efficacité des prédicteurs).

Pourtant, cette version est moins bonne que la précédente. Et ce pour deux raisons :

1. N’importe quel compilateur un tant soit peu évolué va dérouler la boucle de lui-même si c’est nécessaire (le nombre d’itérations de notre boucle étant connu à la compilation, c’est trivial).

2. Cette version est moins portable (le code fera trop d’itérations si les int sont codés sur 16 bits, et pire encore, il ne fonctionnera pas correctement si les int sont codés sur 64 bits) et on ne peut pas la rendre générique facilement.

Tiens, puisque l’on parle de généricité, voyons comment mettre cela en œuvre.

Généricité

Le problème avec la généricité, c’est que l’on a un type de retour variable, donc pas moyen de faire une fonction. Le type influence également le nombre d’itérations à effectuer. On va donc utiliser une macro qui prendra en paramètre la variable et son type.

Je ne prends pas la peine de parenthèser les paramètres de la macro comme il souvent recommandé, à raison d’ailleurs, de le faire car dans le cas présent c’est inutile. En effet, si l’on passe autre chose qu’une variable, « 2 + 2 » par exemple, ça ne passera de toute façon pas à la compilation.

1
2
3
4
5
6
7
8
9

#define generic_next_highest_power_of_2(n, T)\
    do\
    {\
        unsigned s___;\
        --n;\
        for(s___ = 1; s___ < sizeof(T) * CHAR_BIT; s___ <<= 1)\
            n |= n >> s___;\
        ++n;\
    } while(0)

Une rapide analyse nous montre que le second paramètre est inutile étant donné que l’opérateur sizeof peut aussi bien travailler avec les types qu’avec les variables. On peut donc réécrire la macro de cette manière :

1
2
3
4
5
6
7
8
9

#define generic_next_highest_power_of_2(n)\
    do\
    {\
        unsigned s___;\
        --n;\
        for(s___ = 1; s___ < sizeof(n) * CHAR_BIT; s___ <<= 1)\
            n |= n >> s___;\
        ++n;\
    } while(0)

Lors de l’utilisation de cette macro avec un unsigned short ou un unsigned char on obtient un warning du genre :

warning: conversion to 'short unsigned int' from 'int' may alter its value [-Wconversion]

Mais c’est absolument sans risque dans le cas présent (enfin si, ça peut tronquer la valeur dans certains cas, mais dans ces cas-là c’est le comportement attendu donc pas de problème).

Cela dit, bien que cette macro soit générique, elle a quand même plusieurs inconvénients par rapport à la version sous forme de fonction :

1. on ne peut pas l’appliquer sur des constantes (vu qu’elle modifie directement son paramètre).
2. on ne peut pas l’utiliser dans une expression (vu qu’elle ne renvoie pas de valeur).
3. il y a un risque de masquage de variable. En effet, je déclare une variable dans mon bloc do/while (la variable s___), et comme l’utilisateur de la macro ne connait pas le nom de cette variable, il n’est pas impossible qu’il utilise déjà une variable avec le même nom. Cela dit, j’ai choisi un nom assez peu courant pour limiter ce risque, mais il faut savoir qu’il existe.

Le point 3 est solvable en demandant à l’utilisateur de nous fournir une variable au lieu de la créer nous-même.

1
2
3
4
5
6
7
8
9

#define generic_next_highest_power_of_2(n, i)\
    do\
    {\
        unsigned i;\
        --n;\
        for(i = 1; i < sizeof(n) * CHAR_BIT; i <<= 1)\
            n |= n >> i;\
        ++n;\
    } while(0)

Cela dit, les points 1 et 2 restent vrai.