Aufrunden auf die nächste Potenz von 2

Lesezeit: 6 Minuten

Naveen

Ich möchte eine Funktion schreiben, die die 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 zu verwenden?

Siehe hier für mögliche Lösungen: http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2Float

– Stefan

21. Januar 2009 um 17:31 Uhr
Benötigen Sie zur Verdeutlichung die nächste Potenz von 2 (dh 65 würde Ihnen 64 geben, aber 100 würde Ihnen 128 geben) oder die nächste Potenz (dh 65 würde Ihnen 128 geben, und 100 auch)?

– Kim Reece

21. Januar 2009 um 17:45 Uhr
Es sind mehrere Fragen, die zu dieser passen. Zum Beispiel: stackoverflow.com/questions/364985/…

– Yann Droneaud

11. März 2013 um 11:49 Uhr
Mögliches Duplikat von Wie finde ich bei einer Ganzzahl die nächstgrößte Zweierpotenz mit Bit-Twiddling?

– Nathan

16. Januar 2014 um 0:44 Uhr
@Nathan Dein Link ist 8 Monate alt später als diese Frage.

– Joseph Quinsey

16. Januar 2014 um 5:11 Uhr

Paul Dixon

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

Dies funktioniert, indem Sie die Zahl finden, um die Sie 2 erhöhen müssten, um x zu erhalten (nehmen Sie den Log der Zahl und dividieren Sie durch den Log der gewünschten Basis, siehe wikipedia für mehr). Runden Sie das dann mit ceil auf, um die nächste ganzzahlige Potenz zu erhalten.

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

Ab C99 kann man das auch einfach verwenden log2 sofern von Ihren Tools unterstützt. GCC und VS scheinen das nicht zu tun 🙁

– Matthäus Lesen

22. Januar 2012 um 5:49 Uhr
Seien Sie jedoch vorsichtig mit der Float-Genauigkeit. log(pow(2,29))/log(2) = 29,000000000000004, also ist das Ergebnis 230 anstatt 2 zurückzugeben29. Ich denke, das ist der Grund, warum log2-Funktionen existieren?

– Endolith

9. Dezember 2013 um 2:52 Uhr
Die Kosten dafür betragen wahrscheinlich mindestens 200 Zyklen und es ist nicht einmal richtig. Warum hat das so viele Upvotes?

– Axel Gneiting

18. August 2015 um 20:17 Uhr
@SuperflyJon Aber es erwähnt bitweise Operatoren und ich gehe davon aus, dass jede Frage die Richtigkeit impliziert, sofern nicht anders angegeben.

– Blackjack

2. Mai 2017 um 16:02 Uhr
Bitte aktualisieren Sie die Antwort und verwenden Sie log2(). Ich habe einen Fehler gemacht, indem ich die Kommentare nicht gelesen habe, und habe bei einem CP-Wettbewerb einen großen Verlust erlitten. 🙁

– Abhishek

12. April 2020 um 16:15 Uhr

Fair genug, die Frage stellte keine Schleifen. Aber so clever einige der anderen Funktionen auch sind, bei Code, der nicht leistungsempfindlich ist, gewinnt für mich immer die Antwort, die schnell und einfach verstanden und auf Richtigkeit überprüft wird.

– Tim MB

17. Januar 2013 um 12:44 Uhr
Dies gibt nicht die nächste Potenz von 2 zurück, aber die Potenz davon ist sofort größer als X. Immer noch sehr gut

– KaffeeEntwickler

9. Juni 2013 um 16:34 Uhr
Anstatt zu multiplizieren, kann stattdessen etwas bitweise “Magie” verwendet werden power <<= 1

– Vallentin

30. Juli 2016 um 8:01 Uhr
@Vallentin Das sollte automatisch von einem Compiler optimiert werden.

– MarkWeston

5. Oktober 2017 um 5:59 Uhr
Vorsicht vor Endlosschleife if x zu groß ist (dh nicht genug Bits, um die nächste Potenz von 2 darzustellen).

– alban

22. März 2019 um 14:01 Uhr

Finsternis

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;

}

Wäre nett, wenn du es zugeschrieben hättest (sofern du es nicht entdeckt hast). Es kommt von der Bit Twiddling Hacks-Seite.

– Gulden

21. Januar 2009 um 17:47 Uhr
Ist das für eine 32-Bit-Zahl? Erweiterung für 64-Bit?

– Jonathan Leffler

21. Januar 2009 um 17:52 Uhr
@florin, wenn v ein 64-Bit-Typ ist, könnten Sie nicht einfach ein “c |= v >> 32” nach dem für 16 hinzufügen?

– Evan Teran

21. Januar 2009 um 18:18 Uhr
Seien Sie vorsichtig, wenn Sie signed int verwenden. Werte > 0x4000_0000_0000_0000 geben 0x8000_0000_0000_0000 zurück.

– Nathan

18. Oktober 2012 um 23:25 Uhr
Code, der nur für eine bestimmte Bitbreite funktioniert, sollte Typen mit fester Breite anstelle von Typen mit minimaler Breite verwenden. Diese Funktion sollte a annehmen und zurückgeben uint32_t.

– Craig Barnes

21. September 2018 um 21:38 Uhr

Gemeinschaft

Wenn Sie GCC verwenden, sollten Sie einen Blick auf werfen Optimierung der Funktion next_pow2() von Lockless Inc.. Auf dieser Seite wird beschrieben, wie Sie die integrierte Funktion verwenden können builtin_clz() (zählen Sie führende Nullen) und verwenden Sie später direkt x86 (ia32) Assembler-Anweisungen bsr (Bit Scan Reverse), genau wie es in einer anderen Antwort beschrieben ist Link zur Gamedev-Seite. 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, können Sie dies 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));
}

Wäre nett, wenn du es zugeschrieben hättest (sofern du es nicht entdeckt hast). Es kommt von der Bit Twiddling Hacks-Seite.

– Gulden

21. Januar 2009 um 17:47 Uhr
Ist das für eine 32-Bit-Zahl? Erweiterung für 64-Bit?

– Jonathan Leffler

21. Januar 2009 um 17:52 Uhr
@florin, wenn v ein 64-Bit-Typ ist, könnten Sie nicht einfach ein “c |= v >> 32” nach dem für 16 hinzufügen?

– Evan Teran

21. Januar 2009 um 18:18 Uhr
Seien Sie vorsichtig, wenn Sie signed int verwenden. Werte > 0x4000_0000_0000_0000 geben 0x8000_0000_0000_0000 zurück.

– Nathan

18. Oktober 2012 um 23:25 Uhr
Code, der nur für eine bestimmte Bitbreite funktioniert, sollte Typen mit fester Breite anstelle von Typen mit minimaler Breite verwenden. Diese Funktion sollte a annehmen und zurückgeben uint32_t.

– Craig Barnes

21. September 2018 um 21:38 Uhr

Eine weitere, obwohl ich Zyklus verwende, aber das ist viel schneller als mathematische Operanden

Zweierpotenz “Floor”-Option:

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

Zweierpotenz “Ceil”-Option:

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

AKTUALISIEREN

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

Hier sind die vollständigen 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;
}

das Ergebnis ist nicht korrekt, wenn x ist eine Potenz von 2. Ein Mikro zum Testen, ob der Eingang eine Potenz von 2 ist, wird benötigt. #define ISPOW2(x) ((x) > 0 && !((x) & (x-1)))

– pgplus1628

28. Oktober 2015 um 13:05 Uhr
@zorksylar wäre effizienter if (x == 0) return 1; /* Or 0 (Which is what I use) */ x--; /* Rest of program */

– yyny

3. März 2016 um 16:45 Uhr
Gute Lösung! aber die power of two "ceil" option das ist nicht richtig. Wann zum Beispiel x = 2 das Ergebnis sollte sein 2 Anstatt von 4

– MZD

18. August 2018 um 12:02 Uhr

14263400cookie-checkAufrunden auf die nächste Potenz von 2

#Bit-Manipulation #c++ #Optimierung