Delphi-PRAXiS

Delphi-PRAXiS (https://www.delphipraxis.net/forum.php)
-   Programmieren allgemein (https://www.delphipraxis.net/40-programmieren-allgemein/)
-   -   Prüfen ob Potenz von 2 (https://www.delphipraxis.net/109487-pruefen-ob-potenz-von-2-a.html)

Torpedo 2. Mär 2008 15:28


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?

grenzgaenger 2. Mär 2008 15:31

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

Muetze1 2. Mär 2008 15:37

Re: Prüfen ob Potenz von 2
 
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 2. Mär 2008 15:40

Re: Prüfen ob Potenz von 2
 
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 2. Mär 2008 15:49

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:
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 2. Mär 2008 15:59

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.

Neutral General 2. Mär 2008 16:06

Re: Prüfen ob Potenz von 2
 
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 2. Mär 2008 16:10

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.

Hawkeye219 2. Mär 2008 16:11

Re: Prüfen ob Potenz von 2
 
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 2. Mär 2008 16:14

Re: Prüfen ob Potenz von 2
 
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

Hawkeye219 2. Mär 2008 16:20

Re: Prüfen ob Potenz von 2
 
Danke für das Korrekturlesen, Michael!

Gruß Hawkeye

DeddyH 2. Mär 2008 16:26

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:

phXql 2. Mär 2008 16:31

Re: Prüfen ob Potenz von 2
 
Hossa, was macht Pred? Hab kein Delphi mehr installiert ;)

grenzgaenger 2. Mär 2008 16:32

Re: Prüfen ob Potenz von 2
 
gut. hatte mich verhaun...

Delphi-Quellcode:
x := (V mod 2) = 0;

Neutral General 2. Mär 2008 16:33

Re: Prüfen ob Potenz von 2
 
Zitat:

Zitat von grenzgaenger
gut. hatte mich verhaun...

Delphi-Quellcode:
x := (V mod 2) = 0;

Dir ist klar das "Potenz von 2" <> "Vielfaches von 2" ?

6 z.B. ist ein Vielfaches von 2 aber keine Potzenz von 2 ;)

PS: Beim Vielfachen funktioniert auch deine erste gepostete Lösung ;)

dominikkv 2. Mär 2008 16:35

Re: Prüfen ob Potenz von 2
 
Zitat:

Zitat von phXql
Hossa, was macht Pred? Hab kein Delphi mehr installiert ;)

Pred ermittelt den Vorgänger.
Also Pred(5) = 4
Gegenteil von Succ

igel457 2. Mär 2008 16:46

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