algorithm - 以 4 为底表示的过量 (-1)

Question

在过去的几天里，我一直在努力解决这个问题，但我想不出解决它的方法。所以，这里是:

给定基数 4(即 0、1、2、3 作为数字的数字)，找出任何负整数或正整数的基数 4 表示中的多余部分 (-1)。 例子: -6 = (-1)22 相反，(-1)22 超出基数 4 的 (-1) = 2 * 4^0 + 2 * 4^1 + (-1) * 4^2 = 2 + 8 - 16 = 10 - 16 = -6以 10 为基数

27 = 2(-1)(-1) 相反，2(-1)(-1) = (-1) * 4^0 + (-1) * 4^1 + 2 * 4^2 = -1 - 4 + 32 = 27

我确实提出了一些正数算法，但没有一个算法适用于所有负数，所以它们被扔进了垃圾桶。

有人能给我一些线索吗？谢谢!

----------------

编辑:我将尝试以不会引起任何混淆的方式重新表述这个问题。

考虑从每个数字减去 1 得到的基数，称为基数 4 的余量 -(-1)。在这个基数中，任何数字都可以用数字 -1、0、1、2 表示。因此，问题要求一种算法，该算法将任何整数作为输入，并将该给定数字的表示形式作为输出。

例子:

十进制 -6 = -1 2 2 以 4 为底的余数 -(-1)。

为了验证这一点，我们采用表示 -1 -1 2 并将其转换为十进制数，从最右边的数字开始并使用通用的以 n 为基数到 10 为底数的算法，如下所示:

数字 = 2 * 4^0 + 2 * 4^1 + (-1) * 4^2 = 2 + 4 - 16 = -6

Answer 1

我不知道“quaterit”是否是表示此表示中基数的正确词，但无论如何我都会使用它。

既然你说你已经有了正数算法，我会尝试将负数作为输入并编写一些使用你已有的东西的东西。下面的代码不太有效，但我会在最后解释原因。

int[] BaseFourExcessForNegativeNumbers(int x) {
    int powerOfFour = 1;
    while (-powerOfFour > x) {
        powerOfFour *= 4;
    }
    int firstQuaterit = -1;
    int remainder = x + powerOfFour;
    int[] otherQuaterits;
    if (remainder >= 0) {
        otherQuaterits = BaseFourExcessForPositiveNumbers(remainder);
    } else {
        otherQuaterits = BaseFourExcessForNegativeNumbers(remainder);
    }
    int[] result = new int[otherQuaterits.Length + 1];
    result[0] = firstQuaterit;
    for (int index = 0; index < otherQuaterits.Length; ++index) {
        result[index + 1] = otherQuaterits[index];
    }
    return result;
}

这里的想法是，在此表示中，每个负数 x 都将以 (-1) 开头。如果 (-1) 在 4^n 位置，我们想知道如何表示 x - (-1)*4^n 查看如何表示其余数字。

我写的代码不起作用的原因是它没有考虑到第二个四元组是 0 的可能性。如果发生这种情况，我的代码将生成的数组将缺少那个 0。事实上，如果 BaseFourExcessForPositiveNumbers 以相同的方式编写，则生成的数组将缺少 every 0，但否则将是正确的。一种解决方法是跟踪第一个四元组所处的位置，然后将数组设为该大小，并从后往前填充它。