Laden...

Rausfinden ob eine Zahl 2^x ist

Letzter Beitrag vor 15 Jahren 15 Posts 3.695 Views
Rausfinden ob eine Zahl 2^x ist

Guten Tag,

ich möchte möglichst effizient rausfinden ob eine Zahl 2^x ist.

Mein Ansatz:


public static boolean Test(int value)
{
    double temp1 = System.Math.Log(n, 2);
    double temp2 = System.Math.Floor(temp1);
    return (temp1 == temp2);
}

Geht das nicht einfacher? Mit schieben oder so? Was meint ihr?

Gruss Wollmich

Überleg mal wie eine solche Zahl in Binär-Darstellung aussieht. Mit dem Schieben bist du schon auf dem richtigen Dampfer....

Hi,
zuspät, poste aber trotzdem
mein erster gedanke war die zahl in eine binärzahl umzuwandeln und die 1 en zählen!
wenns nur eine ist (ausgenommen wenss die ganz rechts ist), ists ne hochtzahl von 2;

Torley

Danke für die schnelle Antwort.

Ist mir klar das bei einer solchen Zahl in der binär Darstellung nur eine Ziffer eine '1' ist und der Rest alles '0' sein muss.

Aber wie kann ich das clever vergleichen. 32 mal schieben (in einem Loop) und vergleichen ob nur ein 1 vorkommt? Ist mir fast peinlich aber ich denke das geht doch noch einfacher.

Anmerkung am Rande: Die Zahl muss nicht durch 2 teilbar sein sondern die Potenz davon.

Gruss Wollmich

Ist mir fast peinlich aber ich denke das geht doch noch einfacher.

Denk nicht. Ist zumindest eine sehr schnelle Variante. Eine Schleife mit ein paar Shifts und einem Vergleich geht ratzfatz.

Anmerkung am Rande: Die Zahl muss nicht durch 2 teilbar sein sondern die Potenz davon.

Durch zwei teilbar heisst, dass das niederwertigste Bit 0 ist....

Hi,


public static Boolean isPowerOf2(int v)
{
   return (v & (v - 1))==0 && (v != 0);
}

beste Grüße
zommi

PS: Idee kommt von Bit Twiddling Hacks

  
public static Boolean isPowerOf2(int v)  
{  
   return (v & (v - 1))==0 && (v != 0);  
}  
  

Wow, der ist gut.

Vielen Dank für die schnelle Lösung und schnellen Antworten. 😁

Gruss Wollmich

So vielleicht?^^


String binaryString = Convert.ToString(value, 2);
bool result = binaryString.IndexOf('1') == binaryString.LastIndexOf('1');

Lg XXX

Lustige Idee.
Aber was mich daran stört, ist das man einen Int erst in einen String konvertieren muss obwohl das auf Bit-Ebene - wie man sehen kann - viel einfacher und schneller funktioniert.

Damit wollte ich eigentlich nur sagen, das xxxprod vielleicht mal seinen Code durchsuchen sollte um solche Stellen zu verbessern (falls er es denn in seinen Programmen so geschrieben hat).

Religionskriege sind Konflikte zwischen erwachsenen Menschen, bei denen es darum geht, wer den cooleren, imaginaeren Freund hat

Mir gefällt die Lösung von zommi am besten.

1 Subtraktion
2 Logische Verknüpfungen
2 Vergleiche

Das ist viel schneller als eine Umwandlung in einen String.

Für mich ist das Problem gelöst, DANKE.

Gruss Wollmich

nicht so schnell wie die bit-lösung, dafür mathematisch:


int x = 16;

double tmp = Math.Log(x, 2);
bool isPowerOf2 = (int)tmp == tmp;

loop:
btst #6,$bfe001
bne.s loop
rts

Danke, aber das war doch meine Ursprungslösung ?(

ja

aber der gute 0815coder hat wieder mal beim lesen nur den ersten teil gelesen und dann rest überflogen... bzw is drübergestolpert.

is natürlich so gut wie ident.

loop:
btst #6,$bfe001
bne.s loop
rts

huhu

Lustige Idee.
Aber was mich daran stört, ist das man einen Int erst in einen String konvertieren muss [..] das xxxprod vielleicht mal seinen Code durchsuchen sollte um solche Stellen zu verbessern

geh eher davon aus, dass das nur eine nicht ernstgemeinte zusätzliche Lösung ist, um den Alltag etwas amüsanter zu gestalten und dem Leser ein Lächeln zu entlocken^^

🙂

Xynratron

Herr, schmeiss Hirn vom Himmel - Autsch!

Die Erfahrung zeigt immer wieder, dass viele Probleme sich in Luft auslösen, wenn man sich den nötigen Abstand bzw. Schlaf gönnt.