Was ist der einfachste Weg, um zu testen, ob eine Zahl in C ++ eine Zweierpotenz ist?

Ich brauche eine Funktion wie diese:

// return true iff 'n' is a power of 2, e.g.
// is_power_of_2(16) => true  is_power_of_2(3) => false
bool is_power_of_2(int n);

Kann mir jemand vorschlagen, wie ich das schreiben könnte? Können Sie mir eine gute Website nennen, auf der diese Art von Algorithmus zu finden ist?

(n & (n - 1)) == 0ist das Beste. Beachten Sie jedoch, dass für n = 0 fälschlicherweise true zurückgegeben wird. Wenn dies möglich ist, sollten Sie dies explizit überprüfen.

http://www.graphics.stanford.edu/~seander/bithacks.html verfügt über eine große Sammlung cleverer Bit-Twiddling-Algorithmen, einschließlich dieses.

Bei einer Zweierpotenz wird nur ein Bit gesetzt (für vorzeichenlose Zahlen). Etwas wie

bool powerOfTwo = !(x == 0) && !(x & (x - 1));

Wird gut funktionieren; Eins weniger als eine Zweierpotenz ist alles 1s in den weniger signifikanten Bits, muss also bitweise UND auf 0 sein.

Da ich vorzeichenlose Zahlen angenommen habe, ist der == 0-Test (den ich ursprünglich vergessen habe, sorry) ausreichend. Möglicherweise möchten Sie einen Test> 0, wenn Sie vorzeichenbehaftete Ganzzahlen verwenden.

Zweierpotenzen in Binärform sehen folgendermaßen aus:

1: 0001
2: 0010
4: 0100
8: 1000

Beachten Sie, dass immer genau 1 Bit gesetzt ist. Die einzige Ausnahme ist eine vorzeichenbehaftete Ganzzahl. Beispiel: Eine 8-Bit-Ganzzahl mit Vorzeichen und einem Wert von -128 sieht folgendermaßen aus:

10000000

Nachdem wir überprüft haben, ob die Zahl größer als Null ist, können wir mit einem cleveren kleinen Bit-Hack testen, ob nur ein Bit gesetzt ist.

bool is_power_of_2(int x) {
    return x > 0 && !(x & (x−1));
}

Weitere Informationen finden Sie hier .

Ansatz 1:

Teilen Sie die Zahl ausschließlich durch 2, um sie zu überprüfen.

Zeitliche Komplexität: O (log2n).

Ansatz 2:

Bitweise UND die Zahl mit der gerade vorherigen Zahl sollte gleich NULL sein.

Beispiel: Zahl = 8 Binär von 8: 1 0 0 0 Binär von 7: 0 1 1 1 und das bitweise UND beider Zahlen ist 0 0 0 0 = 0.

Zeitliche Komplexität: O (1).

Ansatz 3:

Bitweises XOR Die Zahl mit der gerade vorherigen Zahl sollte die Summe beider Zahlen sein.

Beispiel: Zahl = 8 Binär von 8: 1 0 0 0 Binär von 7: 0 1 1 1 und das bitweise XOR beider Zahlen ist 1 1 1 1 = 15.

Zeitliche Komplexität: O (1).

http://javaexplorer03.blogspot.in/2016/01/how-to-check-number-is-power-of-two.html

bool is_power_of_2(int i) {
    if ( i <= 0 ) {
        return 0;
    }
    return ! (i & (i-1));
}

Für jede Potenz von 2 gilt auch das Folgende.

n & (- n) == n

HINWEIS: Die Bedingung gilt für n = 0, obwohl es keine Potenz von 2 ist.
Grund dafür ist:
-n ist das 2s-Komplement von n. -n wird jedes Bit links vom am weitesten rechts gesetzten Bit von n im Vergleich zu n umgedreht haben. Für Potenzen von 2 gibt es nur ein gesetztes Bit.

In C ++ 20 gibt es eine, std::ispow2die Sie genau für diesen Zweck verwenden können, wenn Sie sie nicht selbst implementieren müssen:

#include <bit>
static_assert(std::ispow2(16));
static_assert(!std::ispow2(15));

Dies ist wahrscheinlich die schnellste, wenn Sie GCC verwenden. Es wird nur eine POPCNT-CPU-Anweisung und ein Vergleich verwendet. Bei der binären Darstellung einer Potenz mit 2 Zahlen wird immer nur ein Bit gesetzt, andere Bits sind immer Null. Wir zählen also die Anzahl der gesetzten Bits mit POPCNT, und wenn es gleich 1 ist, ist die Zahl die Potenz von 2. Ich glaube, es gibt keine möglichen schnelleren Methoden. Und es ist sehr einfach, wenn Sie es einmal verstanden haben:

if(1==__builtin_popcount(n))

Das Folgen wäre aufgrund des booleschen Kurzschlusses und der Tatsache, dass der Vergleich langsam ist, schneller als die am häufigsten abgestimmte Antwort.

int isPowerOfTwo(unsigned int x)
{
  return x && !(x & (x – 1));
}

Wenn Sie wissen, dass x nicht 0 sein kann, dann

int isPowerOfTwo(unsigned int x)
{
  return !(x & (x – 1));
}

return n > 0 && 0 == (1 << 30) % n;

Was ist der einfachste Weg, um zu testen, ob eine Zahl in C ++ eine Zweierpotenz ist?

Wenn Sie einen modernen Intel-Prozessor mit den Bit-Manipulationsanweisungen haben , können Sie Folgendes ausführen. Der reine C / C ++ - Code wird weggelassen, da andere ihn bereits beantwortet haben. Sie benötigen ihn jedoch, wenn der BMI nicht verfügbar oder aktiviert ist.

bool IsPowerOf2_32(uint32_t x)
{
#if __BMI__ || ((_MSC_VER >= 1900) && defined(__AVX2__))
    return !!((x > 0) && _blsr_u32(x));
#endif
    // Fallback to C/C++ code
}

bool IsPowerOf2_64(uint64_t x)
{
#if __BMI__ || ((_MSC_VER >= 1900) && defined(__AVX2__))
    return !!((x > 0) && _blsr_u64(x));
#endif
    // Fallback to C/C++ code
}

GCC, ICC und Clang signalisieren BMI-Unterstützung mit __BMI__. Es ist in Microsoft Compilern in Visual Studio 2015 und höher verfügbar, wenn AVX2 verfügbar und aktiviert ist . Informationen zu den benötigten Headern finden Sie unter Header-Dateien für SIMD-Eigenheiten .

Normalerweise bewache ich das _blsr_u64mit einem _LP64_Fall, der auf i686 kompiliert wird. Clang benötigt eine kleine Problemumgehung, da ein etwas anderer intrinsischer Symbolname verwendet wird:

#if defined(__GNUC__) && defined(__BMI__)
# if defined(__clang__)
#  ifndef _tzcnt_u32
#   define _tzcnt_u32(x) __tzcnt_u32(x)
#  endif
#  ifndef _blsr_u32
#    define  _blsr_u32(x)  __blsr_u32(x)
#  endif
#  ifdef __x86_64__
#   ifndef _tzcnt_u64
#    define _tzcnt_u64(x) __tzcnt_u64(x)
#   endif
#   ifndef _blsr_u64
#     define  _blsr_u64(x)  __blsr_u64(x)
#   endif
#  endif  // x86_64
# endif  // Clang
#endif  // GNUC and BMI

Können Sie mir eine gute Website nennen, auf der diese Art von Algorithmus zu finden ist?

Diese Website wird oft zitiert: Bit Twiddling Hacks .

Dies ist nicht der schnellste oder kürzeste Weg, aber ich denke, er ist sehr gut lesbar. Also würde ich so etwas machen:

bool is_power_of_2(int n)
  int bitCounter=0;
  while(n) {
    if ((n & 1) == 1) {
      ++bitCounter;
    }
    n >>= 1;
  }
  return (bitCounter == 1);
}

Dies funktioniert, da Binär auf Zweierpotenzen basiert. Jede Zahl mit nur einem gesetzten Bit muss eine Zweierpotenz sein.

Hier ist eine andere Methode, in diesem Fall |anstelle von &:

bool is_power_of_2(int x) {
    return x > 0 && (x<<1 == (x|(x-1)) +1));
}

Es ist möglich durch c ++

int IsPowOf2(int z) {
double x=log2(z);
int y=x;
if (x==(double)y)
return 1;
else
return 0;
}

Ich weiß, dass dies ein sehr alter Beitrag ist, aber ich dachte, es könnte interessant sein, dies hier zu posten.

Von Code-Golf SE (also alle Ehre gebührt denjenigen, die dies geschrieben haben): Showcase of Languages

(Absatz über C , Unterabsatz Länge 36 Ausschnitt )

bool isPow2(const int num){return!!num&!(num&(num-1));}

Ein anderer Weg (vielleicht nicht der schnellste) besteht darin, festzustellen, ob ln (x) / ln (2) eine ganze Zahl ist.

Dies ist die Bitverschiebungsmethode in T-SQL (SQL Server):

SELECT CASE WHEN @X>0 AND (@X) & (@X-1)=0 THEN 1 ELSE 0 END AS IsPowerOfTwo

Es ist viel schneller als viermal einen Logarithmus zu erstellen (erster Satz, um ein Dezimalergebnis zu erhalten, zweiter Satz, um eine Ganzzahl zu erhalten und zu vergleichen)