Wie prüft diese bitweise Operation auf eine Potenz von 2?

Ich schaue mir einen Code an, der trivial sein sollte – aber meine Mathematik versagt hier kläglich.

Hier ist eine Bedingung, die überprüft, ob eine Zahl eine Potenz von 2 ist, indem Folgendes verwendet wird:

if((num != 1) && (num & (num - 1))) { /* make num pow of 2 */ }

Meine Frage ist, wie bestimmt die Verwendung eines bitweisen AND zwischen num und num – 1, ob eine Zahl eine Potenz von 2 ist?

Jede Potenz von 2 minus 1 ist alles Einsen: (2 ^N – 1 = 111….b)

2 = 2^1.  2-1 = 1 (1b)
4 = 2^2.  4-1 = 3 (11b)
8 = 2^3.  8-1 = 7 (111b)

Nehmen Sie zum Beispiel 8. 1000 & 0111 = 0000

Dieser Ausdruck testet also, ob eine Zahl KEINE Potenz von 2 ist.

Nun, der erste Fall prüft auf 2⁰ == 1.

Für die anderen Fälle die num & (num - 1) kommt ins Spiel:

Das heißt, wenn Sie eine beliebige Zahl nehmen und die Bits von einer niedrigeren maskieren, erhalten Sie einen von zwei Fällen:

1. Wenn die Zahl bereits eine Zweierpotenz ist, führt eine Zahl weniger zu einer Binärzahl, bei der nur die niederwertigen Bits gesetzt sind. Verwenden & es wird nichts tun.

   • Beispiel mit 8: 0100 & (0100 - 1) –> (0100 & 0011) –> 0000

2. Wenn die Zahl nicht bereits eine Zweierpotenz ist, berührt eins weniger nicht das höchste Bit, also wird das Ergebnis sein wenigstens die größte Zweierpotenz kleiner als num.

   • Beispiel mit 3: 0011 & (0011 - 1) –> (0011 & 0010) –> 0010

   • Beispiel mit 13: 1101 & (1101 - 1) –> (1101 & 1100) –> 1100

Der tatsächliche Ausdruck findet also alles, was keine Zweierpotenz ist, einschließlich 2⁰.

Brunnen,

Wenn Sie X = 1000 haben, dann ist x-1 = 0111. Und 1000 && 0111 ist 0000.

Jede Zahl X, die eine Potenz von 2 ist, hat eine x-1, die Einsen an der Stelle hat, an der x Nullen hat. Und ein bitweises und von 0 und 1 ist immer 0.

Wenn die Zahl x keine Zweierpotenz ist, zum Beispiel 0110. Das x-1 ist 0101 und das und ergibt 0100.

Für alle Kombinationen innerhalb von 0000 – 1111 führt dies zu

   X  X-1 X && X-1  
0000 1111 0000   
0001 0000 0000 
0010 0001 0000
0011 0010 0010
0100 0011 0000
0101 0100 0100
0110 0101 0100
0111 0110 0110
1000 0111 0000
1001 1000 1000
1010 1001 1000
1011 1010 1010
1100 1011 1000
1101 1100 1100
1110 1101 1100
1111 1110 1110

Und es bedarf keiner gesonderten Prüfung für 1.

Ich bevorzuge diesen Ansatz, der auf dem Zweierkomplement beruht:

bool checkPowTwo(int x){
    return (x & -x) == x;
}

Erklärt hier schön

Auch der angegebene Ausdruck betrachtet 0 als Potenz von 2. Um dies zu beheben, verwenden Sie
!(x & (x - 1)) && x; stattdessen.

Es bestimmt, ob Integer eine Potenz von 2 ist oder nicht. Wenn (x & (x-1)) Null ist, dann ist die Zahl eine Potenz von 2.

Lassen Sie zum Beispiel x 8 sein (1000 in binär); dann x-1 = 7 (0111).

if    1000
  &   0111
---------------
      0000

C-Programm zur Demonstration:

#include <stdio.h>

void main()
{
    int a = 8;
    if ((a&(a-1))==0)
    {
        printf("the bit is power of 2  \n");
    }
    else 
    {
        printf("the bit is not power of 2\n");
    }
}

Dies gibt aus the bit is power of 2.

#include <stdio.h>

void main()
{
    int a = 7;
    if ((a&(a-1))==0)
    {
        printf("the bit is power of 2  \n");
    }
    else 
    {
        printf("the bit is not power of 2\n");
    }
}

Dies gibt aus the bit is not power of 2.

Angenommen, n ist die gegebene Zahl,
wenn n eine Potenz von 2 ist (n && !(n & (n-1)) gibt 1 zurück, sonst 0