zwei Binärwerte vergleichen

[Mark]

Hallo zusammen,

ich würde gerne wissen wie ich folgendes am schnellsten (bezogen auf die Rechenzeit) lösen kann:

Ich habe zwei Arrays mit Binärwerten:

array1[0] = 1;  
array1[1] = 1;  
array1[2] = 0;  
array1[...] = ...;  
array1[2000] = 1;  
  
array2[0] = 0;  
array2[1] = 0;  
array2[2] = 1;  
array2[...] = ...;  
array2[4000] = 1;

Nun möchte ich gerne wissen an wieviele Stellen die Binärwerte gleich sind.
Danach möchte ich wissen ob die Binärwerte sich mehr ähneln, wenn ich das kleinere Array um eine Stelle verschiebe. Ich verschiebe also die beiden gegeneinander um Maximal X Stellen:

for (j=0; j<X; j++) {  
  for (i=0; i<array1.size(); i++) {  
    if (array1[i] == array2[i+j]) {  
      zaehler[j] = zaehler[j]++;  
    }  
  }  
}

Der schnellste Vergleich zweier Zahlen dürfte eigentlich der Binärvergleich mit dem "&" Operator sein. Jedoch müsste ich dazu meine Binärzahlen aus den Arrays auslesen in eine Int umwandeln und dann vergleichen, oder gibt es eine andere Lösung? Wie mach ich dann das Verschieben am besten? Und wie große "Binararrays" kann ich in ein Int wandeln?

Noch zur Info:
Das ganze soll in C++ entwickelt werden und der Quelltext ist nur zur Erklärung und nicht funktional...

Bin für jeden Tip Dankbar.
Beste Grüße
Mark

[Alexander (HH)]

Moin Moin!

Hmmm, memcmp könnte Dir helfen, zwei beliebige Speicherblöcke zu vergleichen. Was Du versuchst zu bauen, scheint Ähnlichkeit mit rsync zu haben.

Alexander

[hotti]

hi,

[..] Und wie große "Binararrays" kann ich in ein Int wandeln?

Was deine CPU kann: z.B. 32 bit / 0xFFFFffff (unsigned)

Für mein Script Route Summary hab ich das (mit Perl) so gemacht, dass ich die integer in Bit-Arrays umgewandelt habe (wo Du schon hast) und die Einzel-Bits mit shift aus den Arrays gezogen habe.

Effektiver ists jedoch, den Bit-Shift-Operator (Right-Shift >>, Left-Shift <<) direkt auf die Integer-Werte anzuwenden, einzelne Bits also nach rechts rausschieben und mit der Maske 1 ein bitweises AND (&) zu machen um ein Einzelbit zu kriegen.

Ob der Integer als 0xF oder 15 notiert ist, ein 15 >> 1 ergibt dasselbe wie ein 0xF >> 1 und das geht in c wie in Perl.

Hotte