Arrondir à la puissance de 2 la plus proche

Question

Je veux écrire une fonction qui retourne la puissance supérieure la plus proche de 2. Par exemple, si mon entrée est 789, la sortie devrait être 1024. Y a-t-il un moyen de le faire sans utiliser de boucles mais en utilisant simplement des opérateurs au niveau des bits?

Answer 1

Vérifiez les bidouilles peu bidouiller . Vous devez obtenir le logarithme en base 2, puis ajouter 1 à celui-ci.

Answer 2

 next = pow(2, ceil(log(x)/log(2)));
 

Cela fonctionne en trouvant le nombre que vous auriez à lever 2 pour obtenir x (prenez le journal du nombre et divisez-le par le journal de la base souhaitée, voir wikipedia pour plus d'informations ). Arrondissez ensuite avec ceil pour obtenir le nombre entier le plus proche.

C'est une méthode plus générale (c'est-à-dire plus lente!) Que les méthodes au niveau des bits reliées ailleurs, mais il est bon de connaître le calcul, hein?

Answer 3

Je pense que cela fonctionne aussi:

 int power = 1;
while(power < x)
    power*=2;
 

Et la réponse est power .

Answer 4

unsigned long upper_power_of_two(unsigned long v)
{
    v--;
    v |= v >> 1;
    v |= v >> 2;
    v |= v >> 4;
    v |= v >> 8;
    v |= v >> 16;
    v++;
    return v;

}

Answer 5

Si vous utilisez GCC, vous pouvez avoir un coup d'oeil à l'Optimisation de la next_pow2() fonction par Lockless Inc.. Cette page décrit la façon d'utiliser la fonction intégrée builtin_clz() (compte à zéro) et, plus tard, les utiliser directement x86 (ia32) instruction assembleur bsr (bit de balayage inverse), comme il est décrit dans une autre réponse' lien de gamedev site. Ce code pourrait être plus rapide que celles décrites dans la réponse précédente.

Par ailleurs, si vous n'allez pas utiliser l'instruction assembleur et 64 bits type de données, vous pouvez utiliser cette

/**
 * return the smallest power of two value
 * greater than x
 *
 * Input range:  [2..2147483648]
 * Output range: [2..2147483648]
 *
 */
__attribute__ ((const))
static inline uint32_t p2(uint32_t x)
{
#if 0
    assert(x > 1);
    assert(x <= ((UINT32_MAX/2) + 1));
#endif

    return 1 << (32 - __builtin_clz (x - 1));
}