Prüfen ob Potenz von 2
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? |
Re: Prüfen ob Potenz von 2
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 |
Re: Prüfen ob Potenz von 2
Zitat:
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... |
Re: Prüfen ob Potenz von 2
Zitat:
|
Re: Prüfen ob Potenz von 2
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:
Gruß
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; Neutral General |
Re: Prüfen ob Potenz von 2
Den Logaritmus zu berechnen dürfte afaik langsamer sein als ne schleife zu schreiben, die die 1 zählt.
|
Re: Prüfen ob Potenz von 2
Hi,
Zitat:
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; |
Re: Prüfen ob Potenz von 2
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. |
Re: Prüfen ob Potenz von 2
Hallo,
versucht es einmal so:
Delphi-Quellcode:
Gruß Hawkeye
function IsPowerOf2 (aValue: Cardinal) : Boolean;
begin Result := (aValue <> 0) and ((aValue and Pred(aValue)) = 0); end; |
Re: Prüfen ob Potenz von 2
Zitat:
|
Re: Prüfen ob Potenz von 2
Danke für das Korrekturlesen, Michael!
Gruß Hawkeye |
Re: Prüfen ob Potenz von 2
Ist aber von dem kleinen Lapsus abgesehen ein super Lösung, das wäre mir nicht eingefallen :thumb:
|
Re: Prüfen ob Potenz von 2
Hossa, was macht Pred? Hab kein Delphi mehr installiert ;)
|
Re: Prüfen ob Potenz von 2
gut. hatte mich verhaun...
Delphi-Quellcode:
x := (V mod 2) = 0;
|
Re: Prüfen ob Potenz von 2
Zitat:
6 z.B. ist ein Vielfaches von 2 aber keine Potzenz von 2 ;) PS: Beim Vielfachen funktioniert auch deine erste gepostete Lösung ;) |
Re: Prüfen ob Potenz von 2
Zitat:
Also Pred(5) = 4 Gegenteil von Succ |
Re: Prüfen ob Potenz von 2
Einfach in die Codelib schauen:
http://www.delphipraxis.net/internal...ect.php?t=7838 |
Alle Zeitangaben in WEZ +1. Es ist jetzt 00:28 Uhr. |
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz