IsPowerOfTwo

[himitsu]

Hab hier noch was Kleines als Nachtrag

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]

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

[Desmulator]

Zitat von Dax:

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 Grübelnd...

Wenn man es als inline deklarieren würde, wie wärs dann?

[himitsu]

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]

Der einfachste (und schnellste?) Test ist wohl IsPowerOfTwo := (i<>0) and (i and pred(i) = 0); Gültig für alle Integer-Typen und vollständig ohne asm.


Gammatester

[himitsu]

ist och hübsch und funktioniert ... entspricht auch Hagens 2. Version

[3_of_8]

Funktioniert aber so nicht bei negativen Zahlen - da müsste man ein i>0 reintun.

[himitsu]

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]

@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]

wie gesagt, die Bereichsprüfung sollte besser nicht unterschlagen werden (in ASM gibt's damit aber keine Probleme )

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;