2

2 つのバイナリ文字列のハミング距離が異なるビットの数であることは誰もが知っています。一方、1110 と 1101 の 2 つのバイナリ文字列の場合、それらの類似性を最上位ビットから同じビットの数で説明したい場合。(この例では、左から右に、2 つのビットが異なるまでビットをカウントし、結果は 2 になります。) この種の類似性は定義されているか、正式な名前がありますか?

4

1 に答える 1

0

私は私の大学の他の学部のいくつかに相談しましたが、私たちはこれについて聞いたことがないことに同意します:-)

ただし、この種の問題は常に興味深いものであり、特に以前に見たことがない場合は特にそうです... そのため、解決策に取り組んでいます。

明確化のポイントとして、私はあなたの目標を、同等のストレージの2つの数値のバイナリ値の間の距離を見つけることだと考えています（これを私はConfer距離と呼びます...ねえ、なぜですか?...私はOR Mapperのコメントが大好きでした）。長さ (2 つの unsigned long など) であり、先頭の 0 はすべて無視しています。たとえば、unsigned short 54090 対 3374... 54090 = 1101_0011_0100_1010 および 3374 = 0000_1101_0010_1110 です。最高次数 1 (左端) を見つけると、最初の不一致の前にビット パターン 110_1001 が一致するため、距離は 7 になります。

以下は、この距離メトリックを見つけるために作成した C++ プログラムです。関数 "find_highest_1" と "confer_dist" が適切です。T の #define を unsigned 型に変更します。ただし、unsigned char を選択すると、重要でなく惨めに書かれた数値入力コードが期待どおりに機能しないことに注意してください。ただし、距離の計算は次のようになります :-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 に答える