如何计算两个短整数的汉明距离？(How to count the hamming distance of two short int?)

如何计算两个短整数的汉明距离？(How to count the hamming distance of two short int?)

海明距离：

例如，两个二进制数：1011和1000的HD（汉明距离）是2。

10000和01111的HD是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; }

Hamming Distance:

For example, two binary number: 1011 and 1000's HD(Hamming distance) is 2.

The 10000 and 01111's HD is 5.

Here is the code:

Can some one explain it to me?

Thanks!

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? }

它被称为Brian Kernighan算法 。

最后，整个代码计算不同的位数，即汉明距离。

This instruction will give you a number with all bits that differs from x to y are set :

char val = x^y;

Example : 0b101 ^ 0b011 = 0b110

Notice that val should have the same type of the operands (aka a short). Here, you are downcasting a short to a char, loosing information.

The following is an algorithm used to count the number of bits set in a number :

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

It is known as the Brian Kernighan algorithm.

So finally, the whole code counts bits that differs, which is the hamming distance.