Arrondi à la prochaine puissance de 2

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?

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.

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?

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;

}

Je pense que cela fonctionne aussi:

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

Et la réponse est power.

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));
}

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;
}

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.

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.

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.

/*
** 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.

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);
}

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.

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.

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;
}

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

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

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;
}

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

 =POWER(2,CEILING.MATH(LOG(A1)/LOG(2)))

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);
}

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.

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

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

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

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;
    }
}

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)); }