Delphi-PRAXiS

Delphi-PRAXiS (https://www.delphipraxis.net/forum.php)
-   Neuen Beitrag zur Code-Library hinzufügen (https://www.delphipraxis.net/33-neuen-beitrag-zur-code-library-hinzufuegen/)
-   -   Delphi IsPowerOfTwo (https://www.delphipraxis.net/133667-ispoweroftwo.html)

himitsu 6. Mai 2009 19:52
IsPowerOfTwo
 
Hab hier noch was Kleines als Nachtrag :angel:

Code-Library -> Algorithmen -> IsPowerOfTwo

Delphi-Quellcode:
Function IsPowerOfTwo(i: LongWord): Boolean;
  ASM
    BSR    EDX, EAX
    BSF    EAX, EAX
    JZ     @@None
    CMP    EAX, EDX
    SETZ   AL
    @@None:
  End;
es ist die Kurzfassung von:
Delphi-Quellcode:
Function IsPowerOfTwo(i: LongWord): Boolean;
  ASM
    TEST   EAX, EAX
    JZ     @@None
    BSR    EDX, EAX
    BSF    ECX, EAX
    CMP    ECX, EDX
    JNE    @@None
    MOV    AL, &True
    @@None:
    MOV    AL, &False
  End;

// bzw.

Function IsPowerOfTwo(i: LongWord): Boolean;
  ASM
    BSR    EDX, EAX
    JZ     @@None
    BSF    ECX, EAX
    CMP    ECX, EDX
    JNE    @@None
    MOV    AL, &True
    @@None:
    MOV    AL, &False
  End;

Dax 6. Mai 2009 19:55
Re: IsPowerOfTwo
 
Lohnt sich das denn? ;) Wenn man schon so weit geht, diese Dinge in Assembler zu schreiben - und damit Gegenüber dem Delphicompiler was gutmachen kann - wird der Call-Overhead doch so groß, dass es sich kaum noch lohnt :gruebel:

Desmulator 6. Mai 2009 19:59
Re: IsPowerOfTwo
 
Zitat:
Zitat von Dax
Lohnt sich das denn? :wink: Wenn man schon so weit geht, diese Dinge in Assembler zu schreiben - und damit Gegenüber dem Delphicompiler was gutmachen kann - wird der Call-Overhead doch so groß, dass es sich kaum noch lohnt Grübelnd...
Wenn man es als inline deklarieren würde, wie wärs dann? :gruebel:

himitsu 6. Mai 2009 20:00
Re: IsPowerOfTwo
 
Kommt drauf an ... solange der Compiler keine Inline-Funktionen unterstützt (abgesehn davon, daß Hagens Funktion eh nicht als Inline definiert ist), kann man den Call-Overhead eh nicht umgehn.

[edit]
es ist auch mehr als Alternative zum ersten Code (mit dem Schleifchen) gedacht

das was die Schleife macht, übernimmt hier BSR bzw BSF



das Ganze ist 'ne angepaßte Auskopplung von
Delphi-Quellcode:
// RoL      => rotate left
// RoR      => rotate left
// OpenBit  => number of highest bit (MSB)
// CloseBit => number of lowest bit (LSB)
// CountBits => number of bits
// OneBit   => only one bit is set (OpenBit=CloseBit, IsPowerOfTwo)

{$DEFINE UseInline}

Function RoL(      i: Byte;     r: Byte): Byte;     Overload;
Function RoL(      i: Word;     r: Byte): Word;     Overload;
Function RoL(      i: LongWord; r: Byte): LongWord; Overload;
Function RoL(Const i: LargeWord; r: Byte): LargeWord; Overload;
Function RoL(      i: ShortInt; r: Byte): ShortInt; Overload;
Function RoL(      i: SmallInt; r: Byte): SmallInt; Overload;
Function RoL(      i: LongInt;  r: Byte): LongInt;  Overload;
Function RoL(Const i: LargeInt; r: Byte): LargeInt; Overload;

Function RoR(      i: Byte;     r: Byte): Byte;     Overload;
Function RoR(      i: Word;     r: Byte): Word;     Overload;
Function RoR(      i: LongWord; r: Byte): LongWord; Overload;
Function RoR(Const i: LargeWord; r: Byte): LargeWord; Overload;
Function RoR(      i: ShortInt; r: Byte): ShortInt; Overload;
Function RoR(      i: SmallInt; r: Byte): SmallInt; Overload;
Function RoR(      i: LongInt;  r: Byte): LongInt;  Overload;
Function RoR(Const i: LargeInt; r: Byte): LargeInt; Overload;

Function OpenBit(      i: Byte):     LongInt; Overload;
Function OpenBit(      i: Word):     LongInt; Overload;
Function OpenBit(      i: LongWord): LongInt; Overload;
Function OpenBit(Const i: LargeWord): LongInt; Overload;
Function OpenBit(      i: ShortInt): LongInt; Overload;
Function OpenBit(      i: SmallInt): LongInt; Overload;
Function OpenBit(      i: LongInt):  LongInt; Overload;
Function OpenBit(Const i: LargeInt): LongInt; Overload;

Function CloseBit(      i: Byte):     LongInt; Overload;
Function CloseBit(      i: Word):     LongInt; Overload;
Function CloseBit(      i: LongWord): LongInt; Overload;
Function CloseBit(Const i: LargeWord): LongInt; Overload;
Function CloseBit(      i: ShortInt): LongInt; Overload;
Function CloseBit(      i: SmallInt): LongInt; Overload;
Function CloseBit(      i: LongInt):  LongInt; Overload;
Function CloseBit(Const i: LargeInt): LongInt; Overload;

Function CountBits(      i: Byte):     LongInt; Overload;
Function CountBits(      i: Word):     LongInt; Overload;
Function CountBits(      i: LongWord): LongInt; Overload;
Function CountBits(Const i: LargeWord): LongInt; Overload;
Function CountBits(      i: ShortInt): LongInt; Overload; {$IFDEF UseInline}Inline;{$ENDIF}
Function CountBits(      i: SmallInt): LongInt; Overload; {$IFDEF UseInline}Inline;{$ENDIF}
Function CountBits(      i: LongInt):  LongInt; Overload; {$IFDEF UseInline}Inline;{$ENDIF}
Function CountBits(Const i: LargeInt): LongInt; Overload; {$IFDEF UseInline}Inline;{$ENDIF}

Function OneBit(      i: Byte):     LongInt; Overload;
Function OneBit(      i: Word):     LongInt; Overload;
Function OneBit(      i: LongWord): LongInt; Overload;
Function OneBit(Const i: LargeWord): LongInt; Overload;
Function OneBit(      i: ShortInt): LongInt; Overload;
Function OneBit(      i: SmallInt): LongInt; Overload;
Function OneBit(      i: LongInt):  LongInt; Overload;
Function OneBit(Const i: LargeInt): LongInt; Overload;



Function RoL(i: Byte; r: Byte): Byte;
  ASM
    MOV    CL, &r
    ROL    &i, CL
  End;

Function RoL(i: Word; r: Byte): Word;
  ASM
    MOV    CL, &r
    ROL    &i, CL
  End;

Function RoL(i: LongWord; r: Byte): LongWord;
  ASM
    MOV    CL, &r
    ROL    &i, CL
  End;

Function RoL(Const i: LargeWord; r: Byte): LargeWord;
  ASM
    MOVZX  ECX, &r
    MOV    EAX, DWORD PTR [&i]
    MOV    EDX, DWORD PTR [&i + 4]
    CMP    EAX, 0
    @@Loop:
    RCL    EDX, 1
    RCL    EAX, 1
    LOOP   @@Loop
  End;

Function RoL(i: ShortInt; r: Byte): ShortInt;
  ASM
    MOV    CL, &r
    ROL    &i, CL
  End;

Function RoL(i: SmallInt; r: Byte): SmallInt;
  ASM
    MOV    CL, &r
    ROL    &i, CL
  End;

Function RoL(i: LongInt; r: Byte): LongInt;
  ASM
    MOV    CL, &r
    ROL    &i, CL
  End;

Function RoL(Const i: LargeInt; r: Byte): LargeInt;
  ASM
    MOV    CL, &r
    MOV    EAX, DWORD PTR [&i]
    MOV    EDX, DWORD PTR [&i + 4]
    CMP    EAX, 0
    @@Loop:
    RCL    EDX, 1
    RCL    EAX, 1
    DEC    CL
    JNZ    @@Loop
  End;

Function RoR(i: Byte; r: Byte): Byte;
  ASM
    MOV    CL, &r
    ROR    &i, CL
  End;

Function RoR(i: Word; r: Byte): Word;
  ASM
    MOV    CL, &r
    ROR    &i, CL
  End;

Function RoR(i: LongWord; r: Byte): LongWord;
  ASM
    MOV    CL, &r
    ROR    &i, CL
  End;

Function RoR(Const i: LargeWord; r: Byte): LargeWord;
  ASM
    MOV    CL, &r
    MOV    EAX, DWORD PTR [&i]
    MOV    EDX, DWORD PTR [&i + 4]
    MOV    ESI, EDX
    RCR    ESI, 1
    @@Loop:
    RCR    EAX, 1
    RCR    EDX, 1
    DEC    CL
    JNZ    @@Loop
  End;

Function RoR(i: ShortInt; r: Byte): ShortInt;
  ASM
    MOV    CL, &r
    ROR    &i, CL
  End;

Function RoR(i: SmallInt; r: Byte): SmallInt;
  ASM
    MOV    CL, &r
    ROR    &i, CL
  End;

Function RoR(i: LongInt; r: Byte): LongInt;
  ASM
    MOV    CL, &r
    ROR    &i, CL
  End;

Function RoR(Const i: LargeInt; r: Byte): LargeInt;
  ASM
    MOV    CL, &r
    MOV    EAX, DWORD PTR [&i]
    MOV    EDX, DWORD PTR [&i + 4]
    MOV    ESI, EDX
    RCR    ESI, 1
    @@Loop:
    RCR    EAX, 1
    RCR    EDX, 1
    DEC    CL
    JNZ    @@Loop
  End;

Function OpenBit(i: Byte): LongInt;
  ASM
    AND    EAX, $000000ff
    MOV    EDX, -1
    BSR    EDX, EAX{&i}
    MOV    EAX, EDX
  End;

Function OpenBit(i: Word): LongInt;
  ASM
    AND    EAX, $0000ffff
    MOV    EDX, -1
    BSR    EDX, EAX{&i}
    MOV    EAX, EDX
  End;

Function OpenBit(i: LongWord): LongInt;
  ASM
    MOV    EDX, -1
    BSR    EDX, &i
    MOV    EAX, EDX
  End;

Function OpenBit(Const i: LargeWord): LongInt;
  ASM
    MOV    EAX, -1
    BSR    EAX, DWORD PTR [&i]
    JNZ    @@Exit
    BSR    EAX, DWORD PTR [&i + 4]
    JZ     @@Exit
    ADD    EAX, 32
    @@Exit:
  End;

Function OpenBit(i: ShortInt): LongInt;
  ASM
    AND    EAX, $000000ff
    MOV    EDX, -1
    BSR    EDX, EAX{&i}
    MOV    EAX, EDX
  End;

Function OpenBit(i: SmallInt): LongInt;
  ASM
    AND    EAX, $0000ffff
    MOV    EDX, -1
    BSR    EDX, EAX{&i}
    MOV    EAX, EDX
  End;

Function OpenBit(i: LongInt): LongInt;
  ASM
    MOV    EDX, -1
    BSR    EDX, &i
    MOV    EAX, EDX
  End;

Function OpenBit(Const i: LargeInt): LongInt;
  ASM
    MOV    EAX, -1
    BSR    EAX, DWORD PTR [&i]
    JNZ    @@Exit
    BSR    EAX, DWORD PTR [&i + 4]
    JZ     @@Exit
    ADD    EAX, 32
    @@Exit:
  End;

Function CloseBit(i: Byte): LongInt;
  ASM
    AND    EAX, $000000ff
    MOV    EDX, -1
    BSF    EDX, EAX{&i}
    MOV    EAX, EDX
  End;

Function CloseBit(i: Word): LongInt;
  ASM
    AND    EAX, $0000ffff
    MOV    EDX, -1
    BSF    EDX, EAX{&i}
    MOV    EAX, EDX
  End;

Function CloseBit(i: LongWord): LongInt;
  ASM
    MOV    EDX, -1
    BSF    EDX, &i
    MOV    EAX, EDX
  End;

Function CloseBit(Const i: LargeWord): LongInt;
  ASM
    MOV    EAX, -1
    BSF    EAX, DWORD PTR [&i + 4]
    JNZ    @@Exit
    BSF    EAX, DWORD PTR [&i]
    JZ     @@Exit
    ADD    EAX, 32
    @@Exit:
  End;

Function CloseBit(i: ShortInt): LongInt;
  ASM
    AND    EAX, $000000ff
    MOV    EDX, -1
    BSF    EDX, EAX{&i}
    MOV    EAX, EDX
  End;

Function CloseBit(i: SmallInt): LongInt;
  ASM
    AND    EAX, $0000ffff
    MOV    EDX, -1
    BSF    EDX, EAX{&i}
    MOV    EAX, EDX
  End;

Function CloseBit(i: LongInt): LongInt;
  ASM
    MOV    EDX, -1
    BSF    EDX, &i
    MOV    EAX, EDX
  End;

Function CloseBit(Const i: LargeInt): LongInt;
  ASM
    MOV    EAX, -1
    BSF    EAX, DWORD PTR [&i + 4]
    JNZ    @@Exit
    BSF    EAX, DWORD PTR [&i]
    JZ     @@Exit
    ADD    EAX, 32
    @@Exit:
  End;

Function CountBits(i: Byte): LongInt;
  ASM
    MOV    ECX, 8
    MOV    DL, &i
    XOR    EAX, EAX
    @@Loop:
    SHR    EDX, 1
    JNC    @@noInc
    INC    EAX
    @@noInc:
    LOOP   @@Loop
  End;

Function CountBits(i: Word): LongInt;
  ASM
    MOV    ECX, 16
    MOV    DX, &i
    XOR    EAX, EAX
    @@Loop:
    SHR    EDX, 1
    JNC    @@noInc
    INC    EAX
    @@noInc:
    LOOP   @@Loop
  End;

Function CountBits(i: LongWord): LongInt;
  ASM
    MOV    ECX, 32
    MOV    EDX, &i
    XOR    EAX, EAX
    @@Loop:
    SHR    EDX, 1
    JNC    @@noInc
    INC    EAX
    @@noInc:
    LOOP   @@Loop
  End;

Function CountBits(Const i: LargeWord): LongInt;
  ASM
    XOR    EAX, EAX
    MOV    ECX, 32
    MOV    EDX, DWORD PTR [&i]
    @@Loop1:
    SHR    EDX, 1
    JNC    @@noInc1
    INC    EAX
    @@noInc1:
    LOOP   @@Loop1
    MOV    ECX, 32
    MOV    EDX, DWORD PTR [&i + 4]
    @@Loop2:
    SHR    EDX, 1
    JNC    @@noInc2
    INC    EAX
    @@noInc2:
    LOOP   @@Loop2
  End;

Function CountBits(i: ShortInt): LongInt;
  {$IFDEF UseInline}
    Begin
      Result := CountBits(Byte(i));
    End;
  {$ELSE}
    Const FD: Function(i: Byte): LongInt = CountBits;

    ASM
      JMP &FD
    End;
  {$ENDIF}

Function CountBits(i: SmallInt): LongInt;
  {$IFDEF UseInline}
    Begin
      Result := CountBits(Word(i));
    End;
  {$ELSE}
    Const FD: Function(i: Word): LongInt = CountBits;

    ASM
      JMP &FD
    End;
  {$ENDIF}

Function CountBits(i: LongInt): LongInt;
  {$IFDEF UseInline}
    Begin
      Result := CountBits(LongWord(i));
    End;
  {$ELSE}
    Const FD: Function(i: LongWord): LongInt = CountBits;

    ASM
      JMP &FD
    End;
  {$ENDIF}

Function CountBits(Const i: LargeInt): LongInt;
  {$IFDEF UseInline}
    Begin
      Result := CountBits(LargeWord(i));
    End;
  {$ELSE}
    Const FD: Function(Const i: LargeWord): LongInt = CountBits;

    ASM
      POP EBP
      JMP &FD
    End;
  {$ENDIF}

Function OneBit(i: Byte): LongInt;
  ASM
    AND    EAX, $000000ff
    BSF    EDX, EAX{&i}
    JZ     @@None
    BSR    ECX, EAX{&i}
    CMP    ECX, EDX
    JNE    @@None
    MOV    EAX, EDX
    RET
    @@None:
    MOV    EAX, -1
  End;

Function OneBit(i: Word): LongInt;
  ASM
    AND    EAX, $0000ffff
    BSF    EDX, EAX{&i}
    JZ     @@None
    BSR    ECX, EAX{&i}
    CMP    ECX, EDX
    JNE    @@None
    MOV    EAX, EDX
    RET
    @@None:
    MOV    EAX, -1
  End;

Function OneBit(i: LongWord): LongInt;
  ASM
    BSF    EDX, &i
    JZ     @@None
    BSR    ECX, &i
    CMP    ECX, EDX
    JNE    @@None
    MOV    EAX, EDX
    RET
    @@None:
    MOV    EAX, -1
  End;

Function OneBit(Const i: LargeWord): LongInt;
  ASM
    BSF    EAX, DWORD PTR [&i]
    JZ     @@HiTest
    BSR    EDX, DWORD PTR [&i]
    CMP    EAX, EDX
    JNE    @@None
    TEST   DWORD PTR [&i + 8], 0
    JNE    @@None
    TEST   DWORD PTR [&i + 8], 0
    JNE    @@None
    JMP    @@Exit

    @@HiTest:
    BSF    EAX, DWORD PTR [&i + 8]
    JZ     @@None
    BSR    EDX, DWORD PTR [&i + 8]
    CMP    EAX, EDX
    JNE    @@None
    JMP    @@Exit

    @@None:
    MOV    EAX, -1
    @@Exit:
  End;

Function OneBit(i: ShortInt): LongInt;
  ASM
    AND    EAX, $000000ff
    BSF    EDX, EAX{&i}
    JZ     @@None
    BSR    ECX, EAX{&i}
    CMP    ECX, EDX
    JNE    @@None
    MOV    EAX, EDX
    RET
    @@None:
    MOV    EAX, -1
  End;

Function OneBit(i: SmallInt): LongInt;
  ASM
    AND    EAX, $0000ffff
    BSF    EDX, EAX{&i}
    JZ     @@None
    BSR    ECX, EAX{&i}
    CMP    ECX, EDX
    JNE    @@None
    MOV    EAX, EDX
    RET
    @@None:
    MOV    EAX, -1
  End;

Function OneBit(i: LongInt): LongInt;
  ASM
    BSF    EDX, &i
    JZ     @@None
    BSR    ECX, &i
    CMP    ECX, EDX
    JNE    @@None
    MOV    EAX, EDX
    RET
    @@None:
    MOV    EAX, -1
  End;

Function OneBit(Const i: LargeInt): LongInt;
  {$IFDEF UseInline}
    Begin
      Result := OneBit(LargeWord(i));
    End;
  {$ELSE}
    Const FD: Function(Const i: LargeInt): LongInt = OneBit;

    ASM
      POP EBP
      JMP &FD
    End;
  {$ENDIF}

gammatester 7. Mai 2009 08:07
Re: IsPowerOfTwo
 
Der einfachste (und schnellste?) Test ist wohl
Delphi-Quellcode:
IsPowerOfTwo := (i<>0) and (i and pred(i) = 0);
Gültig für alle Integer-Typen und vollständig ohne asm.


Gammatester

himitsu 7. Mai 2009 09:20
Re: IsPowerOfTwo
 
ist och hübsch und funktioniert ... entspricht auch Hagens 2. Version :angel:

3_of_8 7. Mai 2009 09:34
Re: IsPowerOfTwo
 
Funktioniert aber so nicht bei negativen Zahlen - da müsste man ein i>0 reintun.

himitsu 7. Mai 2009 09:39
Re: IsPowerOfTwo
 
Zitat:
Zitat von 3_of_8
Funktioniert aber so nicht bei negativen Zahlen - da müsste man ein i>0 reintun.
ist klar, da durch die Dastellung oben alles 1 und unten alle Bits 0 sein müßten (siehe Aufbau des Zweierkomplements)

mit aktiver Bereichsprüfung
Delphi-Quellcode:
Function IsPowerOfTwo(i: Integer): Boolean;
  Begin
    Result := (i = Low(Integer))
      or (i > 0) and (i and Pred(i) = 0)
      or (i < 0) and (-i and Pred(-i) = 0);
  End;
ohne Bereichsprüfung
Delphi-Quellcode:
Function IsPowerOfTwo(i: Integer): Boolean;
  Begin
    Result := (i > 0) and (i and Pred(i) = 0)
      or (i < 0) and (-i and Pred(-i) = 0);
  End;
[edit]
Überlaufprüfung beachtet
oder man schaltet die Prüfung in der Funktion geziehlt um

mleyen 7. Mai 2009 11:06
Re: IsPowerOfTwo
 
@himitsu:
Oben hast du Performancemäßig ja noch genau einen ASM-Befehl rausoptimiert.

Jetzt mit deiner Methode zur Prüfung auf negative Zahlen hast du bis zu 7 ASM-Befehle unnötig reingbracht.

Hier mal meine Lösung, die Performancemäßig am besten war:
Delphi-Quellcode:
function IsPowerOfTwoInl(const Value: Cardinal): Boolean; inline;
begin
  Result := (Value > 0) and (Value and (Value -1) = 0);
end;
//...
var
  value: Cardinal;
begin
  isPow2 := IsPowerOfTwoInl(value);
end;
Dieses ergibt 11 ASM-Befehle, wobei durch optimale Jumps minimal 6 Befehle durchlaufen werden.


Wenn man jetzt negative Zahlen testen will, soll man folgendes machen:
Delphi-Quellcode:
//...
var
  value: Integer;
begin
  isPow2 := IsPowerOfTwoInl(Abs(value));
end;
Diese ergibt 14 ASM-Befehle, wobei durch optimale Jumps minimal 7 Befehle durchlaufen werden.
(Dabei habe ich die standard Delphi abs()-Funktion genommen.)


Also negaH´s Funktion ist schon sehr schnell, wer aber noch mehr will, der sollte "inline" hinten dran hängen.

himitsu 7. Mai 2009 12:38
Re: IsPowerOfTwo
 
wie gesagt, die Bereichsprüfung sollte besser nicht unterschlagen werden (in ASM gibt's damit aber keine Probleme :mrgreen: )

Delphi-Quellcode:
Function IsPowerOfTwo(i: Cardinal): Boolean; Inline;
  Begin
    {$IFOPT R+}
      {$R-}
        Result := (i <> 0) and (i and Pred(i) = 0);
      {$R+}
    {$ELSE}
      Result := (i <> 0) and (i and Pred(i) = 0);
    {$ENDIF}
  End;

// oder

Function IsPowerOfTwo(i: Cardinal): Boolean; Inline;
  Begin
    {$IFOPT R+}
      {$DEFINE IsPowerOfTwo_RangechecksOn}
      {$R-}
    {$ELSE}
      {$UNDEF IsPowerOfTwo_RangechecksOn}
    {$ENDIF}
    Result := (i <> 0) and (i and Pred(Abs(i)) = 0);
    {$IFDEF IsPowerOfTwo_RangechecksOn}
      {$R+}
    {$ENDIF}
  End;

// oder (wobei bei in meinen Codes _TEMP_ immer frei ist ... nicht daß man da mal ausversehn was überschreibt)

Function IsPowerOfTwo(i: Cardinal): Boolean; Inline;
  Begin
    {$IFOPT R+} {$R-} {$DEFINE _TEMP_} {$ELSE} {$UNDEF _TEMP_} {$ENDIF}
    Result := (i <> 0) and (i and Pred(Abs(i)) = 0);
    {$IFDEF _TEMP_} {$R+} {$ENDIF}
  End;
Delphi-Quellcode:
Function IsPowerOfTwo(i: Integer): Boolean; Inline;
  Begin
    {$IFOPT R+}
      {$R-}
        Result := (i <> 0) and (i and Pred(Abs(i)) = 0);
      {$R+}
    {$ELSE}
      Result := (i <> 0) and (i and Pred(Abs(i)) = 0);
    {$ENDIF}
  End;

// oder

Function IsPowerOfTwo(i: Integer): Boolean; Inline;
  Begin
    {$IFOPT R+}
      {$DEFINE IsPowerOfTwo_RangechecksOn}
      {$R-}
    {$ELSE}
      {$UNDEF IsPowerOfTwo_RangechecksOn}
    {$ENDIF}
    Result := (i <> 0) and (i and Pred(Abs(i)) = 0);
    {$IFDEF IsPowerOfTwo_RangechecksOn}
      {$R+}
    {$ENDIF}
  End;

// oder ...

Function IsPowerOfTwo(i: Integer): Boolean; Inline;
  Begin
    {$IFOPT R+} {$R-} {$DEFINE _TEMP_} {$ELSE} {$UNDEF _TEMP_} {$ENDIF}
    Result := (i <> 0) and (i and Pred(Abs(i)) = 0);
    {$IFDEF _TEMP_} {$R+} {$ENDIF}
  End;

gammatester 7. Mai 2009 14:26
Re: IsPowerOfTwo
 
Zwei Anmerkungen:

1. In dem angeführten Code ist mM ein Rangecheck nicht nötig! Wo soll er denn zuschlagen, wenn i>0 ist?

2. Völlig überflüssig sind die abs()-Aufrufe, wenn i>0 ist.

Gammatester

himitsu 7. Mai 2009 14:37
Re: IsPowerOfTwo
 
2: das > war 'nen Copy&Paster-Fehlerchen :oops: und sollte ein <> sein

1: Abs(MinInt) = MaxInt+1 , also außerhalb des Wertebereichs, da der negative Bereich um 1 größer ist, also der Positive, weil die 0 im positiven Bit-Satz enthalten ist.

Delphi-Quellcode:
// ohne Rangeprobleme, da der Sonderfall von MinInt abgefangen wird
Result := (i = Low(Integer))
  or (i > 0) and (i and Pred(i) = 0)
  or (i < 0) and (-i and Pred(-i) = 0);

// mit Rangeproblem
Result := (i > 0) and (i and Pred(i) = 0)
  or (i < 0) and (-i and Pred(-i) = 0);

// mit Rangeproblem - verkürzt
Result := (i <> 0) and (i and Pred(Abs(i)) = 0);

3_of_8 7. Mai 2009 15:35
Re: IsPowerOfTwo
 
Zitat:
Zitat von himitsu
Zitat:
Zitat von 3_of_8
Funktioniert aber so nicht bei negativen Zahlen - da müsste man ein i>0 reintun.
ist klar, da durch die Dastellung oben alles 1 und unten alle Bits 0 sein müßten (siehe Aufbau des Zweierkomplements)
Mit Zweierkomplement hat das nichts zu tun - negative Zahlen können nunmal einfach keine Zweierpotenz sein, da 2^i>0 für alle reellen i. (Bei komplexen Exponenten sieht das wieder anders aus, aber darum gehts ja hier nicht.)

himitsu 7. Mai 2009 15:57
Re: IsPowerOfTwo
 
Zitat:
Zitat von 3_of_8
Mit Zweierkomplement hat das nichts zu tun - negative Zahlen können nunmal einfach keine Zweierpotenz sein, da 2^i>0 für alle reellen i. (Bei komplexen Exponenten sieht das wieder anders aus, aber darum gehts ja hier nicht.)
ach menno, so kann man sich auch verdenken :wall:

dann also > wieder rein und Abs raus :nerd:
Delphi-Quellcode:
Result := (i > 0) and (i and Pred(i) = 0);

negaH 16. Aug 2009 08:44
Re: IsPowerOfTwo
 
Davon abgesehen ist in meinem originalem Code der Parameter "Value" mit Absicht als Cardinal deklariert. Der kann garnicht < 0 werden, mal abgesehen davon das ältere Delphi Versionen den vorzeichenlosen Cardinal als vorzeichenbehafteten Integer interpretierten.

Wenn du ASM benutzen möchtest dann so

Delphi-Quellcode:
function IsPowerOfTwo(Value: Cardinal): Boolean; assembler;
asm
     LEA EDX, EAX -1
     AND EAX, EDX
     SETZ AL
end;
Diese Funktion dürfte die am schnellsten ausführbare auf heutigen Intel CPUs sein, also auch Branch frei. Allerdings wird der Wert 0 auch als Potenz von 2 betrachtet.

Deine BSF/BSR Opcodes sind "arsch langsam" ;)

Gruß Hagen


Alle Zeitangaben in WEZ +1. Es ist jetzt 18:40 Uhr.

Powered by vBulletin® Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024-2025 by Thomas Breitkreuz