Как посчитать расстояние Хемминга двух коротких int?
Расстояние Хэмминга:
Например, два двоичных числа: 1011 и 1000-е HD (расстояние Хэмминга) равно 2.
HD 10000 и 01111 — это 5.
Вот код:
Кто-нибудь может мне это объяснить?
Спасибо!
short HammingDist(short x, short y)
{
short dist = 0;
char val = x^y;// what's the meaning?
while(val)
{
++dist;
val &= val - 1; // why?
}
return dist;
}
Решение
Эта инструкция даст вам число со всеми установленными битами, которые отличаются от x до y:
char val = x^y;
Пример : 0b101 ^ 0b011 = 0b110
Заметить, что val должен иметь один и тот же тип операндов (иначе short). Здесь вы понижаете short к char, теряя информацию.
Ниже приведен алгоритм, используемый для подсчета количества бит, установленных в числе:
short dist = 0;
while(val)
{
++dist;
val &= val - 1; // why?
}
Это известно как Алгоритм Брайана Кернигана.
Итак, наконец, весь код подсчитывает биты, которые отличаются, что является расстоянием Хэмминга.
Другие решения
Расстояние Хэмминга — это расстояние между двумя числами, но рассчитывается следующим образом:
Например расстояние между 2 (010) и 4 (100). Теперь мы хотим вычислить отличающиеся биты друг от друга, так как он принимает xor (xor вычисляет разные биты).
Возьмем XOR 2 и 4, равное 6 (110), и вычислим установленный бит в 6, равный 2, следовательно, расстояние Хэмминга между 2 и 4 равно 2.
В вашем коде:
short HammingDist(short x, short y)
{
short dist = 0;
char val = x^y;// calculate differ bit
while(val) //this dist veriable calculate set bit in loop
{
++dist;
val &= val - 1;
}
return dist;
}