2

我们都知道，两个二进制字符串的汉明距离就是不同的位数。而对于两个二进制字符串：1110 和 1101，如果我想用最高位的相同位数来描述它们的相似性。（在这个例子中，从左到右，数位，直到两个位不同，则结果为2。）这种相似性是否已经定义或有一个正式的名称？

4

1 回答 1

0

我咨询了我大学的其他几位教师，我们同意，我们还没有听说过这个:-)

然而，这类问题总是很有趣，尤其是当我以前从未见过它们时……所以我一直在研究解决方案。

作为一个澄清点，我的目标是找到两个等效存储数的二进制值之间的距离（我将称之为授予距离......嘿，为什么不呢？......我喜欢 OR Mapper 的评论）长度（比如两个无符号长整数），并且您忽略了所有前导 0。例如，无符号短裤 54090 与 3374... 54090 = 1101_0011_0100_1010 和 3374 = 0000_1101_0010_1110。一旦找到最高阶 1（最左边），它们在第一个差异之前具有匹配的位模式 110_1001，因此距离为 7。

下面是我编写的用于查找此距离度量的 C++ 程序。函数“find_highest_1”和“confer_dist”是相关的。将 T 的#define 更改为任何无符号类型，但请注意，如果您选择无符号字符，那么不重要且写得很糟糕的数字输入代码将无法正常工作，但距离计算将：-P

#include <iostream>
using namespace std;

/* the type chosen for T MUST be unsigned, but any size is fine */
#define T      unsigned short
#define T_BITS (sizeof(T) * 8)

string print_bin(T num) {
    string result = "0b";
    for(int i = T_BITS - 1; i >= 0; i--) {
        if((i + 1) % 4 == 0) result.append("_");
        result.append(to_string((num & (((T)1) << i)) >> i));
    }
    return result;
}

int find_highest_1(T num) {
    int i = -1; // -1 matters here because of how the Confer Distance is found

    if(num != 0) {
        i = 0;
        for(int shift = T_BITS / 2; shift >= 1; shift >>= 1) {
            if(num & (~(T)0) << shift) {
                num >>= shift;
                i += shift;
            }
        }
    }
    return i;
}

int confer_dist(T a, T b) {
    int len_a = find_highest_1(a) + 1;
    int len_b = find_highest_1(b) + 1;
    int min_length;

    min_length = (len_a < len_b) ? len_a : len_b;
    a >>= len_a - min_length;
    b >>= len_b - min_length;

    return min_length - find_highest_1(a ^ b) - 1;
}

int main(int argc, const char * argv[])
{
    T num1, num2;
    cout << "enter two numbers: ";
    cin >> num1 >> num2;

    cout << "num1 = " << print_bin(num1) << endl;
    cout << "num2 = " << print_bin(num2) << endl;

    cout << "Confer dist: " << confer_dist(num1, num2) << endl;
    return 0;
}

我没有对此发表评论来解释它是如何/为什么起作用的，但如果它能让任何人受益，我会很高兴。

于 2014-03-08T04:41:57.907 回答