Herausfinden ob eine Zahl Potenz von 2 ist

Hallo,

ich muss ein Programm schreiben, welches ermittelt ob eine eingegebene Zahl eine Potent von 2 ist.
Also zum Beispiel gitb man 1024 ein, und erhält true zurück und bei 4314 eben false.
Nun geht es mir nicht um den Programmcode von euch, sondern wie ich das überhaupt logisch feststellen kann?

(I) Potenz von zwei: 2^x
(II) 2^x = 2 * 2 * 2 * 2 ....

Jetzt dürfte es aber nicht mehr schwer sein.

Ich denke Bits zählen geht wohl am schnellsten.

Jockel

Ich hatte auch schon einen Gedanken mit Bits.
Ich wollte die Zahl nehmen, welche ein long ist und dann solange nach links shiften, bis die erste 1 kommt.
Nur weiß ich nicht wie ich das überprüfen kann.

Mach doch sowas:

long x;
...
if(x == 0)
  return false;

while((x & 0x01) != 1)
{
  x = x >> 0x01;
}
if( x == 1)
  return true;
return false;

Die &-Verknüpfung muss natürlich 0x00000001 sein.

Jockel

JBeni

Wobei einem selbst das Bit-zählen abgenommen wird: Integer.bitCount (und erst noch effizienter als eine Schleife!).

@Jockelx: Du meinst natürlich die &Verküpfung muss &2 heißen, ich suche ja die 2er Potenz.

Jetzt noch kurz, wie kann ich denn dann die nächst kleinere Zweierpotenz rausbekommen, wenn die Zahl keine war?

Nein.
Zweierpotenz bedeutet, dass nur ein Bit irgendwo gesetzt ist und
genau das Untersuche ich oben.

Jockel

Ich meinte damit, ob die Zahl sowas ist wie 2,4,8,16,32,.......,1024,2048
und wenn nicht, was die nächst kleinere dieser Zahlen wäre.
Und ich dachte das wären zweier Potenzen.
Entschuldige wenn ich mich falsch ausgedrückt habe.

Also angenommen ich gebe 1465 ein, dann entspricht dies nicht der Folge und die nächst kleinere Zahl der Folge wäre 1024.

So meinte ich das.

Ja, wir meinen schon das selbe. Betrachte doch mal die binäre Darstellung
deiner Zahlen: 2^0 = 1 = 0x0001, 2^1 = 2 = 0x0010, 2^2 = 4 = 0x0100, usw...

Also x Potenz von 2 genau dann wnn Anzahl der Bits gleich 1.
Zu deiner zweten Frage:

Du hast keine Potenzzahl, also z.B. 13 = 0x1101, dann ist die nächst kleiner
Potenzzahl diejenige, die übrigbleibt, wenn man alle 1'en ausser der
höchsten entfernt (hier 8 = 0x1000).

Jockel

Ok, dann ist deine Überprüfung natürlich richtig. Hatte einen Denkfehler drin.
Aber wie finde ich nun die führende 1 heraus?
Angenommen ich 0111 0011 also 115.
Dann wäre die gesuchte Zahl 64 also 0100 0000. Nur wie bekomme ich diese Stelle raus?

Kannst du doch auch wieder über eine Schleife machen, aber JBeni
hat doch schon einen Link gepostet, in dem alle Methoden stehen,
die man so dafür braucht.

Jockel

ok habs gelöst. Die Funktionen von Beni sind erst ab 1.5, ich hab aber nur 1.4. Und außerdem nur für int geeignet.
Meine Lösung:

while( (tmp & 1) != 1 ) {
            tmp = tmp >> 1;
        }

        if( tmp != 1) {

            tmp = 1;

            while ( (tmp << 1 )  <= itmplenght ) {
                tmp <<= 1;
            }
            return tmp; 
        }
        return itmplenght;

gofur

Warum benutzt du nicht einfach den Modulo-Operator?

long n1 = 22 % 2 // ergibt 0
long n2 = 21 % 2 // ergibt 1

JBeni

@gofur

Weder 21 noch 22 sind Potenzen von 2, was nützt der Modulo also?

CengizS

Wieso so kompliziert?

2^x=y

x = logy / log2

Wenn x ganzzahlig ist dann lässt sich y als echte Potenz von 2 darstellen. Ist x nicht ganzzahlig so ist ihr ganzzahliger Teil die nächstkleinere 2er Potenz der eingegebenen ...

Am schnellsten gehts immer noch mit

if(n & (n - 1) == 0) {
   // ist potenz von 2
 } else {
   // keine potenz von 2
 }

DrZoidberg

KaiP schrieb:

ok habs gelöst. Die Funktionen von Beni sind erst ab 1.5, ich hab aber nur 1.4. Und außerdem nur für int geeignet.
Meine Lösung:
while( (tmp & 1) != 1 ) {
            tmp = tmp >> 1;
        }
       
        if( tmp != 1) {
            
            tmp = 1;
            
            while ( (tmp << 1 )  <= itmplenght ) {
                tmp <<= 1;
            }
            return tmp; 
        }
        return itmplenght;

Das kann man aber noch kürzen.

tmp = 1;

while ( (tmp << 1 )  <= itmplenght ) {
    tmp <<= 1;
}
return tmp;