Wie finde ich bei einer gegebenen Ganzzahl die nächstgrößere Zweierpotenz mithilfe von Bit-Twiddling?

72

Wenn ich eine ganzzahlige Zahl habe n, wie kann ich die nächste Zahl k > nso finden, dass k = 2^imit einem iElement von Ndurch bitweise Verschiebung oder Logik.

Beispiel: Wenn n = 123ja, wie kann ich herausfinden k = 128, welche Zweierpotenz ist und welche nicht 124nur durch zwei teilbar ist? Das sollte einfach sein, aber es entgeht mir.

AndreasT
quelle
3
Dies wäre eine großartige Interviewfrage.
Rick Minerich
7
@ Rick: Ich hoffe du bist kein Interviewer und ich habe jetzt einen armen Bewerber in eine schwierige Situation gebracht ;-)
AndreasT
1
Könnte ein Duplikat von stackoverflow.com/questions/466204/… sein , auch hier könnten Antworten auf diese Frage von Interesse sein.
Yann Droneaud
Wenn n = 128, möchten Sie k = 128 oder k = 256 finden?
Endolith

Antworten:

95

Für 32-Bit-Ganzzahlen ist dies eine einfache und unkomplizierte Route:

unsigned int n;

n--;
n |= n >> 1;   // Divide by 2^k for consecutive doublings of k up to 32,
n |= n >> 2;   // and then or the results.
n |= n >> 4;
n |= n >> 8;
n |= n >> 16;
n++;           // The result is a number of 1 bits equal to the number
               // of bits in the original number, plus 1. That's the
               // next highest power of 2.

Hier ist ein konkreteres Beispiel. Nehmen wir die Zahl 221, die binär 11011101 ist:

n--;           // 1101 1101 --> 1101 1100
n |= n >> 1;   // 1101 1100 | 0110 1110 = 1111 1110
n |= n >> 2;   // 1111 1110 | 0011 1111 = 1111 1111
n |= n >> 4;   // ...
n |= n >> 8;
n |= n >> 16;  // 1111 1111 | 1111 1111 = 1111 1111
n++;           // 1111 1111 --> 1 0000 0000

Es gibt ein Bit an der neunten Position, das 2 ^ 8 oder 256 darstellt, was in der Tat die nächstgrößere Potenz von 2 ist . Jede der Verschiebungen überlappt alle vorhandenen 1 Bits in der Zahl mit einigen der zuvor unberührten Nullen, wodurch schließlich eine Anzahl von 1 Bits erzeugt wird, die der Anzahl der Bits in der ursprünglichen Zahl entspricht. Das Hinzufügen von eins zu diesem Wert ergibt eine neue Potenz von 2.

Ein anderes Beispiel; Wir werden 131 verwenden, was 10000011 in binär ist:

n--;           // 1000 0011 --> 1000 0010
n |= n >> 1;   // 1000 0010 | 0100 0001 = 1100 0011
n |= n >> 2;   // 1100 0011 | 0011 0000 = 1111 0011
n |= n >> 4;   // 1111 0011 | 0000 1111 = 1111 1111
n |= n >> 8;   // ... (At this point all bits are 1, so further bitwise-or
n |= n >> 16;  //      operations produce no effect.)
n++;           // 1111 1111 --> 1 0000 0000

Und tatsächlich ist 256 die nächsthöhere Potenz von 2 von 131.

Wenn die Anzahl der zur Darstellung der Ganzzahl verwendeten Bits selbst eine Zweierpotenz ist, können Sie diese Technik weiterhin effizient und unbegrenzt erweitern (z. B. eine n >> 32Zeile für 64-Bit-Ganzzahlen hinzufügen ).

John Feminella
quelle
1
@AndreasT: Kein Problem! (Übrigens, um zu sehen, warum Sie bis zu n >> 16 gehen müssen, überlegen Sie, was passiert, wenn n bereits eine Potenz von 2 ist. Sie haben nur ein einziges 1-Bit, das alle vorherigen Bits abdecken muss , weshalb alle Verschiebung notwendig ist.)
John Feminella
2
+1 ja, guter Trick, ich mag es :) Einige weitere Tricks finden Sie hier: graphics.stanford.edu/~seander/bithacks.html
zxcat
1
Obwohl dies funktioniert, könnte jemand bitte eine Erklärung geben, warum es funktioniert?
Divick
1
@endolith Das dauert log N Verschiebungen. Dies erfordert logarithmische (log N) Verschiebungen, sodass weniger Schichten verwendet werden.
John Feminella
1
Es tut k >= nnichtk > n
Jwalker
30

Hierfür gibt es tatsächlich eine Montagelösung (seit dem 80386-Befehlssatz).

Mit der Anweisung BSR (Bit Scan Reverse) können Sie nach dem höchstwertigen Bit in Ihrer Ganzzahl suchen.

bsr scannt die Bits beginnend mit dem höchstwertigen Bit im Doppelwortoperanden oder im zweiten Wort. Wenn alle Bits Null sind, wird ZF gelöscht. Andernfalls wird ZF gesetzt und der Bitindex des ersten gesetzten gesetzten Bits wird beim Scannen in umgekehrter Richtung in das Zielregister geladen

(Auszug aus: http://dlc.sun.com/pdf/802-1948/802-1948.pdf )

Und dann inc das Ergebnis mit 1.

damit:

bsr ecx, eax  //eax = number
jz  @zero
mov eax, 2    // result set the second bit (instead of a inc ecx)
shl eax, ecx  // and move it ecx times to the left
ret           // result is in eax

@zero:
xor eax, eax
ret

In neueren CPUs können Sie die viel schnellere lzcntAnweisung (auch bekannt als rep bsr) verwenden. lzcnterledigt seine Arbeit in einem einzigen Zyklus.

Davy Landman
quelle
Wenn Ihre Eingabe bereits eine Potenz von 2 ist, wird dies jedoch nicht zurückgegeben
Endolith
21

Ein mathematischerer Weg ohne Schleifen:

public static int ByLogs(int n)
{
    double y = Math.Floor(Math.Log(n, 2));

    return (int)Math.Pow(2, y + 1);
}
DanDan
quelle
2
Vielen Dank. Aber ich suchte nach einem "kleinen Weg". ;-)
AndreasT
5
+1, nicht das, was das OP wollte, aber seltsamerweise brauchte ich eine Antwort, die in einen einzelnen Inline-Ausdruck passen würde:2 ^ (floor(log(x) / log(2)) + 1)
zildjohn01
3
Sie erhalten den vorhandenen Wert. Der nächste Teil, y + 1, bringt dir die nächstgrößere Potenz.
DanDan
1
@ DanDan: aber wenn n bereits eine Potenz von 2 ist, gibt es die nächste Potenz von 2, anstatt n
Endolith
2
@endolith: Wenn nes sich um eine Zweierpotenz handelt und Sie nanstelle der "nächsten Zweierpotenz" erhalten möchten , können Sie 2 ^ ( ceil(log(x) / log(2)) )stattdessen verwenden. Aber das war nicht die Frage (… wie kann ich die nächste Nummer finden k > n…)
Wauzl
12

Hier ist eine logische Antwort:

function getK(int n)
{
  int k = 1;
  while (k < n)
    k *= 2;
  return k;
}
JustLoren
quelle
Ha, so einfach! Ich habe nicht darüber
nachgedacht
8

Hier ist John Feminellas Antwort, die als Schleife implementiert ist, damit sie Pythons lange ganze Zahlen verarbeiten kann :

def next_power_of_2(n):
    """
    Return next power of 2 greater than or equal to n
    """
    n -= 1 # greater than OR EQUAL TO n
    shift = 1
    while (n+1) & n: # n+1 is not a power of 2 yet
        n |= n >> shift
        shift <<= 1
    return n + 1

Es kehrt auch schneller zurück, wenn n bereits eine Potenz von 2 ist.

Für Python> 2.7 ist dies für die meisten N einfacher und schneller:

def next_power_of_2(n):
    """
    Return next power of 2 greater than or equal to n
    """
    return 2**(n-1).bit_length()

Geben Sie hier die Bildbeschreibung ein

Endolith
quelle
2
Wenn Sie Bitverschiebungen verwenden möchten, können Sie dies auch shift <<= 1anstelle von tun shift *= 2. Ich bin mir nicht sicher, ob das in Python tatsächlich schneller ist, sollte es aber sein.
Chris Middleton
4

Größer als / Größer als oder gleich

Die folgenden Ausschnitte sind für die nächste Zahl k> n, so dass k = 2 ^ i
(n = 123 => k = 128, n = 128 => k = 256), wie durch OP angegeben.

Wenn Sie möchten, dass die kleinste Potenz von 2 größer als OR gleich n ist, ersetzen Sie sie einfach __builtin_clzll(n)durch __builtin_clzll(n-1)die obigen Schnipsel.

C ++ 11 mit GCC oder Clang (64 Bit)

constexpr uint64_t nextPowerOfTwo64 (uint64_t n)
{
    return 1ULL << (sizeof(uint64_t) * 8 - __builtin_clzll(n));
}

Verbesserung mit CHAR_BITwie von martinec vorgeschlagen

#include <cstdint>

constexpr uint64_t nextPowerOfTwo64 (uint64_t n)
{
    return 1ULL << (sizeof(uint64_t) * CHAR_BIT - __builtin_clzll(n));
}

C ++ 17 mit GCC oder Clang (von 8 bis 128 Bit)

#include <cstdint>

template <typename T>
constexpr T nextPowerOfTwo64 (T n)
{
   T clz = 0;
   if constexpr (sizeof(T) <= 32)
      clz = __builtin_clzl(n); // unsigned long
   else if (sizeof(T) <= 64)
      clz = __builtin_clzll(n); // unsigned long long
   else { // See https://stackoverflow.com/a/40528716
      uint64_t hi = n >> 64;
      uint64_t lo = (hi == 0) ? n : -1ULL;
      clz = _lzcnt_u64(hi) + _lzcnt_u64(lo);
   }
   return T{1} << (CHAR_BIT * sizeof(T) - clz);
}

Andere Compiler

Wenn Sie einen anderen Compiler als GCC oder Clang verwenden, besuchen Sie bitte die Wikipedia-Seite, auf der die bitweisen Funktionen von Count Leading Zeroes aufgeführt sind :

  • Visual C ++ 2005 => Ersetzen __builtin_clzl()durch_BitScanForward()
  • Visual C ++ 2008 => Ersetzen __builtin_clzl()durch__lzcnt()
  • icc => Ersetzen __builtin_clzl()durch_bit_scan_forward
  • GHC (Haskell) => Ersetzen __builtin_clzl()durchcountLeadingZeros()

Beitrag willkommen

Bitte schlagen Sie Verbesserungen in den Kommentaren vor. Schlagen Sie auch eine Alternative für den von Ihnen verwendeten Compiler oder Ihre Programmiersprache vor ...

Siehe auch ähnliche Antworten

oho
quelle
3

Hier ist eine wilde, die keine Schleifen hat, aber einen Zwischen-Float verwendet.

//  compute k = nextpowerof2(n)

if (n > 1) 
{
  float f = (float) n;
  unsigned int const t = 1U << ((*(unsigned int *)&f >> 23) - 0x7f);
  k = t << (t < n);
}
else k = 1;

Dieser und viele andere Hacks, einschließlich der von John Feminella eingereichten, finden Sie hier .

IJ Kennedy
quelle
1
wtf! 8-), werde es überprüfen. Thx
AndreasT
2

Angenommen, x ist nicht negativ.

int pot = Integer.highestOneBit(x);
if (pot != x) {
    pot *= 2;
}
Alex Cohn
quelle
2

Wenn Sie GCC, MinGW oder Clang verwenden:

template <typename T>
T nextPow2(T in)
{
  return (in & (T)(in - 1)) ? (1U << (sizeof(T) * 8 - __builtin_clz(in))) : in;
}

Wenn Sie Microsoft Visual C ++ verwenden, verwenden Sie die Funktion _BitScanForward()zum Ersetzen __builtin_clz().

Nulleight
quelle
1
Siehe auch ähnliche Antwort in einer anderen Frage: stackoverflow.com/a/10143264/938111 (beantwortet von ydroneaud im Jahr 2012). Siehe Wikipedia integrierte bitweise Funktionen für andere Compiler: en.wikipedia.org/wiki/Find_first_set#Tool_and_library_support             Dies ist eine C ++ 64-Bit-Version:        constexpr uint64_t nextPowerOfTwo64 (uint64_t x) { return 1ULL << (sizeof(uint64_t) * 8 - __builtin_clzll(x)); }
oHo
1
function Pow2Thing(int n)
{
    x = 1;
    while (n>0)
    {
        n/=2;
        x*=2;
    }
    return x;
}
Rik Heywood
quelle
1

Bit-Twiddling, sagst du?

long int pow_2_ceil(long int t) {
    if (t == 0) return 1;
    if (t != (t & -t)) {
        do {
            t -= t & -t;
        } while (t != (t & -t));
        t <<= 1;
    }
    return t;
}

Jede Schleife entfernt das niedrigstwertige 1-Bit direkt. NB Dies funktioniert nur, wenn vorzeichenbehaftete Nummern im Zweierkomplement codiert sind.

Derek Illchuk
quelle
1
Sie können Ihre sicher ersetzen whilemit do/whileund speichert einen Test, wie Sie bereits den ersten Test mit der vorhergehenden bestätigten ifAussage.
seh
Danke @seh; verbessert mit do while.
Derek Illchuk
Schnellste Methode hier, warum keine Upvotes? Obwohl ich zu gewechselt habe while(t > (t & -t)).
Primo
@primo Zumindest in C # ist die akzeptierte Antwort für 32-Bit-Ganzzahlen im Durchschnitt mehr als 2,5-mal schneller.
NetMage
0

Was ist mit so etwas:

int pot = 1;
for (int i = 0; i < 31; i++, pot <<= 1)
    if (pot >= x)
        break;
Eric
quelle
0

Sie müssen nur das höchstwertige Bit finden und es einmal nach links verschieben. Hier ist eine Python-Implementierung. Ich denke, x86 hat eine Anweisung, um das MSB zu erhalten, aber hier implementiere ich alles in reinem Python. Sobald Sie das MSB haben, ist es einfach.

>>> def msb(n):
...     result = -1
...     index = 0
...     while n:
...         bit = 1 << index
...         if bit & n:
...             result = index
...             n &= ~bit
...         index += 1
...     return result
...
>>> def next_pow(n):
...     return 1 << (msb(n) + 1)
...
>>> next_pow(1)
2
>>> next_pow(2)
4
>>> next_pow(3)
4
>>> next_pow(4)
8
>>> next_pow(123)
128
>>> next_pow(222)
256
>>>
FogleBird
quelle
Wenn Sie in einer Python-Antwort über Assembly sprechen, wird kein Wert
hinzugefügt,
0

Vergiss das! Es verwendet Schleife!

     unsigned int nextPowerOf2 ( unsigned int u)
     {
         unsigned int v = 0x80000000; // supposed 32-bit unsigned int

         if (u < v) {
            while (v > u) v = v >> 1;
         }
         return (v << 1);  // return 0 if number is too big
     }
Nunkown
quelle
0
private static int nextHighestPower(int number){
    if((number & number-1)==0){
        return number;
    }
    else{
        int count=0;
        while(number!=0){
            number=number>>1;
            count++;
        }
        return 1<<count;
    }
}
verschwenderisch
quelle
-3
// n is the number
int min = (n&-n);
int nextPowerOfTwo = n+min;
Paras
quelle
Ist das die Idee: Füllen Sie alle Einsen bis zum größten, aktuell aktivierten Bit aus? Wenn ja, wäre es n+min+1?
Garet Claborn
Dies schlägt fehl. (5 & -5) = 1; 5 + 1 = 6.
Olathe
-3
#define nextPowerOf2(x, n) (x + (n-1)) & ~(n-1)

oder auch

#define nextPowerOf2(x, n)  x + (x & (n-1)) 
Araceli
quelle