webentwicklung-frage-antwort-db.com.de

Aufrunden auf die nächste Potenz von 2

Ich möchte eine Funktion schreiben, die die nächste nächste Potenz von 2 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?

coptimizationbit-manipulation
153
Naveen

Überprüfen Sie die Bit Twiddling Hacks . Sie müssen den Logarithmus der Basis 2 ermitteln 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 Ausdehnung auf andere Breiten sollte offensichtlich sein.

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

Dies funktioniert, indem Sie die Zahl finden, die Sie um 2 erhöhen würden, um x zu erhalten (nehmen Sie das Protokoll der Nummer und teilen Sie es durch das Protokoll der gewünschten Basis, siehe Wikipedia für mehr ). Runden Sie das dann mit einer Decke ab, um die nächste volle Zahl zu erhalten.

Dies ist eine allgemeinere (d. H. Langsamere!) Methode als die an anderen Stellen verknüpften bitweisen Methoden, aber es ist gut, die Mathematik zu kennen, oder?

69
Paul Dixon
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;

}
50
Eclipse

Ich denke, das funktioniert auch:

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

Und die Antwort ist power.

42
Jose Dagoberto

Wenn Sie GCC verwenden, möchten Sie vielleicht einen Blick auf Optimierung der Funktion next_pow2 () von Lockless Inc. werfen. Diese Seite beschreibt eine Möglichkeit, die eingebaute Funktion builtin_clz() (Anzahl führender Null) und die spätere Verwendung zu verwenden direkt x86 (ia32) Assembler-Anweisung bsr (Bit-Scan-Reverse), genauso wie in eine andere Antwort 's Verknüpfung zu gamedev site beschrieben. Dieser Code ist möglicherweise schneller als die in vorherige Antwort beschriebenen.

Wenn Sie keine Assembler-Anweisungen und einen 64-Bit-Datentyp verwenden, können Sie dies übrigens 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));
}
28
Yann Droneaud

Eine mehr, obwohl ich cycle benutze, aber das ist viel schneller als mathematische Operanden

potenz von zwei "Boden" -Option:

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

macht von zwei "ceiling" Option:

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

UPDATE

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

Hier sind volle 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;
}
15
vlk

Für jeden vorzeichenlosen Typ, der auf den Bit Twiddling Hacks aufbaut:

#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 nicht wirklich eine Schleife, da der Compiler die Anzahl der Iterationen zur Kompilierzeit kennt.

9
robson

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 Integer-Lösung benötigen und Inline-Assembly verwenden können, gibt Ihnen BSR das log2 einer Integer-Zahl auf dem x86. Es zählt, wie viele rechte Bits gesetzt sind, was genau dem log2 dieser Zahl entspricht. Andere Prozessoren verfügen über ähnliche Anweisungen (häufig), z. B. CLZ. Abhängig von Ihrem Compiler ist möglicherweise ein System vorhanden, das die Arbeit für Sie erledigt.

8
Jasper Bekkers

Der Vollständigkeit halber ist hier eine Floating-Point-Implementierung im Sumpfstandard 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);
}
6
doynax
/*
** 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 des undefinierten Verhaltens begeben wollen, muss der Eingabewert zwischen 1 und 2 ^ 63 liegen. Das Makro ist auch nützlich, um die Konstante zur Kompilierzeit zu setzen.

4
Philip J. Fry

Eine effiziente Microsoft-Lösung (z. B. Visual Studio 2017) in C/C++ für die Ganzzahleingabe. Behandelt den Fall, dass der Eingang genau mit einem Potenzwert von zwei übereinstimmt, indem er dekrementiert wird, bevor der Ort des höchstwertigen 1-Bit geprü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

Dadurch werden etwa fünf eingebettete Anweisungen für einen Intel-Prozessor erzeugt, die der folgenden ähneln:

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

Anscheinend ist der Visual Studio C++ - Compiler nicht so programmiert, dass er die Werte für die Kompilierungszeit optimiert, aber es gibt nicht viele Anweisungen.

Bearbeiten:

Wenn Sie möchten, dass ein Eingabewert von 1 eine 1 ergibt (2 für die nullte Potenz), generiert eine kleine Änderung des obigen Codes immer noch direkte Anweisungen ohne Verzweigung.

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

Erzeugt nur ein paar weitere Anweisungen. Der Trick ist, dass Index durch einen Test gefolgt von einer cmove-Anweisung ersetzt werden kann.

2
NoelC

In x86 können Sie die sse4-Bitmanipulationsanweisungen 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.

2
Johan

Paul Dixons Antwort an Excel angepasst, das funktioniert perfekt.

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

Trotz der Frage ist als c hier meine fünf Cent markiert. Zum Glück würde C++ 20 std::ceil2 und std::floor2 (siehe hier ) enthalten. Es handelt sich hierbei um consexpr-Template-Funktionen, die aktuelle GCC-Implementierung verwendet Bitshifting und arbeitet mit jedem ganzzahligen vorzeichenlosen Typ.

1
kreuzerkrieg

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

werde schön auf eine konstante reduzieren.

0
Kaz

Angenommen, Sie haben einen guten Compiler und er kann das bisschen vor mir, das jetzt über mir liegt, drehen, aber das funktioniert trotzdem !!!

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

Viele Prozessorarchitekturen unterstützen log base 2 oder sehr ähnliche Operationen - count leading zeros. Viele Compiler verfügen über Intrinsics. Siehe https://en.wikipedia.org/wiki/Find_first_set

0
Simon

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;
}
0
Kevin Yang

Eine Variante von @YannDroneaud, die für x==1 gültig ist, gilt nur für x86-Plattenformulare, 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);
}
0
Oliv

Ich versuche, die nächst niedrigere Potenz von 2 zu erreichen, und habe diese Funktion gemacht. Möge es Ihnen helfen. Vervielfachen Sie einfach die nächstniedrigere Zahl mal 2, um die nächsthöhere 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;
}
0
user6398437