给定inDigits的基本否定

Question

我有以下问题：给定以base为单位的输入（输入以该base的数字数组的形式给出），将数字的取反记入outDigits中的“ base”的补码符号中。数字的“基数补码”表示法是“二进制补数”的概括：如果我们将（-x）视为基数中的无符号数，并将其加到x，则应该得到0（模数基数^数字大小）。 我无法调用其他函数（甚至是Math.pow）我的测试不断出现错误。我的代码：

public static void baseNegate(int base, int[] inDigits, int[] outDigits) {
        outDigits[0] = 1;
        for (int i = outDigits.length - 1; i >= 0; i--) {
            outDigits[i] += base - (1 + inDigits[i]);
            if (i < outDigits.length - 1) {
                outDigits[i + 1] = outDigits[i] / base;
            }
            outDigits[i] %= base;
        }
    }

我在计算中找不到错误，请提供帮助。我的测试：

------------------------------------ Negate number 365 in base 10 ------------------------------------
Test case have FAILED.
Base:    10
Input number:    [5, 6, 3]
Expected:        [5, 3, 6]
Output:          [5, 0, 0]

-------------------------------- Negate number b1010110011 in base 2 --------------------------------
Test case have FAILED.
Base:    2
Input number:    [1, 1, 0, 0, 1, 1, 0, 1, 0, 1]
Expected:        [1, 0, 1, 1, 0, 0, 1, 0, 1, 0]
Output:          [1, 0, 0, 0, 0, 0, 0, 0, 0, 0]

-------------------------------------- Negate 0x7AF0 in base 16 --------------------------------------
Test case have FAILED.
Base:    16
Input number:    [0, 15, 10, 7]
Expected:        [0, 1, 5, 8]
Output:          [0, 1, 0, 0]

Answer 1

您的问题是，在计算补数时，您似乎试图对补数求反，这使您的解决方案变得复杂。

您可以通过将其分为两个阶段来尝试简化解决方案：

• 首先计算补数。
• 第二将+1添加到计算的补码中。

以下方法是此方法的有效版本：

    public static void baseNegate(int base, int[] inDigits, int[] outDigits) {
        // Compute the complement of the digits
        for (int i = outDigits.length - 1; i >= 0; i--)  
            outDigits[i] = base - (1 + inDigits[i]);

        // Negate the complement by adding +1 to the computed number (collection of digits)
        for (int i = 0; i < outDigits.length; i++) {  
            if (outDigits[i] == base - 1) {
                // Max out digit. Set it to zero and try with the higher order next. 
                outDigits[i] = 0;
            } else {
                // Digit that has room for +1. Finally add the 1 and DONE!
                outDigits[i]++;
                break;
            }
        }
    }
这种方法更清晰，性能更好，并且代码易于说明；但我在代码中添加了注释，以遵循所使用的逻辑。

Complete code on GitHub

希望这会有所帮助。

Answer 2

由于“预期”值表明索引0是最低顺序数字，因此，对于数字123₁₀，该数组将为[3, 2, 1]，即，这些数字与人类期望的顺序相反。 。对于计算机，有意义的是索引i处的值是必须乘以baseⁱ的值。

Answer 3

我认为这附近有问题：