Как посчитать расстояние Хемминга двух коротких 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;
}

11

Решение

Эта инструкция даст вам число со всеми установленными битами, которые отличаются от x до y:

char val = x^y;

Пример : 0b101 ^ 0b011 = 0b110

Заметить, что val должен иметь один и тот же тип операндов (иначе short). Здесь вы понижаете short к char, теряя информацию.

Ниже приведен алгоритм, используемый для подсчета количества бит, установленных в числе:

short dist = 0;
while(val)
{
++dist;
val &= val - 1; // why?
}

Это известно как Алгоритм Брайана Кернигана.

Итак, наконец, весь код подсчитывает биты, которые отличаются, что является расстоянием Хэмминга.

19

Другие решения

Расстояние Хэмминга — это расстояние между двумя числами, но рассчитывается следующим образом:

Например расстояние между 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;
}
0