Prüfen ob Potenz von 2

[Torpedo]

Hallo,
wie kann ich möglichst schnell kontrollieren ob eine Zahl eine Potenz von 2 ist?
Egal ob in Delphi, Assembler oder einen anderen Sprache.

Habe mir gedacht man könnte die Anzahl der 1-Bits zählen.
Oder sowas: (bei 1 byte)

edit: ok die methode war falsch ;) aber was gibts sonst so?

[grenzgaenger]

du brauchst nur das letzte bit prüfen. ist dieses nicht gesetzt, ist es eine potenz von 2, sonst nicht.

Delphi-Quellcode:

8 4 2 1
0 0 1 0 --> 2
0 0 0 1 --> 1
0 1 1 0 --> 6
0 1 1 1 --> 7

[Muetze1]

Zitat:

Zitat von grenzgaenger

du brauchst nur das letzte bit prüfen. ist dieses nicht gesetzt, ist es eine potenz von 2, sonst nicht.

Veto: Was ergibt denn 2^0 ?

Er müsste - binär betrachtet - schauen ob in der Ganzzahl nur ein einzelnes Bit gesetzt ist. Also z.B. die gesamte Zahl nach rechts durchshiften und zählen wie oft das Bit 0 gesetzt ist. Wenn er auf ein zweites mal auf ein gesetztes Bit trifft, kann er aufhören.

Er müsste - mathematisch betrachtet - die Potenz berechnen zu der Basis 2, also: pot = ln(zahl) / ln(2). Wenn diese eine glatte Ganzzahl ergibt, ist es eine direkt 2'er Potenz, ansonsten nicht.

/EDIT: sirius, ja war ich im Edit gerade am ausführen...

[sirius]

Zitat:

Zitat von Muetze1

Zitat:

Zitat von grenzgaenger

du brauchst nur das letzte bit prüfen. ist dieses nicht gesetzt, ist es eine potenz von 2, sonst nicht.

Veto: Was ergibt denn 2^0 ?

Deswegen muss man zählen, wie viele Bits auf 1 stehen. Ist es nur ein Bit in der gesamten Zahl, dann ist die Zahl =2^n.

[Neutral General]

Hi,

wir wärs mit Mathe?

Ceil(log 2 (Zahl)) = log 2 (Zahl)

(Also man muss prüfen ob log 2 (Zahl) ne Ganzzahl ist)

PS:

Folgendes funktioniert bei mir soweit ich das getestet habe:

Delphi-Quellcode:

uses Math;

function Is2erPotenz(Zahl: Integer): Boolean;
var tmp: Single;
begin
  tmp := ln(Zahl) / ln(2);
  Result := tmp = Ceil(tmp);
end;

procedure TForm1.Button1Click(Sender: TObject);
begin
  if Is2erPotenz(StrToInt(Edit1.Text)) then
    ShowMessage('Potenz von 2!');
end;

Gruß
Neutral General

[phXql]

Den Logaritmus zu berechnen dürfte afaik langsamer sein als ne schleife zu schreiben, die die 1 zählt.

[Neutral General]

Hi,

Zitat:

Den Logaritmus zu berechnen dürfte afaik langsamer sein als ne schleife zu schreiben, die die 1 zählt.

Ok, dann darf mans sich aussuchen

Delphi-Quellcode:

function Is2erPotenz(Zahl: Integer): Boolean;
var s: Single;
begin
  s := ln(Zahl) / ln(2);
  Result := s = Ceil(s);
end;

// Is nicht optimiert aber funktioniert und dürfte wie gesagt schneller sein als das obere.
// Und man muss Math nicht einbinden.
function Is2erPotenz(Zahl: Integer): Boolean;
var i: Integer;
    tmp: Integer;
begin
  tmp := 0;
  for i:= 0 to 31 do
    if (Zahl and (1 shl i)) shr i = 1 then
      inc(tmp);
  Result := tmp = 1;
end;

[Torpedo]

Vielen Dank für eure Hilfe :-D
Ich werde noch eine Abfrage einbauen, die die Schleife verlässt, sobald 2 Einser gefunden wurden, damit es noch schneller ist.

[Hawkeye219]

Hallo,

versucht es einmal so:

Delphi-Quellcode:

function IsPowerOf2 (aValue: Cardinal) : Boolean;
begin
  Result := (aValue <> 0) and ((aValue and Pred(aValue)) = 0);
end;

Gruß Hawkeye

[Neutral General]

Zitat:

Zitat von Hawkeye219

Hallo,

versucht es einmal so:

Delphi-Quellcode:

function IsPowerOf2 (aValue: Cardinal) : Boolean;
begin
  Result := (aValue = 0) or ((aValue and Pred(aValue)) = 0);
end;

Gruß Hawkeye

Funktioniert zu 99% ;) Aber 2 hoch wie viel ist bitte 0 ? :P