Anwenden von logischen (bitweise) Operatoren

[Constantinus van der Kruijs]

Hier etwas für die mathematiker unter euch.

Vorhanden ist ein array mit integerwerten, die boolsche werte representieren.
Das problem ist, dass ich zwei dieser integer's vergleichen.

Herausfinden möchte ich, ob sie sich in einem einzelnen bit unterscheiden, und wenn ja, in welchem bit sie das tun.

Beispiel:
<pre>
Variable Hex Boolean
int1 $00 $00 $00 $00 0000000000000000000000000000000
int2 $00 $40 $00 $00 0000000000000010000000000000000
int3 $00 $40 $01 $00 0000000000000010100000000000000
</pre>

Beim Vergleich von int1 mit int2 möchte ich als ergebnis herausbekommen,
dass sie sich tatsächlich in einem bit unterscheiden, und dessen index
ist 14. (Ergebnis: 14)

Beim vergleich von int1 mit int3 soll lediglich festgestellt werden,
dass sich mehr als ein bit unterscheiden.
(Ergebnis: false)

Beim vergleich von int2 mit int3 soll festgestellt werden, dass sie
sich in einem bit (index ist 16) unterscheiden
(Ergebnis: 16)

Wie gehe ich dabei vor?

[Robert Marquardt]

Bei "int1 xor int2" sind alle Bits 1, die sich unterscheiden und alle gleichen Bits 0.<br>
Das loest jetzt nur einen Teil dr aufgabe, aber ueber den rest denke ich ein andermal nach

[Ulrich Gerhardt]

Mir fällt da spontan TBits.OpenBit ein.
Hab ich aber noch nie genauer angeschaut.
<br>Uli

[Frank ter Duis]

wie wärs damit:<br><br>
function PrfArray(Array1 : Array of Boolean; Array2 : Array of Boolean; Laenge : integer): integer;<br>
var<br>
i : integer;<br>
Position : integer;<br>
Ergebnis : boolean;<br>
begin<br>
<br>
Position := 0;<br>
<br>
for i := 0 to Laenge -1 do<br>
begin<br>
Ergebnis := Array1[i] xor Array2[i];<br>
if (Ergebnis) and (Position = 0) then<br>
Position := i +1<br>
else<br>
if (Ergebnis) and (Position <> 0) then Position := -1;<br>
end;<br>
<br>
PrfArray := Position;<br>
<br>
end;<br><br>
Aufruf: PrfArray([true, false, false], [true, false, true], 3);<br><br>
PrfArray gibt die Position (beginnend bei 1) der ersten Ungleichheit wieder. Bei mehreren Ungleichheiten wird -1 zurückgegeben. <br><br>
Bye Fran

[Frank ter Duis]

Noch ein kleines Update, so kann man sich sparen die Länge der Arrays mitzugeben:<br><br>
function PrfArray(Array1 : Array of Boolean; Array2 : Array of Boolean): integer;<br>
var<br>
i : integer;<br>
Position : integer;<br>
Ergebnis : boolean;<br>
begin<br>
<br>
Position := 0;<br>
<br>
if length(Array1) = Length(Array2) then<br>
begin<br>
for i := 0 to Length(Array1) -1 do<br>
begin<br>
Ergebnis := Array1[i] xor Array2[i];<br>
if (Ergebnis) and (Position = 0) then<br>
Position := i +1<br>
else<br>
if (Ergebnis) and (Position <> 0) then Position := -1;<br>
end;<br>
end<br>
else<br>
Position := -2;<br>
<br>
PrfArray := Position;<br>
<br>
end;<br>
<br>
Sind die Arrays nicht gleich lang wird -2 zurück gegeben

[Robert Marquardt]

Wenn du schon so schweres Geschuetz auffaehrst dann kann man auch die Jedi Code Library empfehlen, die in JclLogic alles zu Bits in Worten anbietet

[Frank ter Duis]

... sorry, aber ich kenn mich in der JediCodeLibrary nicht so wirklich aus. ;-)<br><br>
Und wenn etwas in 5 min. Prgrammiert ist, brauche ich nicht 30 Minuten in irgendwelchen Librarys suchen. Man sollte nicht mit Kanonnen auf Spatzen schießen.<br><br>
Schönes Wochenende (Jawohl!!!!) ;-)<br><br>
Gruß Fran

[Constantinus van der Kruijs]

Hallo Frank,

Das ganze in 'ne schleife zu packen habe ich bereits in erwägung gezogen. Doch handelt es sich bei mir um einen vorgang, bei dem ich ca 600.000 solcher arrays miteinander vergleichen muss (also ca. 600.000 n! vergleiche). Dabei jeweils zwei arrays elementweise zu vergleichen nimmt insgesamt zu viel zeit in anspruch. Daher dachte ich an sowas:
<pre>
var z: integer;
_bitsets: array of integer;
_ext: Extended;

...

// differenz-maske bilden
z := _bitsets[x] XOR _bitsets[y];
// prüfen, ob eine abweichung vorliegt
if (z>0) then
begin
// sehen, ob abweichung
// auf einem einzelnen bit
// vorliegt
// -> nur wenn sich eine einzelne stelle
// unterscheidet,
// ist z ganzzahlig *zweifel*
_ext:=log2(z);
if( frac(_ext)=0 )then
begin
// die stelle der abweichung
z:=trunc(_ext);
// ... hier die weitere
// verarbeitung des ergebnisses
end;
end;
</pre&gt

[Robert Marquardt]

Fuer das Zaehlen der Bits in einem 32-Bit Wort hat der Pentium glaube ich einen Befehl. Da wuerde es sich lohnen eine Assembler-Funktion einzuschieben

[Frank ter Duis]

.... also bei mir dauern 1.000.000 Vergleiche eines 20 stelligen Arrays 3,6 MilliSec (gerundet ;-)). Ich habe einen P3 800 MHZ mit W2K... also nicht mal eine Powermaschine.... also so Zeitkritsch kann keine Anwendung sein...

[Frank ter Duis]

Zeitmäßig kann der Code auch noch optimiert werden, wenn man nachdem man Position auf -1 setzt ein Break macht... dann werden nicht mehr alle folgenden überflüssigen Operationen durchgeführt.... wirklich messbar ist diese Änderung aber erst bei 6.000.000 (!!!) Funktionsaufrufen mit einem 20 stelligen Array.<br><br>
Also ich denke, bei 600.000 Funktionsaufrufen, ist eine Optimirung kaum noch messbar.... <br> <br> Aber falls das nicht schnell genug ist, muß ich passen, da bin ich mit meinem Latein am Ende ;-

[Torsten Grundke]

Hallo zusammen,

die folgende Funktion liefert das gewünschte Ergebnis (-1 Zahlen identisch, -2 mehr als 1Bit unterschiedlich und ansonsten das Bit das sich unterscheidet).

<pre>
function TForm1.BitTest(const a, b: integer): integer; assembler;
asm
mov eax, -1 // Standardergebnis Zahlen sind identisch
xor a,b
jz @@end // Zahlen identisch
bsf eax, a // erstes gesetztes Bit von links ermitteln
bsr ecx, a // erstes gesetztes Bit von rechts ermitteln
cmp eax, ecx // Ergebnis von links und rechts vergleichen
jz @@end // links und rechts sind identisch -> es gibt nur ein Bit welches verschieden ist
// Ergebnis befindet sich EAX
mov eax, -2 // mehr als ein Bit ist unterschiedlich
@@end:
end;
</pre>

Optimal ist das aber noch nicht. Für eine optimale Performance sollte man noch den Funktionsaufruf vermeiden und die Speicherzugriffe optimieren.

Wenn es bei den zu analysierenden Daten Abweicherungen eher die Ausnahme sind dann
könnte man das XOR noch aus der Funktion rausnehmen.

Tschau

Torste

[Torsten Grundke]

Hallo Frank,

Deine 3,6 ms sind sehr mit Vorsicht zu geniesen. Wenn Du immer mit dem selben Array arbeitest liegen die Daten immer Cache und dadurch ist der Zugriff entsprechend schnell.

Ich habe bei mir testweise mit meiner Funktion zwei Array's mit jeweils 10 Millionen Integerwerten verglichen und dafür 0,7 Sekunden gebraucht.

Um überhaupt irgendwelche Laufzeitabschätzungen machen zu können müßten mehr Info's über die Größe der Array's vorliegen. Richtig entscheidende Optimierungen sind aber nur nach einer intensiven Datenanalyse und einer möglicherweise sinnvolleren Vergleichsmethode zu erwarten.

Tschau

Torste

[Constantinus van der Kruijs]

Hallo leute,

Es gefällt mir sehr gut, wie Ihr Euch die mühe macht, mir bei meinem problem zu helfen.
Leider hatte ich einen denkfehler beim entwurf der anforderung. Also werde ich im 'Diverses'-Forum die aufgabe nochmal neu posten

[Hagen Reddmann]

<pre>
function BitWeight(Value: Cardinal): Cardinal; assembler; register;
asm
MOV EDX,EAX
SHR EDX,1
AND EDX,055555555h
SUB EAX,EDX
MOV EDX,EAX
AND EAX,033333333h
SHR EDX,2
AND EDX,033333333h
ADD EAX,EDX
MOV EDX,EAX
SHR EDX,4
ADD EAX,EDX
AND EAX,00F0F0F0Fh
MOV EDX,EAX
SHR EDX,8
ADD EAX,EDX
MOV EDX,EAX
SHR EDX,16
ADD EAX,EDX
AND EAX,0FFh
end;<br>

if BitWeight(A xor B) = 1 then ;

</pre>

Und nein, Intel CPU's kennen keinen Befehl die Bits eines Wertes zu zählen.

Gruß Hage