Laden...

Rausfinden ob eine Zahl 2^x ist

Erstellt von wollmich vor 15 Jahren Letzter Beitrag vor 15 Jahren 3.654 Views
wollmich Themenstarter:in
178 Beiträge seit 2008
vor 15 Jahren
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

S
8.746 Beiträge seit 2005
vor 15 Jahren

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

T
109 Beiträge seit 2008
vor 15 Jahren

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

wollmich Themenstarter:in
178 Beiträge seit 2008
vor 15 Jahren

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

S
8.746 Beiträge seit 2005
vor 15 Jahren

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....

1.361 Beiträge seit 2007
vor 15 Jahren

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

S
8.746 Beiträge seit 2005
vor 15 Jahren
  
public static Boolean isPowerOf2(int v)  
{  
   return (v & (v - 1))==0 && (v != 0);  
}  
  

Wow, der ist gut.

wollmich Themenstarter:in
178 Beiträge seit 2008
vor 15 Jahren

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

Gruss Wollmich

1.378 Beiträge seit 2006
vor 15 Jahren

So vielleicht?^^


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

Lg XXX

P
67 Beiträge seit 2008
vor 15 Jahren

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

wollmich Themenstarter:in
178 Beiträge seit 2008
vor 15 Jahren

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

0
767 Beiträge seit 2005
vor 15 Jahren

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

wollmich Themenstarter:in
178 Beiträge seit 2008
vor 15 Jahren

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

0
767 Beiträge seit 2005
vor 15 Jahren

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

X
1.177 Beiträge seit 2006
vor 15 Jahren

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.