Autor |
Beitrag |
BenBE
Beiträge: 8721
Erhaltene Danke: 191
Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
|
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
Beiträge: 2931
XP Prof, Vista Business
D6, D2k5-D2k7 je Prof
|
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
Beiträge: 1033
Erhaltene Danke: 1
WinXP Pro SP2
Delphi 6 Prof.
|
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
Beiträge: 6388
Erhaltene Danke: 146
Windows 7 + Windows 10
Sydney Prof + CE
|
Verfasst: Mo 13.12.04 13:40
Mein Versuch:
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.
Zuletzt bearbeitet von jasocul am Mo 13.12.04 13:49, insgesamt 1-mal bearbeitet
|
|
Udontknow
Beiträge: 2596
Win7
D2006 WIN32, .NET (C#)
|
Verfasst: Mo 13.12.04 13:42
Wie liegt denn die Zahl überhaupt vor? Was für Zahlen sind zu erwarten?
Cu,
Udontknow
|
|
jasocul
Beiträge: 6388
Erhaltene Danke: 146
Windows 7 + Windows 10
Sydney Prof + CE
|
Verfasst: Mo 13.12.04 13:55
Das dürfte schneller sein, als mein erste Variante.
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; result := (i = 1); end; |
Zuletzt bearbeitet von jasocul am Mo 13.12.04 15:11, insgesamt 3-mal bearbeitet
|
|
BenBE
Beiträge: 8721
Erhaltene Danke: 191
Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
|
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:
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
Beiträge: 6388
Erhaltene Danke: 146
Windows 7 + Windows 10
Sydney Prof + CE
|
Verfasst: Mo 13.12.04 15:07
Wert testet denn jetzt, was schneller ist?
Übersichtlicher finde ich meins.
|
|
IngoD7
Beiträge: 629
D7
|
Verfasst: Mo 13.12.04 15:29
Delphi-Quelltext 1:
| if Frac(Log2(Zahl))=0 then <Zahl ist Zweierpotenz>; |
|
|
raziel
Beiträge: 2453
Arch Linux
JS (WebStorm), C#, C++/CLI, C++ (VS2013)
|
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
Beiträge: 2931
XP Prof, Vista Business
D6, D2k5-D2k7 je Prof
|
Verfasst: Mo 13.12.04 15:46
jasocul hat folgendes geschrieben: | Wert testet denn jetzt, was schneller ist?
Übersichtlicher finde ich meins. |
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
Beiträge: 6388
Erhaltene Danke: 146
Windows 7 + Windows 10
Sydney Prof + CE
|
Verfasst: Mo 13.12.04 15:50
@BenBE:
Was hab ich jetzt gewonnen?
Danke für die Messungen, raziel.
|
|
IngoD7
Beiträge: 629
D7
|
Verfasst: Mo 13.12.04 16:11
Zuletzt bearbeitet von IngoD7 am Mo 13.12.04 16:16, insgesamt 1-mal bearbeitet
|
|
jasocul
Beiträge: 6388
Erhaltene Danke: 146
Windows 7 + Windows 10
Sydney Prof + CE
|
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.
|
|
IngoD7
Beiträge: 629
D7
|
Verfasst: Mo 13.12.04 16:18
jasocul hat folgendes geschrieben: | Auf jeden Fall sind unsere Sourcen viel schöner als der von BenBE. |
Vollkommen einverstanden!
|
|
I.MacLeod
Beiträge: 109
|
Verfasst: Mo 13.12.04 16:29
Dann werf ich doch auch mal meins in die Runde:
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
Beiträge: 2453
Arch Linux
JS (WebStorm), C#, C++/CLI, C++ (VS2013)
|
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
|
Verfasst: Mo 13.12.04 17:50
Gibts einen Extrapreis für Kürze? ; -)
Delphi-Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9: 10:
| function IsPowerOfTwo(A: DWORD): boolean; asm test eax, eax jz @@end @@loop: shl eax, 1 jno @@loop shl eax, 1 setz al @@end: end; |
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
Beiträge: 8721
Erhaltene Danke: 191
Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
|
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:
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.
|
Verfasst: So 09.01.05 21:02
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.
|
|