Ich habe den Wikipedia-Artikel über Hamming Weight gelesen und etwas Interessantes bemerkt:
Es ist also gleichbedeutend mit
Hamming distancevon der gesamten Null-Zeichenfolge mit der gleichen Länge . Für den typischsten Fall, eine Bitfolge, ist dies die Anzahl der 1en in der Zeichenfolge. In diesem binären Fall wird es auch als Bevölkerungszahl,popcountoder Seitwärtssumme bezeichnet.[Betonung meiner]
So etwas ist mir eingefallen. Könnte ich die Hamming-Distanz zwischen zwei Strings mit XOR ing berechnen und dann die Hamming-Gewichtung (POPCOUNT) des resultierenden Strings nehmen?
Etwas in dieser Richtung (mit gcc intrinsics):
Was nun, warum ich das machen möchte, nun, auf einigen Plattformen, würde ja das nur bedeuten, dass gcc einen Aufruf an eine Funktion ausgibt, die popcount berechnet. Zum Beispiel, auf x64 ohne popcnt , gcc spuckt aus ( Godbolts GCC Online ):
OTOH, wenn Sie eine Plattform haben, die POPCOUNT unterstützt, wie x64-Modelle einschließlich nehalem und after (mit POPCNT ), erhalten Sie ( Godbolts GCC Online ):
was sollte schneller sein, vor allem einmal inline.
Aber zurück zur ursprünglichen Frage. Kannst du das Hamming-Gewicht des XOR zweier Saiten nehmen, um ihre Hamming-Distanz zu finden? zB:
%Vor% Die Hamming-Distanz zwischen zwei gleich langen Strings, x und y , ist definiert als die Anzahl der Positionen, an denen sie sich unterscheiden. Wenn x und y Bitstrings sind, ist x^y eine Zeichenfolge mit 1 s genau in den Positionen, in denen sie sich unterscheiden. Also, HammingDistance(x,y) = Number of 1s in x^y , für Bitstrings. Außerdem HammingWeight(x) = number of 1s in x für eine Bitfolge x . Daher gilt Ihr erster Anspruch HammingDistance(x,y) = HammingWeight(x^y) für Bitstrings. Wenn Sie dies festgestellt haben, ist es klar, dass Ihre Implementierung korrekt ist.
Ja, das funktioniert. Für jedes Bit ist das Bit genau dann 1, wenn die Eingangsbits unterschiedlich sind. Bei einem ganzzahligen Bitvektor hat das Ergebnis daher so viele Bits (HW) wie die Eingänge unterschiedliche Bits (HD) haben. Und dein Code scheint diese Beziehung perfekt auszunutzen. Tatsächlich wird diese Abkürzung sogar weiter in dem Hamming Weight Artikel erwähnt, zu dem Sie verlinken ( Efficient implementation ):
Die Hamming-Distanz der beiden Wörter A und B kann als Hamming-Gewicht von A xor B berechnet werden.
Tags und Links c gcc intrinsics hamming-distance