给定 inDigits 的基础否定

Question

我遇到以下问题：给定 base 中的输入（输入作为其在该基数中的数字的数组给出），在 "base's" 中写入数字的否定 - 在 outDigits 中补码。
数字的 "base's complement" 表示法是 "two's complement" 的推广：如果我们将 (-x) 视为基数中的无符号数并将其添加到 x，我们应该得到 0（模数 base^digit-size ). 我无法调用其他函数（甚至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

我认为这里有问题：

if (i < outDigits.length - 1) {
    outDigits[i + 1] = outDigits[i] / base;
}

假设您使用的是以 10 为底数。由于数字只能是 0 到 9，除以 10 意味着此计算的结果始终为 0。我认为您不是故意的。

Answer 2

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

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

首先计算补码。
其次将 +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 3

由于 "expected" 值显示索引 0 是最低位数字，这意味着对于数字 123₁₀ 数组将是 [3, 2, 1]，即数字顺序相反你对人类的期望。对于计算机来说，索引 i 处的值是必须乘以 baseⁱ 的值是有意义的。

这意味着您需要 i 循环向上迭代，而不是向下迭代，因此您可以跟踪结转。否则你的代码工作正常：

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

就个人而言，这样写更有意义，尤其是因为它不依赖于 outDigits 数组预初始化为全 0:

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

为了更好的性能，你不想使用 % 和 /，所以这样的东西可能会更好：

public static void baseNegate(int base, int[] inDigits, int[] outDigits) {
    boolean carry = false;
    for (int i = 0; i < outDigits.length; i++) {
        if (carry) {
            outDigits[i] = base - inDigits[i] - 1;
        } else if (inDigits[i] != 0) {
            outDigits[i] = base - inDigits[i];
            carry = true;
        }
    }
}

测试

所有 3 个都会给出相同的结果：

public static void main(String[] args) {
    test(10, 5,6,3);
    test(2,  1,1,0,0,1,1,0,1,0,1);
    test(16, 0,15,10,7);
    test(8,  0,0,0); // 0 -> 0 (000)
    test(8,  1,0,0); // 1 -> -1 (777)
    test(8,  7,7,3); // 255 -> -255 (104)
    test(8,  0,0,4); // -256 -> -256 (004)
}

static void test(int base, int... inDigits) {
    int[] outDigits = new int[inDigits.length];
    baseNegate(base, inDigits, outDigits);
    System.out.printf("%d: %s -> %s%n", base, Arrays.toString(inDigits),
                                        Arrays.toString(outDigits));
}

输出

10: [5, 6, 3] -> [5, 3, 6]
2: [1, 1, 0, 0, 1, 1, 0, 1, 0, 1] -> [1, 0, 1, 1, 0, 0, 1, 0, 1, 0]
16: [0, 15, 10, 7] -> [0, 1, 5, 8]
8: [0, 0, 0] -> [0, 0, 0]
8: [1, 0, 0] -> [7, 7, 7]
8: [7, 7, 3] -> [1, 0, 4]
8: [0, 0, 4] -> [0, 0, 4]

给定 inDigits 的基础否定

Base Negation given an inDigits

java

algorithm

math

design-patterns

twos-complement