Ermitteln, ob eine Zahl eine Zweierpotenz ist.

BenBE · Verfasst: Mo 13.12.04 12:00

Dies ist ein Wettbewerb für unsere Optimierungsspezies:

Wie kann man am effektivsten feststellen, ob eine Zahl eine Zweierpotenz ist.

ASM erwünscht, aber nicht notwendig. Ich poste meine bisherige Version sobald die ersten Vorschläge kamen.

_________________

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

Motzi · Verfasst: Mo 13.12.04 12:16

Einfach zählen wieviele einsen die Binär-Darstellung hat - eine Zweierpotenz ist immer nur durch eine einzige 1 darstellbar... das ganze in einen Algo umzusetzen überlass ich aber dir..

_________________
gringo pussy cats - eef i see you i will pull your tail out by eets roots!

MrSaint · Verfasst: Mo 13.12.04 12:19

Also mir würden auf Anhieb mal zwei Möglichkeiteneinfallen:
Entweder wir teilen die Zahl so lange durch zwei bis mod 2 <> 0 ist oder wir bei zahl = 2 angekommen sind.
Oder genau die Rückrichtung. Wir lassen die Zahl so stehen und fangen an diese mod 2 zu nhemen. Dann mod 2², dann mod 2³ und wenns irgendwann mal <> 0 is, isses keine Zweierpotenz.

MrSaint

EDIT: Oha, da gibts aber schon bessere Lösungen

Also nehm ich meinen Vorschlag mal zurück

_________________
"people knew how to write small, efficient programs [...], a skill that has subsequently been lost"
Andrew S. Tanenbaum - Modern Operating Systems

jasocul · Verfasst: Mo 13.12.04 13:40

Mein Versuch:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:

Function IstZweierPotenz(i : Integer) : Boolean;
var
  a : Integer;
begin
  a := 1;
  while a < i do  a:= a shl 1;
  Result := (a = i);
end;

Wenn man das noch in asm umbaut, dann dürfte das ganz flott sein.

Udontknow · Beiträge: 2596 Win7 D2006 WIN32, .NET (C#)

Wie liegt denn die Zahl überhaupt vor? Was für Zahlen sind zu erwarten?

Cu,
Udontknow

jasocul · Verfasst: Mo 13.12.04 13:55

Das dürfte schneller sein, als mein erste Variante.

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:

Function IstZweierPotenz(i : Integer) : Boolean;
begin
  while (not Odd(i)) and (i > 1) do i := i shr 1; // while (i mod 2 = 0) and (i > 1) do i := i shr 1; Was da schneller ist, weiß ich nicht
  result := (i = 1);
end;

BenBE · Verfasst: Mo 13.12.04 14:35

Zahlen: Z.Zt. Umgesetzt für DWORD, theoretisch aber beliebige Größe, mit 2^n Bits.

Hab's mal rekursiv gelöst, geht aber noch wesentlich zu optimieren. Erstmal hier nur der versprochene Vorschlag von mir. Bin mal auf eure Verbesserungen gespannt:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:

function IsPowerOfTwo(Number:Integer): Boolean;

    function BitCount(const Number: DWORD; const Count:Byte): Byte;
    var
        Temp1:DWORD;
        Temp2:DWORD;
        Mask: DWORD;
        CntHalf:Byte;
    Begin
        If Count = 1 Then
        Begin
            Result := Number and 1;
            Exit;
        end;

        CntHalf := Count shr 1;
        Mask := 1 shl CntHalf - 1;

        Temp1 := Number and Mask;
        Temp2 := (Number shr CntHalf) and Mask;

        If Temp1 <> 0 Then
            Result := BitCount(Temp1, CntHalf)
        else
            Result := 0;

        If Result > 1 Then Exit;

        If Temp2 <> 0 Then
            Result := Result + BitCount(Temp2, CntHalf);
    end;

begin
    Result := BitCount(Number, 32) = 1;
end;

_________________

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

jasocul · Verfasst: Mo 13.12.04 15:07

Wert testet denn jetzt, was schneller ist?
Übersichtlicher finde ich meins. :wink:

IngoD7 · Beiträge: 629 D7

markieren

Delphi-Quelltext

1:	if Frac(Log2(Zahl))=0 then <Zahl ist Zweierpotenz>;

raziel · Verfasst: Mo 13.12.04 15:36

jasocul < IngoD7 < BenBE

jasocul: mit Abstand am schnellsten: ~200 Zyklen
IngoD7: ~ 500 Zyklen
BenBE: ~600 Zyklen

Getestet mit Hilfe dieses Codes von Luckie/negaH

_________________
JSXGraph

Motzi · Verfasst: Mo 13.12.04 15:46

jasocul hat folgendes geschrieben:

Wert testet denn jetzt, was schneller ist?
Übersichtlicher finde ich meins. :wink:

Also schneller als deine Implementierung gehts wohl nicht mehr.. das ist schon das absolute Minimum (wie raziels Messungen zeigen

)..!

_________________
gringo pussy cats - eef i see you i will pull your tail out by eets roots!

jasocul · Verfasst: Mo 13.12.04 15:50

@BenBE:
Was hab ich jetzt gewonnen? :dance:

Danke für die Messungen, raziel.

IngoD7 · Beiträge: 629 D7

jasocul hat folgendes geschrieben:

@BenBE:
Was hab ich jetzt gewonnen? :dance:

Nix da!

Wo steht geschrieben, dass Effizienz und Effektivität (hiervon sprach BenBE) immer nur Geschwindigkeit bedeutet??

In der Kürze liegt die Würze. Ich glaube, ich habe gewonnen ... :lol:

jasocul · Verfasst: Mo 13.12.04 16:16

Auf jeden Fall sind unsere Sourcen viel schöner als der von BenBE. Bei seinem muss ich ja nachdenken. :wink:

IngoD7 · Beiträge: 629 D7

jasocul hat folgendes geschrieben:

Auf jeden Fall sind unsere Sourcen viel schöner als der von BenBE.

Vollkommen einverstanden! :beer:

I.MacLeod · Beiträge: 109

Dann werf ich doch auch mal meins in die Runde:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:

function IsPowerOfTwo(A: DWORD): boolean;
asm
             test eax, eax
             jz   @@end
  @@loop:    shl  eax, 1
             jo   @@testit
             jmp  @@loop
  @@testit:  shl  eax, 1
             jz   @@true
             xor  al, al
             jmp  @@end
  @@true:    mov  al, 1
  @@end:
end;

Dürfte ganz gut klappen, aber die Geschwindigkeit hab ich nicht überprüft. ;-)

raziel · Verfasst: Mo 13.12.04 16:35

Jo, klappt ganz gut, aber jasocul is immer noch auf Platz 1, dicht gefolgt von I.Macleod

_________________
JSXGraph

I.MacLeod · Beiträge: 109

Gibts einen Extrapreis für Kürze? ;-)

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:

function IsPowerOfTwo(A: DWORD): boolean;
asm
             test eax, eax  // 2
             jz   @@end     // 2
  @@loop:    shl  eax, 1    // 2
             jno  @@loop    // 2
             shl  eax, 1    // 2
             setz al        // 3
  @@end:
end;                        // 1

14 Bytes

//Edit: Ich habe übrigens seltsame Unregelmäßigkeiten festgestellt, wenn ich die selbe Fkt zweimal hintereinander mit dem oben genannten Code teste. (Fast immer hat eine der beiden ein paar Zyklen mehr als die andere)

BenBE · Verfasst: Mo 13.12.04 20:24

Gut, bei den DWORDs geb ich mich geschlagen

Bleiben noch die von mir erwähnten großen Zahlen von 2^n Bits (Das heißt auch 1KB große Zahlen ;-)

)

Vorschlag:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:

Type
    TBigNumber = Array of Byte;

Function IsPowerOfTwo(const Number: TBigNumber): Boolean;
asm
    PUSH    EDI
    LEA     EDI, DWORD PTR [Number]
    MOV     ECX, DWORD PTR [EDI-$04]

    XOR     EAX, EAX
    REPZ    SCASB
    JZ      @@FinishFalse

    MOVZX   EAX, BYTE PTR [EDI-$01]

@@Loop:
    SHL     EAX, 1
    JNO     @@Loop

    SHL     EAX, 1
    JNZ     @@FinishFalse

    REPZ    SCASB
    SETZ    AL
    JMP     @@Finish

@@FinishFalse:
    XOR     EAX, EAX

@@Finish:
    POP     EDI
end;

Moderiert von Motzi: Delphi-Tags repariert.

_________________

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

Spaceguide · Beiträge: 552 (D3/D7/D8) Prof.

markieren

Delphi-Quelltext

1:
2:
3:
4:

function IsPowerOfTwo(d : dword) : boolean;
begin
  Result := (d>0) and (d and (d - 1) = 0);
end;

Moderiert von Motzi: Delphi-Tags hinzugefügt.

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme