反向溢出

Question

int num = -340721550;
int multi =  -214882771;
int result = num * multi; // = 10

如果我知道 multi 和 result，我怎样才能在不强制使用的情况下倒退到 num？

或者提高我的暴力破解方法的速度

public static int multiInverse(int multi, int result){
    for (int i = Integer.MIN_VALUE; i <= Integer.MAX_VALUE; i++){
        if (multi * i == result){
            return i;
        }
    }
    return -1;
}

Answer 1

简单地说，你的问题是关于求解以下方程式：

x * b = a，其中 a 和 b 已知。

通常，这非常简单，因为您可以简单地执行以下操作：

x = a / b

但是，由于我们使用的是整数，因此这仅在 a 是 b 的倍数时才给出正确的解决方案。例如，如果 b = 2 且 a = 4.

如果 a 不是 b 的倍数，那么我们知道 a*x 导致整数溢出。

现在，想想除以 b 是什么意思。您实际上在做的是应用 b 的倒数。毕竟，b / b = 1。除以 b，你是 'undoing b'。

所以我们必须做的是找到解决方案，找到我们必须乘以 b 的整数，以获得导致 1 的溢出。

我将举一个小例子来说明这是如何工作的。

假设我们有一个范围为 0 到 8 的数据类型，那么对于 0 到 8 范围之外的任何值它都会溢出。

在这种情况下，以下内容为真：3 * 3 == 1。 (因为9溢出到1)

现在假设我们有 3 * 5 == 7（因为 15 溢出到 7）。

你想要的是通过了解 5 和 7 回到 3。更正式地说，你想在模 8 中找到 5x = 7 的 x。

模8中，5的倒数为5，因为5*5=25，溢出为1

所以你的解是7 * 5 = 3（因为35溢出到3）

但是，要找到一种简单的方法来求有符号 java 整数的倒数并不容易。如果你能找到它，因为不是每个整数都保证有一个倒数。

Answer 2

在一个, the problem can be attacked through calculating the inverse modulo 2^32 of the known divisor. java.math.BigInteger has a modInverse方法中指出可以使用

正如答案中还指出的那样，相对于模基不是素数的数字没有倒数。在以二为底数的幂的情况下，这意味着偶数没有倒数。我通过将除数和乘积减半直到除数为奇数来解决这个问题。

不幸的是，我的方法只能找到一个 result 使得 divisor * result == product 在 int 算术中。这样的数字可能不止一个，所以它不一定是你开始的那个。

  private static final BigInteger modulo = BigInteger.ONE.shiftLeft(32);

  public static int unoverflowDivide(int product, int divisor) {
    if (divisor == 0)
        throw new IllegalArgumentException("No solution");
    while((divisor & 1) == 0){
      if ((product & 1) == 1)
          throw new IllegalArgumentException("No solution"); 
      divisor >>= 1;
      product >>= 1;
    }
    BigInteger bigDivisor = BigInteger.valueOf(divisor);
    BigInteger bigProduct = BigInteger.valueOf(product);
    BigInteger bigInverse = bigDivisor.modInverse(modulo);
    BigInteger bigResult = bigInverse.multiply(bigProduct);
    return bigResult.intValue();
  }

反向溢出

Reverse int overflow

java

int

reverse

integer

overflow