Alte macht 2

Gibt es eine Menge Informationen, wie man die nächste Potenz von 2 ist von einem bestimmten Wert (siehe refs) aber ich finde keine, um die bisherige Leistung der beiden.

Nur so, ich finde so weit ist, um einen Tisch mit aller macht von zwei bis zu 2^64, und eine einfache Suche.

Holen Sie sich die nächste Potenz von 2 ist, und durch 2 dividieren...?
Binäre Verschiebung? Teilen?
Die nächste, durch 2 dividieren.
Dies sollte eine ziemlich einfache Anpassung der bestehenden algorithmen, die Sie miteinander verknüpft. Können Sie veröffentlichen, was Sie haben, und wir können Ihnen helfen, zusammen mit Tipps?
Er bittet für die Kraft der zwei, die am nächsten an einem vorgegebenen Wert (und weniger als, nicht größer als der angegebene Wert)
klar, alle, aber die meisten signifikanten bit. es ist ein allgemein gültiges Rezept, können Sie in vielfältiger Weise umgesetzt
Danke, das macht diese Frage viel mehr Sinn.

InformationsquelleAutor Horacio | 2010-04-21

algorithm

31

Vom Hacker ' s Delight, einen schönen astfreie Lösung:
```
uint32_t flp2 (uint32_t x)
{
    x = x | (x >> 1);
    x = x | (x >> 2);
    x = x | (x >> 4);
    x = x | (x >> 8);
    x = x | (x >> 16);
    return x - (x >> 1);
}
```
Dies dauert in der Regel 12 Anweisungen. Sie können es in weniger, wenn Ihre CPU verfügt über den "count leading zeroes" - Anweisung.
- FWIW, dies ist deutlich schneller als die bsr Lösung für AMD CPUs, 3-4x schneller für eine 32-bit-version und 1,5-2x für 64-bit-version. Ich habe gehört, es ist das Gegenteil für Intel, aber ich haben keinen Zugriff auf Ihre CPUs zu testen.
InformationsquelleAutor Paul R
2
```
uint32_t previous_power_of_two( uint32_t x ) {
    if (x == 0) {
        return 0;
    }
    //x--; Uncomment this, if you want a strictly less than 'x' result.
    x |= (x >> 1);
    x |= (x >> 2);
    x |= (x >> 4);
    x |= (x >> 8);
    x |= (x >> 16);
    return x - (x >> 1);
}
```
Danke für die Antworten. Ich werde versuchen, zusammenfassen und erklären, ein wenig etwas klarer.
Was dieser Algorithmus tut, verändert sich zu 'lieben' alle bits nach dem ersten " ein " - bit, verursachen diese sind die einzigen bits, die machen können, unser 'x' größer als der vorhergehende Potenz von zwei.
Nachdem Sie sicher, Sie sind 'diejenigen', es entfernt nur Ihnen verlassen die ersten 'ein' bit intakt. Das einzige bisschen an seiner Stelle unserer bisherigen Leistung der beiden.

InformationsquelleAutor Vladius
2

Wohl die einfachste Methode (für positive zahlen):
```
//find next (must be greater) power, and go one back
p = 1; while (p <= n) p <<= 1; p >>= 1;
```
Können Sie Variationen in viele Richtungen, wenn Sie wollen zu optimieren.

InformationsquelleAutor Anycorn
1

Ist hier ein Einzeiler für die Nachwelt (ruby):
```
2**Math.log(input, 2).floor(0)
```
- Mit floating-point Mathematik für das ist ernst overkill.
- Er zählt die Frage unter "Algorithmus", also gab ich eine Lösung, die Algorithmus orientiert.
- Das war genau die information, die ich hoffte zu finden, wenn ich " gegoogelt "nächste Potenz von 2" und fand diese StackOverflow-Frage.
InformationsquelleAutor Nicolas Goy
0

Wenn man die nächst höhere Potenz von 2, der nächst-niedrigeren Potenz von 2 ist entweder der nächst höhere oder die Hälfte. Es hängt davon ab, was man als die "nächsthöhere" für eine beliebige Potenz von 2 ist (und was Sie betrachten, um die nächst-niedrigeren Potenz von 2).

InformationsquelleAutor Vatine
0

Was
```
if (tt = v >> 16)
{
   r = (t = tt >> 8) ? 0x1000000 * Table256[t] : 0x10000 * Table256[tt];
}
else 
{
  r = (t = v >> 8) ? 0x100 * Table256[t] : Table256[v];
}
```
Ist es nur modifizierte Methode von http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogLookup.
Diese erfordern, wie 7 Operationen und es könnte schneller zum ersetzen von Multiplikationen mit shift.

InformationsquelleAutor Luka Rahne
-1

Wenn Sie die Arbeit in der Basis 2, springen Sie von eine Potenz von zwei, um die nächsten ein, indem Sie einfach hinzufügen oder entfernen einer Ziffer aus der rechten Seite.

Zum Beispiel, die frühere macht der zwei, die Zahl 8 ist die Zahl 4. In Binär:

01000 -> 0100 (wir entnehmen die nachfolgenden null zu bekommen, Nummer 4)

Also den Algorithmus zum lösen der Rechnung von der vorherigen Leistung der beiden ist:

previousPower := Zahl shr 1

previousPower = Zahl >> 1

(oder eine beliebige andere syntax)
- Dies gilt nur, wenn number ist auch eine Potenz von 2 ist. Wenn number ist sagen wir 11, dann wird dies nicht funktionieren.
InformationsquelleAutor Manuel Gonzalez

-1

Diese kann getan werden, in einer Zeile.

int nextLowerPowerOf2 = i <= 0
                        ? 0
                        : ((i & (~i + 1)) == i)
                            ? i >> 1
                            : (1 << (int)Math.Log(i, 2));

Ergebnis

i    power_of_2
-2    0
-1    0
0    0
1    0
2    1
3    2
4    2
5    4
6    4
7    4
8    4
9    8

Hier eine besser lesbare version in c#, mit der <=0 guard-Klausel verteilt, um die utility-Methoden.

int nextLowerPowerOf2 = IsPowerOfTwo(i) 
    ? i >> 1 //shift it right
    : GetPowerOfTwoLessThanOrEqualTo(i);

public static int GetPowerOfTwoLessThanOrEqualTo(int x)
{
    return (x <= 0 ? 0 : (1 << (int)Math.Log(x, 2)));
}

public static bool IsPowerOfTwo(int x)
{
    return (((x & (~x + 1)) == x) && (x > 0));
}

Mit floating-point Mathematik für das ist ernst overkill.

InformationsquelleAutor Handcraftsman

-2

Code unten finden Sie die bisherige Leistung von 2:
```
int n = 100;
    n /= 2;//commenting this will gives the next power of 2
    n |= n>>1;
    n |= n>>2;
    n |= n>>4;
    n |= n>>16;

System.out.println(n+1);
```
- Andere Antworten sind sehr ähnlich, und dieser zurückgeben, falsche Ergebnisse, wenn n eine Potenz von 2 ist schon.
InformationsquelleAutor Ram Kumar
-5

Dies ist meine aktuelle Lösung zu finden, die nächsten und vorherigen Potenzen von zwei beliebigen positiven Ganzzahl n und auch eine kleine Funktion, um zu bestimmen, ob eine Zahl Potenz von zwei.

Diese Implementierung für Ruby.
```
class Integer

  def power_of_two?
    (self & (self - 1) == 0)
  end

  def next_power_of_two
    return 1 if self <= 0
    val = self
    val = val - 1
    val = (val >> 1) | val
    val = (val >> 2) | val
    val = (val >> 4) | val
    val = (val >> 8) | val
    val = (val >> 16) | val
    val = (val >> 32) | val if self.class == Bignum
    val = val + 1
  end

  def prev_power_of_two
   return 1 if self <= 0
   val = self
   val = val - 1
   val = (val >> 1) | val
   val = (val >> 2) | val
   val = (val >> 4) | val
   val = (val >> 8) | val
   val = (val >> 16) | val
   val = (val >> 32) | val if self.class == Bignum
   val = val - (val >> 1)
  end
end
```
Beispiel verwenden:
```
10.power_of_two? => false
16.power_of_two? => true
10.next_power_of_two => 16
10.prev_power_of_two => 8
```
Für die bisherige Leistung der beiden, der Suche nach dem nächsten und Division durch zwei ist etwas langsamer als die oben genannte Methode.

Ich bin nicht sicher, wie es funktioniert mit Bignums.
- Hey, Etikette ist es, dass Sie ausgezeichnet die Antwort der Kerl, gab Sie die Idee in den ersten Platz. Ich denke, es ist schlechte form, um die Auszeichnung selbst die richtige Antwort in diesem Fall.
- Tun die markierte Antwort gibt etwas auf das Plakat? Ich dachte, die Antwort markiert werden sollten, die am meisten nützlich, um anderen mit der gleichen Frage. Dieser fasst die ganze Diskussion in einem einzigen, einfach zu verstehen, Antworten.
InformationsquelleAutor Horacio

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.