algorithm - 2s补码一般形式

Question

假设我有一个系统，其中的整数在 mod n 中工作。所以我的整数加一到 n-1 实际上等于零。

进一步假设您将一个数的二进制补码定义为与自身相加等于零的数。即:

x + C(x) = 0   (here C(x) is the twos compliment of x)

通常我应该怎么做才能得到 x 的补码？

真正的问题:

如果 x 是一个二进制数，我可以将 x 的所有位取反，然后对该数加一。

如果 x 是一个三进制数，这会变得有点棘手。这个问题是它不匹配偶数位，所以你会尝试翻转 2/3 的位或其他东西，我不知道这在物理上意味着什么。

所以我的问题是:我怎样才能对多个任意基数取二补？

Answer 1

我假设您正在为一些整数 s > 0 处理基础 s 并且您正在尝试以 s^(n+ 1) 对于一些固定整数 n > 0。换句话说，最多使用 n+1 个位置(或数字)。

因此，您将此系统中的整数表示为序列 [xn ... x0]，其中每个 xi 都是 0 和s-1。例如，如果 s=3 和 n=4，表示 [01201] 将对应于十进制数 0*3 ^4 + 1*3^3 + 2*3^2 + 0*3^1 + 1*3^0 = 27 + 18 + 1 = 46。

一般来说，上述表示的十进制值为:

x = xn*s^n + ... + x0*s^0

现在，您的问题在于找到 -x 模 s^(n+1) 的表示(记住我们只能使用 s+1 “数字”。

定义，对于每个数字xi，它对s的补是

c(xi) = s - 1 - xi

请注意，在二进制情况下，当s=2 时，2 的补码符合相同的定义。还要注意

xi + c(xi) = s - 1                                          eq(1)

现在让我在这里使用一个更简单的符号并调用 yi = c(xi)。然后顺序

y = [yn ... y0]

是我们可以称之为对 x 的 s 的补充。它也是 -x - 1 模 s^(n+1) 的表示，因此要获得 -x 您只需添加1 到 y。例如，在 x=[01201] 的情况下，我们将得到 y=[21021]，因为每个数字的总和为 3-1=2位置。

原因很简单:

[yn ... y0] + [xn ... x0]
            = yn*s^n + ... + y0*s^0 + xn*s^n + ... + x0*s^n
            = (yn+xn)*s^n + ... + (y0+x0)*s^0
            = (s-1)*sˆn + ... + (s-1)*s^0              ; by eq(2)
            = s^(n+1) + ... + sˆ1 - (s^n + ... + s^0)
            = s^(n+1) - 1
            = -1  modulo s^(n+1)

因此，事情的工作方式与 s=2 和模 2^32(32 位)时的工作方式类似。从这个意义上说，二进制情况没有什么特别之处。