AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren

SetBit-Funktion verbessern?

Ein Thema von SirThornberry · begonnen am 10. Jul 2004 · letzter Beitrag vom 11. Jul 2004
Antwort Antwort
Benutzerbild von SirThornberry
SirThornberry
(Moderator)

Registriert seit: 23. Sep 2003
Ort: Bockwen
12.235 Beiträge
 
Delphi 2006 Professional
 
#1

SetBit-Funktion verbessern?

  Alt 10. Jul 2004, 18:17
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
Jens
Mit Source ist es wie mit Kunst - Hauptsache der Künstler versteht's
  Mit Zitat antworten Zitat
Basilikum

Registriert seit: 9. Aug 2003
389 Beiträge
 
Delphi 7 Professional
 
#2

Re: SetBit-Funktion verbessern?

  Alt 10. Jul 2004, 19:15
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;
  Mit Zitat antworten Zitat
Benutzerbild von negaH
negaH

Registriert seit: 25. Jun 2003
Ort: Thüringen
2.950 Beiträge
 
#3

Re: SetBit-Funktion verbessern?

  Alt 10. Jul 2004, 20:16
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
  Mit Zitat antworten Zitat
Basilikum

Registriert seit: 9. Aug 2003
389 Beiträge
 
Delphi 7 Professional
 
#4

Re: SetBit-Funktion verbessern?

  Alt 10. Jul 2004, 20:46
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 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;
  Mit Zitat antworten Zitat
Benutzerbild von negaH
negaH

Registriert seit: 25. Jun 2003
Ort: Thüringen
2.950 Beiträge
 
#5

Re: SetBit-Funktion verbessern?

  Alt 10. Jul 2004, 23:42
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
  Mit Zitat antworten Zitat
Benutzerbild von SirThornberry
SirThornberry
(Moderator)

Registriert seit: 23. Sep 2003
Ort: Bockwen
12.235 Beiträge
 
Delphi 2006 Professional
 
#6

Re: SetBit-Funktion verbessern?

  Alt 11. Jul 2004, 08:27
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
Jens
Mit Source ist es wie mit Kunst - Hauptsache der Künstler versteht's
  Mit Zitat antworten Zitat
Benutzerbild von atreju2oo0
atreju2oo0

Registriert seit: 5. Dez 2003
Ort: Berlin
289 Beiträge
 
Delphi 6 Enterprise
 
#7

Re: SetBit-Funktion verbessern?

  Alt 11. Jul 2004, 10:24
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?
Thomas
  Mit Zitat antworten Zitat
neolithos

Registriert seit: 31. Jul 2003
Ort: Dresden
1.386 Beiträge
 
Delphi 7 Architect
 
#8

Re: SetBit-Funktion verbessern?

  Alt 11. Jul 2004, 11:43
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.
- ciao neo -
Es gibt niemals dumme Fragen, sondern nur dumme Antworten!
  Mit Zitat antworten Zitat
Benutzerbild von negaH
negaH

Registriert seit: 25. Jun 2003
Ort: Thüringen
2.950 Beiträge
 
#9

Re: SetBit-Funktion verbessern?

  Alt 11. Jul 2004, 12:52
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
  Mit Zitat antworten Zitat
Benutzerbild von atreju2oo0
atreju2oo0

Registriert seit: 5. Dez 2003
Ort: Berlin
289 Beiträge
 
Delphi 6 Enterprise
 
#10

Re: SetBit-Funktion verbessern?

  Alt 11. Jul 2004, 19:45
Vielen Dank für die Antwort.
Das hat mir echt geholfen.
Thomas
  Mit Zitat antworten Zitat
Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 14:57 Uhr.
Powered by vBulletin® Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2019 by Daniel R. Wolf