Zweierpotenz erkennen!?

[Julezzz]

Hallo!
Nur eine kurze Frage. Das Programm soll erkennen, ob eine Zweierpotenz eingegeben wurde.

Ich komme einfach nicht auf den logischen Lösungsweg! Mein Prof meinte, man braucht einen konstanten Wert, mit dem man immer weiter rechnet, aber das hilft mir auch nicht besonders -.-

Please help me!
Danke

 

[SCIPIO-AEMILIANUS]

Also wenn ich das Problem richtig verstanden hab würde ich es wie folgt lösen:

#include "iostream"
#include "math.h"
using namespace std;

bool check(double z)
{
   double foo=log(z)/log(2);
   if(round(foo)==foo) return true;
   else false;
}
int main(){
    double num=0;
    cout<<"Gib eine Zahl ein: ";
    cin>>num;
    if(check(num)==true){
       cout<<num<<" ist eine Zweierpotenz!";
    }
    else{
       cout<<num<<" ist keine Zweierpotenz!";
    }
}

 

[Matthias Reitinger]

Hallo,

bei ganzzahligen Werten klappt auch folgender Trick:

int n;
if (n && !(n & (n-1))) {
  // Zweierpotenz
}

Grüße,
Matthias

 

[Julezzz]

Danke für die Hilfe!

Aber da ich noch am Anfang bin, wird der Prof mir das...:

bool check(double z)
{
double foo=log(z)/log(2);
if(round(foo)==foo) return true;
else false;
}

... nicht glauben ^^ Es muss einen einfacheren Weg geben... Wie gibt man überhaupt 2^n ein? Da wir den Befehl noch nicht hatten, muss es anders gehen...

Danke

 

[SCIPIO-AEMILIANUS]

2^n kann man mit pow eingeben.
Sollte dann so aussehen: pow(2,n);

Und einen leichteren Weg, als die Beiden oben stehenden Wege, gibt es meiner Meinung nach nicht. Ansonsten in einer Schleife pow(2,n) n inkrementieren lassen, bis das Ergebnis größer oder gleich der Eingabe ist. Jedoch wäre das Rechenzeit technisch äußerst ineffizient in meinen Augen.

 

[Vereth]

Wie wäre es damit:

boolean ist2erPotenz(double d)
{
  long n = (long)d;

  if ( n != d ) return false;

  while ( n%2 == 0 ) n /= 2;

  return ( n == 1 ) ? true : false;
}

Die Laufzeit ist logarithmisch und die meisten nicht-Potenzen werden sehr früh erkannt.

 

[Enumerator]

Hi!

Solang es sich ausschließlich um ganzzahlige, natürliche Werte größer oder gleich Null handelt musst Du nur kontrollieren, ob im Bitsatz des gegebenen Wertes genau ein Bit gesetzt ist. Den einfachsten Weg dafür hat Matthias oben schon gezeigt. Was Dein Prof aber mit dem konstanten Wert meinen könnte, ist mir schleierhaft.

Gruß
Enum

 

[Vereth]

Der konstante Wert ist die 2 in der Anweisung 'n /= 2;' und das immer weiter rechnen übernimmt die while-Schleife.

Wenn meine Funktion auch negative 2er-Potenzen erkennen soll, muss die letzte Zeile lauten:
return ( n == 1 || n==-1 ) ? true : false;