SetBit-Funktion verbessern?

[SirThornberry]

hallo,

kann man

Delphi-Quellcode:

function SetBit(const AByte: Integer; const ANewBitStatus: Boolean; const ABitIndex: TBitIndex): Integer;
begin
  if ANewBitStatus then
     result := AByte or (1 shl (ABitIndex - 1))
  else
     result := AByte and not(1 shl (ABitIndex - 1));
end;

noch irgendwie verbessern. Also das es weniger performance benötigt. Irgendwie denk ich mir das man das "ABitindex - 1" doch bestimmt irgendwie weg optimieren kann damit eine rechenoperation weniger ausgeführt werden muss

[Basilikum]

wenn der Parameter ABitIndex per Definition zwischen 0 und 7 (oder 31) liegt, entfällt die Subtraktion...

hier das selbe in ASM:

Delphi-Quellcode:

Procedure                         asmBitSet(Var Value : LongWord;Const Bit : Byte;Const State : Boolean); Register;
Asm
  OR     CL,CL
  JNZ    @@True

  MOV    ECX,[EAX]
  BTR    ECX,EDX
  MOV    [EAX],ECX
  RET

@@True:
  MOV    ECX,[eax]
  BTS    ECX,EDX
  MOV    [EAX],ECX
end;

[negaH]

Delphi-Quellcode:

function BitSet(Value,BitIndex: LongWord; State: Boolean): LondWord; 
asm 
    shr   ecx, 1
    btc   eax, edx 
end;

procedure BitSet(var Value: LongWord; BitIndex: LongWord; State: Boolean);  
asm 
    shr   ecx, 1
    btc   dword ptr [eax], edx 
end;

Bit Indizes beginnt man immer von 0 bis X zu zählen, und nicht von 1 bis X.
Die Logik dahinter ist simpel da eine Binäre Zahl sich aus

2^0 + 2^1 + 2^2 + 2^3 + 2^4 + ... + 2^x zusammensetzt.

wie man sieht beginnt der Exponent mit 0 statt mit 1.

Die binäre Zahl 10110101 ist also

Code:

BitIndex= Exponent 76543210
                   10110101 = 1 * 2^7 + 0 * 2^6 + 1 * 2^5 + 1 * 2^4 + 0 * 2^3 + 1 * 2^2 + 0 * 2^2 + 1 * 2^0 =
                            =     128 +       0 +      32 +      16 +       0 +       4 +       0 +       1 =
                            = 181

Wie man sieht ist es essentiel das Bit Indizes mit 0 beginnen, dies schafft den Übergang in der Logik der Rechentechnik in die Logik der Mathematik.

Gruß Hagen

[Basilikum]

Zitat:

Zitat von negaH

Delphi-Quellcode:

function BitSet(Value,BitIndex: LongWord; State: Boolean): LondWord; 
asm 
    shr   ecx, 1
    btc   eax, edx 
end;

procedure BitSet(var Value: LongWord; BitIndex: LongWord; State: Boolean);  
asm 
    shr   ecx, 1
    btc   dword ptr [eax], edx 
end;

dies setzt jedoch voraus, dass das betroffene Bit nicht bereits 1 war...

Zitat:

Zitat von intel 8086 Family Architecture

The destination bit indexed by the source value is copied into the Carry Flag after being complimented (inverted).

also ist doch ein Compare notwendig:

Delphi-Quellcode:

Function BitSet(Const Value : LongWord;Const Bit : Byte;Const State : Boolean) : LongWord;
Asm
  OR     CL,CL
  JNZ    @@True

  BTR    EAX,EDX
  RET

@@True:
  BTS    EAX,EDX
end;

[negaH]

Stimmt, habe mich da im Assembler vertan und bin darauf reingefallen das ich momentan mit RISC MCUs arbeite ;)

BTR/BTS/BT/BTC sind auf Intel CPUs sehr langsam und eine Kombination aus SHL/SHR/AND/OR/XOR ist wesentlich effizienter:

Delphi-Quellcode:

function BitSet(Value: Cardinal; State: Boolean; Index: Cardinal): Cardinal;
asm
      test  dl, dl
      mov   edx, 1
      jz    @@1
  
      shl   edx, cl
      or    eax, edx
      ret

@@1:  shl   edx, cl
      not   edx
      and   eax, edx
end;

function BitSet(Value: Cardinal; State: Boolean; Index: Cardinal): Cardinal;
begin
  if State then Result := Value or (1 shl Index)
    else Result := Value and not (1 shl Index);
end;

Gruß Hagen

[SirThornberry]

Thx. TBitIndex hatte ich von 1 bis 64 definiert um mit Int64 noch arbeiten zu können wobei mir dann aufgefallen ist das es schwachsinn ist da meine funktion ja nur mit Integern arbeitet.
Wenn ich mir von Hagen

Delphi-Quellcode:

function BitSet(Value: Cardinal; State: Boolean; Index: Cardinal): Cardinal;
begin
  if State then Result := Value or (1 shl Index)
    else Result := Value and not (1 shl Index);
end;

anschaue ist das ja so ziemlich das gleiche wie in meinem Post nur das bei diesem Beispiel bei Bit 0 angefangen wird und bei mir war

Delphi-Quellcode:

type
  TBitIndex = 1..8; //bzw. dann 1..64

Naja, ok, dann fang ich bei Index 0 an um die eine Rechenoperation zu sparen. Wäre es nicht effektiver wenn man "Index" vom Type Byte defniert da er dann nicht mit überträgen etc. rumrechnen muss und nen Byte geht ja eher in ein Register als ein Cardinal oder nicht? Und 255 Bitshiftpositionen dürften ja auch reichen

welche der folgenden 3 Varianten wäre eigentlich die effektivste im Zusamenhang mit der Funktion (eventuell mit Begründung)

Delphi-Quellcode:

  TBitIndex = Byte; //Variante1
  TBitIndex = 0..7; //Variante2
  TBitIndex = Cardinal; //Variante3

[atreju2oo0]

Ich kann euch hier zwar leider nicht weiterhelfen, hätte da aber mal ne Frage zu diesem Thema.
Die Erklärung von Hagen bezieht sich doch auf duale Zahlen im Einer-Komplement, oder?
Und Rechner nutzten doch aber auch das Zweierkomlement...?
Meine Frage wäre ob das für die Rechenschritte keinen Unterschied macht oder ob man sich für negative Zahlen dann
extra Funktionen bauen muss bzw halt mit einbeziehen?
:gruebel:

[neolithos]

Ich weis nicht ob es dir Hilft

Positive Zahl 12 -> b00001100
Negative -12 Einkomplement -> b11110011 -> riesen Problem, es gibt einmal -0 und +0
desweiteren 12+-12 ergbibt -0
b00001100+b11110011=b11111111
desweiteren 15+-12 ergbibt -125
b00001111+b11110011=b00000010

Negative -12 Zweierkomplement -> b11110100 -> Einerkomplement +1
desweiteren 12+-12 ergbibt 0
b00001100+b11110100=0
desweiteren 15+-12 ergbibt -1
b00001111+b11110100=b00000011


Ergo: Komplemente haben etwas mit dem negativen Vorzeichen zu tun.

[negaH]

Zitat:

Ich kann euch hier zwar leider nicht weiterhelfen, hätte da aber mal ne Frage zu diesem Thema.
Die Erklärung von Hagen bezieht sich doch auf duale Zahlen im Einer-Komplement, oder?
Und Rechner nutzten doch aber auch das Zweierkomlement...?
Meine Frage wäre ob das für die Rechenschritte keinen Unterschied macht oder ob man sich für negative Zahlen dann
extra Funktionen bauen muss bzw halt mit einbeziehen?

Du verwechselst da was. Die SetBit() Funktion ist in die Gruppe der Boolschen Operationen zuzuordnen, sprich Rechenoperationen die der Boolschen Algebra angehören. Dort gibt es nur JA/NEIN Zustände und somit stellt ein Integer/Cardinal/Int64 ein Array aus Bits dar. Primär sind es also KEINE Zahlen im herkömmlichen Sinne sondern eher Sets aus Bits.

In der Boolschen Algebra arbeitet man mit den Operatoren AND/OR/XOR/NOT/SHL/SHR usw.

Die Zahlendarstellung wie du sie nachfragst bezieht sich auf die normale Zahlentheorie. Es ist somit klar das wenn man mit Integer arbeitet und das 31. Bit modifiziert sich das Vorzeichen des Wertes ändert, und zwar im Grunde mathematisch inkorrekt.

Nun, wie du aber siehst verwendet meine obige Funktion Cardinals. Diese sind vorzeichenlos und somit kann auch mathematisch gesehen nichts schiefgehen. Es gibt eben dan nur 32Bit positive Ganzzahlen.

Wie Neolithos es schon sagte wird auf Intel PC im Zweier-Komplement gearbeitet. Zweier/Einer-Komplement besagt aus wie man die Zahlen negiert, wie Negative Zahlen dargestellt werden, wo und wie das Vorzeichen gespeichert wird und als Kontequenz all dessen wie in der CPU die Befehle verdrahtet werden müssen.

Das wichtigste am Zweierkomplement ist es das es nur eine NULL gibt, und somit der Rechenschritt von +1 nach -1 eben 2 beträgt. Im Einerkomplement würde man +1 -3 = -1 rechnen müssen, dafür wäre die Negation einer Zahl identisch mit dem Boolschen Operator NOT = NICHT.
Im Zweierkomplement ist eine Negation eienr Zahl, also x = -x ein bischen komplizierter, nämlich X = not X +1.
D.h. 0000b - 0001b = 1111b -> 0 - 1 = -1 ist ein ganz normaler Rechen-Unterlauf um 1 Bit. not 1111b +1 = 0000b +1 = 1 wäre dann die Negation einer Zahl. not 0001b + 1 = 1110b + 1 = 1111b = -1 die Negation von +1 nach -1.

Das Zweierkomplement ist also 0-symmetrisch, hat aber KEINEN symmetrischen Wertebereich, denn er geht bei Integer von -2^31 < x < 2^31 -1, sprich binär eben von $80000000 <= x $7FFFFFFF. Der Binäre Wert $80000000, also Vorzeichenbit = 1 Rest der Bits alle 0 wäre der größte negative Wert.

Man muß sich einfach mal vorstellen wie eine binäre Addition zweier Zweierkomplementärzahlen aussieht.

Code:

Zahlen im Wertebereich -2^(4-1) <= x < +2^(4-1)
Binäre Addition 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, 1 + 1 = 0 +1 Bit Übertrag.

wie rechnen nun:

  1110b    =  -2
+ 0011b    =  +3
  -----

von Rechts nach Links addieren wir die Bits

1.)
  xxx0b
+ xxx1b
------
  xxx1b  kein Übertrag

2.)
  xx10b
+ xx11b
-------
= xx01b
  x100b Übertrag   
  
3.)
  x110b
  x011b
+ x100b obiger Übertrag
-------
= x001b
  1000b neuer Übertrag

4.)

  1110b
  0011b
+ 1100b  
-------
= 0001b == +1  
 10000b neuer Übertrag, aber ausserhalb des Wertebereiches  
 
Resultat von -2 + +3 = +1 == 0001b

Wie man sieht kann diese Addition direkt ohne zusätzliche Bewertungen oder Ausgleichsrechnung in Hardware umgesetzt werden. Nur auf Grund der Logik des Zweierkomplements kann man ohne Problem Zahlen Addieren/Subtrahieren ohne auf das Vorzeichen aufpassen zu müssen. Die "Vorzeichenbits" werden beim Zweierkomplement in der Addition/Subtraktion AUTOMAISCH durch die Einzelbit-Operationen und deren Über/Unterläufe eliminiert oder eben gesetzt. Tritt ein Überlauf/Unterlauf in der Addition/Subtraktion zweier Zahlen auf so muß es einen Finalen Übertrag geben, man kann also damit den Vorzeichen-Wechsel in der Operation erkennen.

Im Grunde muß man es historisch gesehen sogar umgekehrt betrachten. Zuerst war die CPU Hardware da die Addieren und Subtrahieren konnte (wie oben) und erst DANACH entstand der Begriff "Zweierkomplement".

Gruß Hagen

[atreju2oo0]

Vielen Dank für die Antwort.
Das hat mir echt geholfen.
:thuimb: