2

文字列 s のフィンガープリント f(s) = (S[1]r^m-1) xor (S[2]r^m-2) xor....(xor S[n]r^0 )) mod (2^32) let s には a と b (それぞれ 0,1) のみが含まれます。

xor ではなく加算であれば簡単です。(a + b)mod m = ((a mod m) + (b mod m)) mod m という規則を使用して解決できますが、ここでは当てはまりません。したがって、整数オーバーフローに直面する可能性があるため、たとえば r^m-1 を計算できないことに注意してください。

4

4 に答える 4

2

懸念事項がオーバーフローである場合は、BigInteger十分なメモリがあると仮定して、これを 使用することをお勧めします。

javadoc :

算術演算のセマンティクスは、Java 言語仕様で定義されているように、Java の整数算術演算子のセマンティクスを正確に模倣しています。たとえば、ゼロによる除算は ArithmeticException をスローし、負の値を正の値で除算すると、負 (またはゼロ) の剰余が生成されます。オーバーフローに関する Spec の詳細はすべて無視されます。BigInteger は、操作の結果を収容するために必要な大きさになるからです。

SO説明オーバーフロー

BigInteger は実際には型ではありません。クラスです。これは、int と同じ機能を提供するように設計されたラッパー クラスですが、オーバーフローを心配することなく、必要なだけ大きな数値を使用できます。

型は単純に数バイト (正確な量は型によって異なります) のメモリであるため、オーバーフローが発生します。その少量のメモリがオーバーフローすると、数値もオーバーフローします。

特にそうするように設計されていない限り (またはリソースが不足している場合)、クラスが「オーバーフロー」することはありません。クラスは、含まれるすべてのものに対して十分なメモリを使用して定義されます。ほとんどの場合、他のクラスまたは他のデータ構造への参照になります。

于 2013-04-29T19:01:23.173 に答える
0

待ってください... m が単純に S の長さである場合、すべてがより単純になります。

int re = 1;
int sig = 0;
for (int i=m-1; i>=0; --m) {
    if (s[i] != 0)
        sig ^= re;
    re = (re*r) & 0xffffffff;
}

これは私には単純すぎるように思えます。あなたは正しい表現を持っていると確信していますか？

（私の元の答え：

まだ持っていない場合は、整数指数関数から始めます。

/**
 * Return x^e, mod 2^32
 */
unsigned int
iExp(unsigned int x, unsigned int e)
{
    unsigned int rval = 1;
    while (e > 0) {
        if ((e & 1) != 0)
            rval *= x;
        x *= x;
        e >>= 1;
    }
    return rval & 0xffffffff;
}

S が 0 または 1 の値の配列である場合、それは実際には部分式の残りの「使用」/「使用しない」フラグです。

// I've taken the liberty of indexing S starting at 0 instead of 1
// compute f(s) = (S[0]r^m-1) xor (S[1]r^m-2) xor....(xor S[m-1]r^0)) mod (2^32)

int rval = 0;
for (x : S) {
    --m;
    if (x != 0)
        rval ^= iExpr(r, m);
}

私はこれをテストしていませんが (テスト ベクトルはありません)、これでうまくいくはずです。

于 2013-04-30T16:01:57.383 に答える