Arrondi à la prochaine puissance de 2

190

Je veux écrire une fonction qui renvoie la puissance suivante la plus proche de 2 nombre. Par exemple, si mon entrée est 789, la sortie doit être 1024. Existe-t-il un moyen d'y parvenir sans utiliser de boucles mais en utilisant simplement des opérateurs au niveau du bit?

Naveen
la source
4
Voir ici pour les solutions possibles: http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2Float
Stefan
4
A titre de clarification, avez-vous besoin de la puissance la plus proche de 2 (c'est-à-dire que 65 vous donnerait 64, mais 100 vous donnerait 128) ou la plus proche au-dessus (c'est-à-dire que 65 vous donnerait 128 et 100)?
Kim Reece
1
Ce sont plusieurs questions correspondant à celle-ci. Par exemple: stackoverflow.com/questions/364985/…
Yann Droneaud
7
@Nathan Votre lien est postérieur de 8 mois à cette question.
Joseph Quinsey

Réponses:

148

Vérifiez les Bit Twiddling Hacks . Vous devez obtenir le logarithme de base 2, puis ajouter 1 à cela. Exemple pour une valeur 32 bits:

Arrondissez à la prochaine puissance la plus élevée de 2

unsigned int v; // compute the next highest power of 2 of 32-bit v

v--;
v |= v >> 1;
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;
v++;

L'extension à d'autres largeurs devrait être évidente.

florin
la source
11
Ce n'est pas la solution la plus efficace car de nombreux processeurs ont des instructions spéciales pour compter les zéros non significatifs qui peuvent être utilisées pour calculer log2 très efficacement. Voir en.wikipedia.org/wiki/Find_first_set
Simon
7
@Simon: c'est la solution portable. Il n'y a pas d'algorithme efficace commun pour toutes les architectures
phuclv
5
Et si le nombre lui-même était une puissance de deux?
Litherum
6
Ce fil est toujours bien référencé mais cette réponse (et la plupart des autres) sont très obsolètes. Les processeurs ont une instruction pour aider (en fait déjà à ce moment-là?). De: jameshfisher.com/2018/03/30/round-up-power-2.html uint64_t next_pow2(uint64_t x) { return x == 1 ? 1 : 1<<(64-__builtin_clzl(x-1)); } Et pour 32 bits: uint32_t next_pow2(uint32_t x) { return x == 1 ? 1 : 1<<(32-__builtin_clz(x-1)); }c'est si vous utilisez GCC (et Clang je pense?), Mais il serait sage de prendre le temps de trouver l'appel à CLZ au lieu de copier-coller toutes les options autour.
MappaM
2
@MappaM Cette réponse est toujours très pertinente et la meilleure façon portable de le faire. Votre version 64 bits a un comportement non défini si x > UINT32_MAXet n'est pas sans branche. De plus, GCC et Clang utilisent -mtune=genericpar défaut (comme le font la plupart des distributions), donc votre code ne sera PAS étendu à l' lzcntinstruction sur x86_64 - il sera en fait étendu à quelque chose de BEAUCOUP plus lent (une routine libgcc) à moins que vous n'utilisiez quelque chose comme -march=native. Donc, votre remplacement proposé est non portable, bogué et (généralement) plus lent.
Craig Barnes
76
next = pow(2, ceil(log(x)/log(2)));

Cela fonctionne en trouvant le nombre que vous auriez augmenté de 2 pour obtenir x (prenez le journal du nombre et divisez par le journal de la base souhaitée, voir wikipedia pour plus ). Arrondissez ensuite avec ceil pour obtenir la puissance du 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 du bit liées ailleurs, mais il est bon de connaître les mathématiques, hein?

Paul Dixon
la source
3
À partir de C99, vous pouvez également simplement utiliser log2 s'il est pris en charge par vos outils. GCC et VS ne semblent pas: (
Matthew Read
2
Il vous manque un crochet ... suivant = pow (2, ceil (log (x) / log (2)));
Matthieu Cormier
13
Faites cependant attention à la précision du flotteur. log(pow(2,29))/log(2)= 29.000000000000004, donc le résultat est 2 30 au lieu de renvoyer 2 29. Je pense que c'est pourquoi les fonctions log2 existent?
endolith
48
Le coût est probablement d'au moins 200 cycles et ce n'est même pas correct. Pourquoi cela a-t-il autant de votes positifs?
Axel Gneiting
4
@SuperflyJon Mais il mentionne les opérateurs au niveau du bit et je suppose que l'exactitude est impliquée par toute question, sauf indication contraire.
BlackJack
50
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;

}
Éclipse
la source
62
Ce serait bien si vous l'aviez attribué (à moins que vous ne l'ayez découvert). Cela vient de la page des hacks bit twiddling.
florin le
3
Est-ce que c'est pour un nombre 32 bits? Extension pour 64 bits?
Jonathan Leffler
Jonathan, tu dois le faire pour la moitié supérieure, et si c'est zéro, tu le fais pour la moitié inférieure.
florin
5
@florin, si v est un type 64 bits, ne pourriez-vous pas simplement ajouter un "c | = v >> 32" après celui de 16?
Evan Teran
3
Le code qui ne fonctionne que pour une largeur de bits spécifique doit utiliser des types à largeur fixe au lieu de types à largeur minimale. Cette fonction doit prendre et retourner un fichier uint32_t.
Craig Barnes
50

Je pense que cela fonctionne aussi:

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

Et la réponse est power.

José Dagoberto
la source
19
Assez juste, la question ne demandait aucune boucle. Mais aussi intelligentes que soient certaines des autres fonctions, pour un code qui n'est pas sensible aux performances, la réponse qui est rapidement et facilement comprise et vérifiée comme étant correcte gagne toujours pour moi.
Tim MB
2
Cela ne renvoie pas la puissance la plus proche de 2, mais la puissance de celle-ci est immédiatement supérieure à X. Toujours très bon
CoffeDeveloper
1
Au lieu de multiplier, une «magie» au niveau du bit peut être utilisée à la placepower <<= 1
vallentin
5
@Vallentin Cela devrait être automatiquement optimisé par un compilateur.
MarkWeston
4
Attention à la boucle infinie si elle xest trop grande (c'est-à-dire pas assez de bits pour représenter la prochaine puissance de 2).
alban
36

Si vous utilisez GCC, vous voudrez peut-être jeter un oeil à Optimisation de la fonction next_pow2 () par Lockless Inc .. Cette page décrit un moyen d'utiliser la fonction intégrée builtin_clz()(nombre de zéro devant ) et plus tard d'utiliser directement x86 (ia32) instruction assembleur bsr(bit scan reverse), comme décrit dans le lien d' une autre réponse vers le site gamedev . Ce code peut être plus rapide que ceux décrits dans la réponse précédente .

À propos, si vous n'allez pas utiliser l'instruction assembleur et le type de données 64 bits, vous pouvez utiliser ceci

/**
 * 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));
}
Yann Droneaud
la source
3
Notez que cela renvoie la plus petite puissance de 2 supérieure à OU égale à x. Changer (x -1) en x change la fonction pour renvoyer la plus petite puissance de 2 supérieure à x.
Guillaume
2
Vous pouvez utiliser _BitScanForwardsur Visual C ++
KindDragon
Vous pouvez également utiliser__builtin_ctz()
MarkP
@MarkP __builtin_ctz()ne sera pas utile pour arrondir toute puissance de 2 à la prochaine puissance de deux
Yann Droneaud
2
Veuillez ajouter dans votre réponse un lien vers la liste Wikipedia des fonctions binaires intégrées pour d'autres compilateurs: en.wikipedia.org/wiki/Find_first_set#Tool_and_library_support                                Veuillez également fournir une version 64 bits. Je propose la fonction C ++ 11 suivante:              constexpr uint64_t nextPowerOfTwo64 (uint64_t x) { return 1ULL<<(sizeof(uint64_t) * 8 - __builtin_clzll(x)); }
olibre
15

Un de plus, bien que j'utilise le cycle, mais c'est beaucoup plus rapide que les opérandes mathématiques

puissance de deux option "étage":

int power = 1;
while (x >>= 1) power <<= 1;

option puissance de deux "ceil":

int power = 2;
x--;    // <<-- UPDATED
while (x >>= 1) power <<= 1;

METTRE À JOUR

Comme mentionné dans les commentaires, il y a eu une erreur dans le ceilcas où son résultat était faux.

Voici les fonctions complètes:

unsigned power_floor(unsigned x) {
    int power = 1;
    while (x >>= 1) power <<= 1;
    return power;
}

unsigned power_ceil(unsigned x) {
    if (x <= 1) return 1;
    int power = 2;
    x--;
    while (x >>= 1) power <<= 1;
    return power;
}
vlk
la source
2
le résultat n'est pas correct si la xpuissance est de 2. Un micro pour tester si l'entrée est une puissance de 2 est nécessaire. #define ISPOW2(x) ((x) > 0 && !((x) & (x-1)))
pgplus1628
@zorksylar serait plus efficace pourif (x == 0) return 1; /* Or 0 (Which is what I use) */ x--; /* Rest of program */
yyny
Bonne solution! mais le power of two "ceil" optionn'est pas correct. Par exemple, lorsque x = 2le résultat doit être 2au lieu de4
MZD
10

Pour tout type non signé, en s'appuyant sur les Bit Twiddling Hacks:

#include <climits>
#include <type_traits>

template <typename UnsignedType>
UnsignedType round_up_to_power_of_2(UnsignedType v) {
  static_assert(std::is_unsigned<UnsignedType>::value, "Only works for unsigned types");
  v--;
  for (size_t i = 1; i < sizeof(v) * CHAR_BIT; i *= 2) //Prefer size_t "Warning comparison between signed and unsigned integer"
  {
    v |= v >> i;
  }
  return ++v;
}

Il n'y a pas vraiment de boucle car le compilateur connaît au moment de la compilation le nombre d'itérations.

Robson
la source
4
Notez que la question concerne C.
martinkunev
@martinkunev Remplacez simplement UnsignedType et traitez-le manuellement. Je suis presque sûr qu'un programmeur C peut développer ce modèle simple en ignorant l' std::is_unsigned<UnsignedType>::valueassertion.
user877329
2
@ user877329 Bien sûr, ce serait bien d'avoir une réponse en Javascript également, juste au cas où quelqu'un voudrait la traduire en C.
martinkunev
@martinkunev UnsignedType en JavaScript? Quoi qu'il en soit, cette solution montre comment le faire pour n'importe quel UnsignedType, et il se trouve qu'il est écrit en C ++, plutôt qu'en pseudocode [sizeof (v) * CHAR_BIT au lieu de quelque chose comme le nombre de bits dans un objet de UnsignedType].
user877329
9

Pour les flotteurs IEEE, vous pourriez faire quelque chose comme ça.

int next_power_of_two(float a_F){
    int f = *(int*)&a_F;
    int b = f << 9 != 0; // If we're a power of two this is 0, otherwise this is 1

    f >>= 23; // remove factional part of floating point number
    f -= 127; // subtract 127 (the bias) from the exponent

    // adds one to the exponent if were not a power of two, 
    // then raises our new exponent to the power of two again.
    return (1 << (f + b)); 
}

Si vous avez besoin d'une solution entière et que vous êtes capable d'utiliser l'assemblage en ligne, BSR vous donnera le log2 d'un entier sur le x86. Il compte combien de bits droits sont définis, ce qui est exactement égal au log2 de ce nombre. D'autres processeurs ont des instructions similaires (souvent), telles que CLZ et en fonction de votre compilateur, il peut y avoir un intrinsèque disponible pour faire le travail à votre place.

Jasper Bekkers
la source
Ceci est un événement intéressant, bien que non lié à la question (je veux arrondir uniquement les nombres entiers), je vais essayer celui-ci ..
Naveen
Je suis venu avec après avoir lu l'article de wikipedia sur les flotteurs. En plus de cela, je l'ai utilisé pour calculer les racines carrées en précision entière. Aussi bien, mais encore plus sans rapport.
Jasper Bekkers
Cela enfreint les règles strictes d'aliasing. Sur certains compilateurs, cela peut ne pas fonctionner ou émettre un avertissement.
martinkunev
6

Malgré la question est étiqueté comme cici mes cinq cents. Heureusement pour nous, C ++ 20 inclurait std::ceil2et std::floor2(voir ici ). Ce sont des consexprfonctions de modèle, l' implémentation actuelle de GCC utilise le décalage de bits et fonctionne avec tout type non signé intégral.

kreuzerkrieg
la source
2
Ils l'ont récemment renommé bit_ceil open-std.org/JTC1/SC22/WG21/docs/papers/2020/p1956r1.pdf
Wolfgang Brehm
5
/*
** http://graphics.stanford.edu/~seander/bithacks.html#IntegerLog
*/
#define __LOG2A(s) ((s &0xffffffff00000000) ? (32 +__LOG2B(s >>32)): (__LOG2B(s)))
#define __LOG2B(s) ((s &0xffff0000)         ? (16 +__LOG2C(s >>16)): (__LOG2C(s)))
#define __LOG2C(s) ((s &0xff00)             ? (8  +__LOG2D(s >>8)) : (__LOG2D(s)))
#define __LOG2D(s) ((s &0xf0)               ? (4  +__LOG2E(s >>4)) : (__LOG2E(s)))
#define __LOG2E(s) ((s &0xc)                ? (2  +__LOG2F(s >>2)) : (__LOG2F(s)))
#define __LOG2F(s) ((s &0x2)                ? (1)                  : (0))

#define LOG2_UINT64 __LOG2A
#define LOG2_UINT32 __LOG2B
#define LOG2_UINT16 __LOG2C
#define LOG2_UINT8  __LOG2D

static inline uint64_t
next_power_of_2(uint64_t i)
{
#if defined(__GNUC__)
    return 1UL <<(1 +(63 -__builtin_clzl(i -1)));
#else
    i =i -1;
    i =LOG2_UINT64(i);
    return 1UL <<(1 +i);
#endif
}

Si vous ne voulez pas vous aventurer dans le domaine du comportement indéfini, la valeur d'entrée doit être comprise entre 1 et 2 ^ 63. La macro est également utile pour définir une constante au moment de la compilation.

Philip J. Fry
la source
C'est probablement la pire solution (il manque également le suffixe ULL sur la constante 64 bits). Cela générera 32 tests par entrée dans tous les cas. Mieux vaut utiliser une boucle while, ce sera toujours plus rapide ou à la même vitesse.
xryl669
1
MAIS ... cela peut être évalué par le préprocesseur si l'entrée est une constante, et donc ZERO opération au moment de l'exécution!
Michael le
4

Pour être complet, voici une implémentation en virgule flottante dans la norme bog C.

double next_power_of_two(double value) {
    int exp;
    if(frexp(value, &exp) == 0.5) {
        // Omit this case to round precise powers of two up to the *next* power
        return value;
    }
    return ldexp(1.0, exp);
}
Doynax
la source
1
Navigateurs aléatoires, si vous lisez ce commentaire, choisissez ce code. C'est clairement la meilleure réponse, pas d'instructions spéciales, pas de twiddling, juste un code efficace, portable et standard. Deviner pourquoi personne d'autre n'a voté pour ^^
CoffeDeveloper
5
Navigateurs aléatoires, cela va être très lent si vous n'avez pas de matériel spécialisé en virgule flottante. Sur x86, vous pouvez exécuter des cercles autour de ce code en utilisant le bit twiddling. rep bsr ecx,eax; mov eax,0; cmovnz eax,2; shl eax,clest environ 25 fois plus rapide.
Johan
4

Une solution efficace spécifique à Microsoft (par exemple, Visual Studio 2017) en C / C ++ pour la saisie d'entiers. Gère le cas de l'entrée correspondant exactement à une valeur de puissance de deux en décrémentant avant de vérifier l'emplacement du bit 1 le plus significatif.

inline unsigned int ExpandToPowerOf2(unsigned int Value)
{
    unsigned long Index;
    _BitScanReverse(&Index, Value - 1);
    return (1U << (Index + 1));
}

// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

#if defined(WIN64) // The _BitScanReverse64 intrinsic is only available for 64 bit builds because it depends on x64

inline unsigned long long ExpandToPowerOf2(unsigned long long Value)
{
    unsigned long Index;
    _BitScanReverse64(&Index, Value - 1);
    return (1ULL << (Index + 1));
}

#endif

Cela génère environ 5 instructions en ligne pour un processeur Intel similaire à ce qui suit:

dec eax
bsr rcx, rax
inc ecx
mov eax, 1
shl rax, cl

Apparemment, le compilateur Visual Studio C ++ n'est pas codé pour optimiser cela pour les valeurs de compilation, mais ce n'est pas comme s'il y avait beaucoup d'instructions.

Éditer:

Si vous voulez qu'une valeur d'entrée de 1 donne 1 (2 à la puissance zéro), une petite modification du code ci-dessus génère toujours des instructions directes sans branche.

inline unsigned int ExpandToPowerOf2(unsigned int Value)
{
    unsigned long Index;
    _BitScanReverse(&Index, --Value);
    if (Value == 0)
        Index = (unsigned long) -1;
    return (1U << (Index + 1));
}

Génère juste quelques instructions supplémentaires. L'astuce est que Index peut être remplacé par un test suivi d'une instruction cmove.

NoelC
la source
Une petite erreur: il devrait renvoyer 1 pour 1, ce n'est pas le cas.
0kcats
Merci. Dans l'application pour laquelle il a été développé, nous avions explicitement besoin de 2 à la première puissance lorsque 1 est entré. 1 pourrait être pris comme un cas particulier avec un conditionnel sans générer trop d'instructions supplémentaires j'imagine.
NoelC
Mise à jour de la réponse pour inclure une version qui renvoie 1 pour une valeur d'entrée de 1.
NoelC
3

Dans x86, vous pouvez utiliser les instructions de manipulation de bits sse4 pour le rendre rapide.

//assume input is in eax
popcnt edx,eax
lzcnt ecx,eax
cmp edx,1
jle @done       //popcnt says its a power of 2, return input unchanged
mov eax,2
shl eax,cl
@done: rep ret

En c, vous pouvez utiliser les intrinsèques correspondants.

Johan
la source
Inutile mais génial!
Marco
3

Voici ma solution en C. J'espère que cela vous aidera!

int next_power_of_two(int n) {
    int i = 0;
    for (--n; n > 0; n >>= 1) {
        i++;
    }
    return 1 << i;
}
Kevin Yang
la source
0

De nombreuses architectures de processeur prennent en charge log base 2ou un fonctionnement très similaire - count leading zeros. De nombreux compilateurs ont des caractéristiques intrinsèques. Voir https://en.wikipedia.org/wiki/Find_first_set

Simon
la source
il ne s'agit pas de trouver le bit le plus élevé (= bsr) ou de compter les zéros non significatifs. il veut arrondir à la puissance supérieure la plus proche de 2. la réponse par «soustraire 1, puis faire bsr et décaler 1 à gauche» fait cela.
Flo
0

En supposant que vous ayez un bon compilateur et qu'il puisse faire le petit twiddling avant la main, c'est au-dessus de moi à ce stade, mais de toute façon cela fonctionne !!!

    // http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious
    #define SH1(v)  ((v-1) | ((v-1) >> 1))            // accidently came up w/ this...
    #define SH2(v)  ((v) | ((v) >> 2))
    #define SH4(v)  ((v) | ((v) >> 4))
    #define SH8(v)  ((v) | ((v) >> 8))
    #define SH16(v) ((v) | ((v) >> 16))
    #define OP(v) (SH16(SH8(SH4(SH2(SH1(v))))))         

    #define CB0(v)   ((v) - (((v) >> 1) & 0x55555555))
    #define CB1(v)   (((v) & 0x33333333) + (((v) >> 2) & 0x33333333))
    #define CB2(v)   ((((v) + ((v) >> 4) & 0xF0F0F0F) * 0x1010101) >> 24)
    #define CBSET(v) (CB2(CB1(CB0((v)))))
    #define FLOG2(v) (CBSET(OP(v)))

Code de test ci-dessous:

#include <iostream>

using namespace std;

// http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious
#define SH1(v)  ((v-1) | ((v-1) >> 1))  // accidently guess this...
#define SH2(v)  ((v) | ((v) >> 2))
#define SH4(v)  ((v) | ((v) >> 4))
#define SH8(v)  ((v) | ((v) >> 8))
#define SH16(v) ((v) | ((v) >> 16))
#define OP(v) (SH16(SH8(SH4(SH2(SH1(v))))))         

#define CB0(v)   ((v) - (((v) >> 1) & 0x55555555))
#define CB1(v)   (((v) & 0x33333333) + (((v) >> 2) & 0x33333333))
#define CB2(v)   ((((v) + ((v) >> 4) & 0xF0F0F0F) * 0x1010101) >> 24)
#define CBSET(v) (CB2(CB1(CB0((v)))))
#define FLOG2(v) (CBSET(OP(v))) 

#define SZ4         FLOG2(4)
#define SZ6         FLOG2(6)
#define SZ7         FLOG2(7)
#define SZ8         FLOG2(8) 
#define SZ9         FLOG2(9)
#define SZ16        FLOG2(16)
#define SZ17        FLOG2(17)
#define SZ127       FLOG2(127)
#define SZ1023      FLOG2(1023)
#define SZ1024      FLOG2(1024)
#define SZ2_17      FLOG2((1ul << 17))  // 
#define SZ_LOG2     FLOG2(SZ)

#define DBG_PRINT(x) do { std::printf("Line:%-4d" "  %10s = %-10d\n", __LINE__, #x, x); } while(0);

uint32_t arrTble[FLOG2(63)];

int main(){
    int8_t n;

    DBG_PRINT(SZ4);    
    DBG_PRINT(SZ6);    
    DBG_PRINT(SZ7);    
    DBG_PRINT(SZ8);    
    DBG_PRINT(SZ9); 
    DBG_PRINT(SZ16);
    DBG_PRINT(SZ17);
    DBG_PRINT(SZ127);
    DBG_PRINT(SZ1023);
    DBG_PRINT(SZ1024);
    DBG_PRINT(SZ2_17);

    return(0);
}

Les sorties:

Line:39           SZ4 = 2
Line:40           SZ6 = 3
Line:41           SZ7 = 3
Line:42           SZ8 = 3
Line:43           SZ9 = 4
Line:44          SZ16 = 4
Line:45          SZ17 = 5
Line:46         SZ127 = 7
Line:47        SZ1023 = 10
Line:48        SZ1024 = 10
Line:49        SZ2_16 = 17
nimig18
la source
0

J'essaie d'obtenir la puissance inférieure la plus proche de 2 et j'ai fait cette fonction. Que cela vous aide, il suffit de multiplier le nombre inférieur le plus proche par 2 pour obtenir la puissance supérieure la plus proche de 2

int nearest_upper_power(int number){
    int temp=number;
    while((number&(number-1))!=0){
        temp<<=1;
        number&=temp;
    }
    //Here number is closest lower power 
    number*=2;
    return number;
}
Cody Piersall
la source
0

Adapté de la réponse de Paul Dixon à Excel, cela fonctionne parfaitement.

 =POWER(2,CEILING.MATH(LOG(A1)/LOG(2)))
Tim Tharratt
la source
0

Une variante de @YannDroneaud répond valable pour x==1, uniquement pour les plates-formes x86, les compilateurs, gcc ou clang:

__attribute__ ((const))
static inline uint32_t p2(uint32_t x)
{
#if 0
    assert(x > 0);
    assert(x <= ((UINT32_MAX/2) + 1));
#endif
  int clz;
  uint32_t xm1 = x-1;
  asm(
    "lzcnt %1,%0"
    :"=r" (clz)
    :"rm" (xm1)
    :"cc"
    );
    return 1 << (32 - clz);
}
Oliv
la source
0

Voici ce que j'utilise pour que ce soit une expression constante, si l'entrée est une expression constante.

#define uptopow2_0(v) ((v) - 1)
#define uptopow2_1(v) (uptopow2_0(v) | uptopow2_0(v) >> 1)
#define uptopow2_2(v) (uptopow2_1(v) | uptopow2_1(v) >> 2)
#define uptopow2_3(v) (uptopow2_2(v) | uptopow2_2(v) >> 4)
#define uptopow2_4(v) (uptopow2_3(v) | uptopow2_3(v) >> 8)
#define uptopow2_5(v) (uptopow2_4(v) | uptopow2_4(v) >> 16)

#define uptopow2(v) (uptopow2_5(v) + 1)  /* this is the one programmer uses */

Ainsi, par exemple, une expression comme:

uptopow2(sizeof (struct foo))

se réduira joliment à une constante.

Kaz
la source
0

Vous trouverez peut-être la clarification suivante utile à votre objectif:

Aashay Sathe
la source
0

Convertissez-le en flottant, puis utilisez .hex () qui montre la représentation IEEE normalisée.

>>> float(789).hex() '0x1.8a80000000000p+9'

Ensuite, extrayez simplement l'exposant et ajoutez 1.

>>> int(float(789).hex().split('p+')[1]) + 1 10

Et élevez 2 à cette puissance.

>>> 2 ** (int(float(789).hex().split('p+')[1]) + 1) 1024

David Wallace
la source
Notez que cette réponse est en python
David Wallace
0
import sys


def is_power2(x):
    return x > 0 and ((x & (x - 1)) == 0)


def find_nearest_power2(x):
    if x <= 0:
        raise ValueError("invalid input")
    if is_power2(x):
        return x
    else:
        bits = get_bits(x)
        upper = 1 << (bits)
        lower = 1 << (bits - 1)
        mid = (upper + lower) // 2
        if (x - mid) > 0:
            return upper
        else:
            return lower


def get_bits(x):
    """return number of bits in binary representation"""
    if x < 0:
        raise ValueError("invalid input: input should be positive integer")
    count = 0
    while (x != 0):
        try:
            x = x >> 1
        except TypeError as error:
            print(error, "input should be of type integer")
            sys.exit(1)
        count += 1
    return count
Yossarian42
la source
-1

Si vous en avez besoin pour des choses liées à OpenGL:

/* Compute the nearest power of 2 number that is 
 * less than or equal to the value passed in. 
 */
static GLuint 
nearestPower( GLuint value )
{
    int i = 1;

    if (value == 0) return -1;      /* Error! */
    for (;;) {
         if (value == 1) return i;
         else if (value == 3) return i*4;
         value >>= 1; i *= 2;
    }
}
Paulo Lopes
la source
8
«for» est une boucle.
florin le
1
florin: ça l'est. et c'est utilisé comme une boucle ici, n'est-ce pas?
Tamas Czinege
9
DrJokepu - Je pense que florin voulait dire ici que l'OP demandait une solution sans boucle
Eli Bendersky
-1

Si vous voulez un modèle sur une ligne. C'est ici

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

ou

int nxt_po2(int n) { return 1 + (n|=(n|=(n|=(n|=(n|=(n-=1)>>(1<<0))>>(1<<1))>>(1<<2))>>(1<<3))>>(1<<4)); }
Vo Hoang Anh
la source
Ce comportement n'est pas défini en C ou C ++ et entraînera des erreurs. La modification à nplusieurs reprises sans point de séquence n'est pas valide. Vous l'avez écrit comme si n-=1cela devait arriver en premier, mais la seule garantie ici est que ncontient sa nouvelle valeur après le ;et les parenthèses ne changent pas cela.
sam hocevar
Plus précisément, cela fait saigner mes yeux.
Donal Fellows