java - 蛮力基础256乘法

Question

在我的计算机科学课上，我学习了一种将两个相同长度的二进制数相乘的算法。我被指示将它转换为以 256 为基数的乘法并用 Java 实现它，但我似乎无法获得正确的输出，而且我不知道我遗漏了什么。

给我的算法:

MULTIPLY(U,V)
  define array W[1..2n] for k = 1 to 2n
  W[k] = 0 // Initialize result
  for j=1 to n
    c = 0 // Carry bit
    for i = 1 to n
      t = U[i]V[ j] + W [i+j] + c
      W[i+j] = t mod 2 // lower bit 
      c= 𝑡/2 // upper bit
    k = i+j
    while k ≤ 2n and c ≠ 0 // propagate carry bit
      t=W[k]+ c
      W[k]=tmod2 // lower bit 
      c=𝑡/2 // upper bit 
      k++
  return W

我的尝试:

private static Byte[] bruteMultiply(Byte[] U, Byte[] V) {
    Byte[] W = new Byte[U.length * 2];

    for (int k = 0; k < W.length; k++) {
        W[k] = 0;
    }

    for (int j = 0; j < U.length; j++) {
        int c = 0;

        for (int i = 0; i < U.length; i++) {
            int t = (U[i] & 0xFF) * (V[j] & 0xFF) + (W[i + j] & 0xFF) + c;
            W[i + j] = (byte) (t % 256);
            c = t / 256;
        }
        int k = U.length + j;
        while ((k < 2 * U.length) && (c != 0)) {
            int t = (W[k] & 0xFF) + c;
            W[k] = (byte) (t % 256);
            c = t / 256;
            k++;
        }
    }

    return W;
}

当我向它提供数组 [197, 33, 151, 79] 和 [248, 164, 50, 235] 时，我得到 [216 , 234, 132, 91, 206, 122, 31, 73] 当 [191, 118, 251, 78, 251, 255, 83, 133] 是预期的。

我不知道我错过了什么或哪里出错了。任何建议或指示都会有所帮助!

Answer 1

提示:尝试将 [79, 151,33, 197] 和 [235, 50, 164, 248] 与您的代码相乘，并将结果与目标结果。

我相信您是时候了解 endianness 了.一般来说，您的实现看起来不错，但您使用的字节顺序与示例中的不同。一旦你修复它，我想你会得到正确的答案。

附言我认为没有充分的理由使用 Byte而不是数组中的 byte 。这是您可能应该了解的另一个棘手的区别。