webentwicklung-frage-antwort-db.com.de

Wie lässt sich am einfachsten testen, ob eine Zahl in C++ eine 2 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 dieser Algorithmus zu finden ist?

72
Ant

(n & (n - 1)) == 0 ist am besten. Beachten Sie jedoch, dass falsch für n = 0 true zurückgegeben wird. Wenn dies möglich ist, möchten Sie dies explizit überprüfen.

http://www.graphics.stanford.edu/~seander/bithacks.html verfügt über eine große Sammlung intelligenter Bit-Twiddling-Algorithmen, darunter auch diesen.

156
Anonymous

Bei Zweierpotenzen wird nur ein Bit gesetzt (für vorzeichenlose Zahlen). So etwas wie

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

Funktioniert gut; Eins weniger als eine Zweierpotenz ist alle 1en in den niederwertigen Bits, also muss AND auf 0 bitweise stehen.

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.

72
Adam Wright

Zweierpotenzen im Binärmodus 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. z.B. Eine vorzeichenbehaftete 8-Bit-Ganzzahl mit einem Wert von -128 sieht folgendermaßen aus:

10000000

Nachdem wir also überprüft haben, dass die Zahl größer als Null ist, können wir einen cleveren kleinen Hack verwenden, um zu testen, dass nur ein Bit gesetzt ist.

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

Mehr dazu finden Sie hier .

44
Matt Howells

Ansatz # 1:

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

Zeitkomplexität: O (log2n).

Ansatz Nr. 2:

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

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

Zeitkomplexität: O (1).

Ansatz # 3:

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

Beispiel: Number = 8 Binärzahl von 8: 1 0 0 0 Binärzahl von 7: 0 1 1 1 und die bitweise XOR beider Zahlen ist 1 1 1 1 = 15 .

Zeitkomplexität: O (1).

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

12
Raj Dixit
bool is_power_of_2(int i) {
    if ( i <= 0 ) {
        return 0;
    }
    return ! (i & (i-1));
}
5
Rob Wells

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 2er-Komplement von n. -n wird jedes Bit links von rechts ganz gesetztes Bit von n umgedreht im Vergleich zu n haben. Für Potenzen von 2 gibt es nur ein gesetztes Bit.

3
FReeze FRancis
return n > 0 && 0 == (1 << 30) % n;
3
Yuxiang Zhang

Wie lässt sich am einfachsten testen, ob eine Zahl in C++ eine 2 ist?

Wenn Sie über einen modernen Intel-Prozessor mit der Bit-Manipulationsanweisung verfügen, können Sie Folgendes ausführen. Es wird der direkte C/C++ - Code 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
}

Unterstützung für GCC, ICC und Clang signalisiert BMI mit __BMI__. Es ist in Microsoft-Compilern in Visual Studio 2015 und höher verfügbar, wenn AVX2 verfügbar und aktiviert ist . Für die Header, die Sie benötigen, siehe Header-Dateien für SIMD-Intrinsics .

Normalerweise bewache ich den _blsr_u64 mit einem _LP64_, falls ich auf i686 kompiliere. Clang benötigt eine kleine Problemumgehung, da es ein etwas anderes intrinsisches Symbol nam verwendet:

#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 dieser Algorithmus zu finden ist?

Diese Website wird häufig zitiert: Bit Twiddling Hacks .

2
jww

Die Folge wäre aufgrund boolescher Kurzschlüsse und der Tatsache, dass der Vergleich langsam ist, schneller als die meistgestimmte 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));
}
2
Margus

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

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

Dies ist nicht der schnellste oder kürzeste Weg, aber ich denke, dass er sehr gut lesbar ist. 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 Potenzen von zwei basiert. Jede Zahl mit nur einem gesetzten Bit muss eine Zweierpotenz sein.

1
Jere.Jones

Dies ist die schnellste:

if(1==__builtin_popcount(n))
1
F10PPY

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));
}
0
Chethan

Es ist durch C++ möglich

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