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 为基数工作，并且您正在尝试对某个固定整数 n > 0 以模 s^(n+1) 表示数量.换句话说，最多使用 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 "digits".

定义，对于每个数字 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 位）时的工作方式类似。从这个意义上说，二进制情况没有什么特别之处。

2s补码一般形式

2s compliment general form

language-agnostic

algorithm

bit-manipulation