2

我有字符串 s 的指纹， f(s) = (S[1]r^m-1) xor (S[2]r^m-2) xor....(xor S[n]r^0 )) mod (2^32) 让 s 只包含 a 和 b （分别为 0,1）。

如果它是加法而不是异或，那将很容易。我们可以使用以下规则来解决它：(a + b)mod m = ((a mod m) + (b mod m)) mod m，但这里不是这样。因此，任何想法都请记住，我无法计算例如 r^m-1，因为我可能面临整数溢出。

4

4 回答 4

2

如果担心溢出，我建议使用BigInteger它不会溢出假设你有足够的内存：

文档 ：

算术运算的语义完全模仿 Java 的整数算术运算符，如 Java 语言规范中所定义。例如，除以零会引发 ArithmeticException，而负数除以正数会产生负数（或零）余数。规范中关于溢出的所有细节都被忽略了，因为 BigInteger 被制作得尽可能大以适应操作的结果。

所以解释溢出

BigInteger 并不是真正的类型。这是一堂课。它是一个包装类，旨在为您提供与 int 相同的功能，但允许您使用任意大小的数字而无需担心溢出。

类型确实会溢出，因为它们只是内存的几个字节（确切数量取决于类型），一旦少量内存溢出，数字也会溢出。

没有类“溢出”，除非它是专门设计的（或者如果你用完了资源）。一个类被定义为它包含的所有内容都有足够的内存，这主要是对其他类或其他数据结构的引用。

于 2013-04-29T19:01:23.173 回答
1

溢出不是问题，因为：

  • XOR 是 bitwuse 操作（高位的存在/不存在确实会影响结果）
  • mod 2^32屏蔽高位的最终动作

只需使用 along来保存您的结果（64 位，因此第 31 位不会导致符号问题）。

于 2013-04-29T19:11:27.350 回答
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 回答
0

JavaBigInteger类不支持提升到类型的指数BigInteger。您可以做的是实现一种算法来自己计算幂，使用Exponentiation by Squaring。这些通常以递归算法的形式出现，该算法将计算您的功率，而实际上不会将数字提高到超过2（因此平方）的指数。

然而， JavaBigInteger类确实处理了溢出问题。

于 2013-04-29T20:40:56.280 回答