Aufrunden auf die nächste Potenz von 2

Ich möchte eine Funktion schreiben, die die nächste Potenz von 2 Zahlen zurückgibt. Wenn meine Eingabe beispielsweise 789 ist, sollte die Ausgabe 1024 sein. Gibt es eine Möglichkeit, dies zu erreichen, ohne Schleifen zu verwenden, sondern nur einige bitweise Operatoren zu verwenden?

Überprüfen Sie die Bit Twiddling Hacks . Sie müssen den Logarithmus zur Basis 2 erhalten und dann 1 hinzufügen. Beispiel für einen 32-Bit-Wert:

Runden Sie auf die nächsthöhere Potenz von 2 auf

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

Die Erweiterung auf andere Breiten sollte offensichtlich sein.

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

Dies funktioniert, indem Sie die Zahl finden, um die Sie 2 erhöhen würden, um x zu erhalten (nehmen Sie das Protokoll der Zahl und dividieren Sie es durch das Protokoll der gewünschten Basis, siehe Wikipedia für weitere Informationen ). Runden Sie das dann mit Ceil ab, um die nächste ganze Zahl zu erhalten.

Dies ist eine allgemeinere (dh langsamere!) Methode als die an anderer Stelle verknüpften bitweisen Methoden, aber gut, um die Mathematik zu kennen, oder?

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;

}

Ich denke, das funktioniert auch:

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

Und die Antwort ist power.

Wenn Sie GCC verwenden, sollten Sie sich die Optimierung der next_pow2 () -Funktion von Lockless Inc. ansehen. Auf dieser Seite wird eine Möglichkeit beschrieben, die integrierte Funktion builtin_clz()(Anzahl führender Nullpunkte) und später direkt x86 (ia32) zu verwenden. Assemblerbefehl bsr(Bit - Scan - Reverse), so wie es in beschrieben ist eine andere Antwort ‚s Link zu gamedev Website . Dieser Code ist möglicherweise schneller als die in der vorherigen Antwort beschriebenen .

Übrigens, wenn Sie keine Assembler-Anweisung und keinen 64-Bit-Datentyp verwenden möchten, können Sie diese verwenden

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

Eins mehr, obwohl ich Zyklus benutze, aber das ist viel schneller als mathematische Operanden

Power of Two "Floor" Option:

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

Potenz von zwei "Ceil" -Option:

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

AKTUALISIEREN

Wie in den Kommentaren erwähnt, gab es einen Fehler, bei ceildem das Ergebnis falsch war.

Hier sind alle Funktionen:

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

Aufbauend auf den Bit Twiddling Hacks für jeden nicht signierten Typ:

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

Es gibt dort keine wirkliche Schleife, da der Compiler zur Kompilierungszeit die Anzahl der Iterationen kennt.

Für IEEE-Floats können Sie so etwas tun.

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

Wenn Sie eine Ganzzahllösung benötigen und die Inline-Assembly verwenden können, gibt Ihnen BSR das Protokoll2 einer Ganzzahl auf dem x86. Es wird gezählt, wie viele richtige Bits gesetzt sind, was genau dem log2 dieser Zahl entspricht. Andere Prozessoren haben (häufig) ähnliche Anweisungen, wie z. B. CLZ. Abhängig von Ihrem Compiler steht möglicherweise eine eigene Anleitung zur Verfügung, um die Arbeit für Sie zu erledigen.

Trotz der Frage ist wie chier meine fünf Cent markiert . Glücklicherweise würde C ++ 20 std::ceil2und enthalten std::floor2(siehe hier ). Es handelt sich um consexprVorlagenfunktionen, die aktuelle GCC-Implementierung verwendet Bitshifting und funktioniert mit jedem integralen vorzeichenlosen Typ.

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

Wenn Sie sich nicht in den Bereich undefinierten Verhaltens wagen möchten, muss der Eingabewert zwischen 1 und 2 ^ 63 liegen. Das Makro ist auch nützlich, um zur Kompilierungszeit eine Konstante festzulegen.

Der Vollständigkeit halber ist hier eine Gleitkomma-Implementierung in Moor-Standard 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);
}

Eine effiziente Microsoft-spezifische (z. B. Visual Studio 2017) spezifische Lösung in C / C ++ für die Eingabe von Ganzzahlen. Behandelt den Fall, dass der Eingang genau mit einer Zweierpotenz übereinstimmt, indem er dekrementiert wird, bevor die Position des höchstwertigen 1-Bits überprüft wird.

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

Dies erzeugt ungefähr 5 Inline-Anweisungen für einen Intel-Prozessor, ähnlich den folgenden:

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

Anscheinend ist der Visual Studio C ++ - Compiler nicht codiert, um dies für Werte zur Kompilierungszeit zu optimieren, aber es ist nicht so, dass es dort eine ganze Reihe von Anweisungen gibt.

Bearbeiten:

Wenn Sie möchten, dass ein Eingabewert von 1 1 ergibt (2 zur nullten Potenz), wird durch eine kleine Änderung des obigen Codes immer noch direkt Anweisungen ohne Verzweigung generiert.

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

Generiert nur noch ein paar Anweisungen. Der Trick besteht darin, dass Index durch einen Test gefolgt von einer cmove-Anweisung ersetzt werden kann.

In x86 können Sie die Anweisungen zur Manipulation von sse4-Bits verwenden, um es schnell zu machen.

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

In c können Sie die passenden Intrinsics verwenden.

Hier ist meine Lösung in C. Hoffe das hilft!

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

Viele Prozessorarchitekturen unterstützen log base 2oder sehr ähnliche Operationen - count leading zeros. Viele Compiler haben Eigenheiten dafür. Siehe https://en.wikipedia.org/wiki/Find_first_set

Vorausgesetzt, Sie haben einen guten Compiler und er kann das bisschen vor der Hand drehen, das an diesem Punkt über mir liegt, aber trotzdem funktioniert das !!!

    // 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)))

Testcode unten:

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

Ausgänge:

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

Ich versuche, die nächst niedrigere Potenz von 2 zu erhalten und habe diese Funktion ausgeführt. Möge es Ihnen helfen. Multiplizieren Sie einfach die nächste untere Zahl mit 2, um die nächste obere Potenz von 2 zu erhalten

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

Angepasst an Paul Dixons Antwort auf Excel funktioniert dies perfekt.

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

Eine Variante der @ YannDroneaud-Antwort gilt x==1nur für x86-Plattenformen, Compiler, gcc oder 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);
}

Hier ist, was ich verwende, damit dies ein konstanter Ausdruck ist, wenn die Eingabe ein konstanter Ausdruck ist.

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

So zum Beispiel ein Ausdruck wie:

uptopow2(sizeof (struct foo))

wird schön auf eine Konstante reduzieren.

Die folgende Klarstellung kann für Ihren Zweck hilfreich sein:

Konvertieren Sie es in einen Float und verwenden Sie dann .hex (), das die normalisierte IEEE-Darstellung zeigt.

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

Dann extrahieren Sie einfach den Exponenten und addieren 1.

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

Und erhöhe 2 auf diese Kraft.

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

Wenn Sie es für OpenGL-bezogene Dinge benötigen:

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

Wenn Sie eine einzeilige Vorlage möchten. Hier ist es

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

oder

int nxt_po2(int n) { return 1 + (n|=(n|=(n|=(n|=(n|=(n-=1)>>(1<<0))>>(1<<1))>>(1<<2))>>(1<<3))>>(1<<4)); }