2s称赞一般形式 [英] 2s compliment general form

问题描述

假设我有一个系统，该系统具有在mod n 中工作的整数。因此，用我的整数将 n-1 加一实际上等于零。

Suppose I have a system that has integers that work in mod n. So with my integers adding one to n-1 is actually equal to zero.

进一步假设您定义了一个数字的二进制补码是要加上的数字等于零。即：

Suppose further that you define the twos compliment of a number to be the number when added to itself is equal to zero. That is:

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

一般而言，我应该怎么做才能得到x的双补？

What in general should I do to get the twos compliment of x?

真正的问题：

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

If x is a number in binary I could just invert all of the the bits of x and then add one to that number.

如果x是一个三进制数，这将变得有些棘手。问题在于它与偶数位数不匹配，因此您将尝试翻转2/3位数或其他内容，但我对物理意义不了解。

This gets a little trickier if x is say a trinary number. The problem with this is that it does not match up to an even number of bits, so you would be trying to flip 2/3 of a bit or something, which I don't have any clue what would mean physically.

所以我的问题是：我该如何接受两个任意基数的互补？

So my question is this: How can I take the two's compliment of a number of arbitrary base?

推荐答案

我会假设您正在基于 s 的某个整数 s> 0 ，而您正尝试对某些固定整数 n>以模数 s ^（n + 1）表示数量。 0 。换句话说，最多使用 n + 1 个位（或数字）。

I will assume that you are working on base s for some integer s > 0 and that you are trying to express quantities modulo s^(n+1) for some fixed integer n > 0. In other words using at most n+1 places (or digits).

因此，您在此表示整数系统作为序列 [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 。

So, you represent integers in this system as sequences [xn ... x0] where every xi is a digit between 0 and s-1. For example, if s=3 and n=4, the representation [01201] would correspond to the decimal number 0*3^4 + 1*3^3 + 2*3^2 + 0*3^1 + 1*3^0 = 27 + 18 + 1 = 46.

通常来说，上述表示形式的十进制值为：

Generally speaking the decimal value of the representation above would be:

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

现在，您的问题是找到 -x 模 s ^（n + 1）（请记住，我们只能使用 s + 1 数字。

Now, your problem consists in finding the representation of -x modulo s^(n+1) (remember that we only can use s+1 "digits".

定义，对于每个数字 xi 其补语与 s 一样

Define, for every digit xi its complement to s as being

c(xi) = s - 1 - xi

请注意，在二进制情况下，当 s = 2 时， 2 的补码与

Note that in the binary case, when s=2, the complemento to 2 conforms the same definition. Also notice that

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

现在让我在这里使用一个更简单的表示法，然后调用 yi = c（xi）。然后序列

Now let me use a simpler notation here and call yi = c(xi). Then the sequence

y = [yn ... y0]

是我们所说的 x的 s 的补语 。它也是 -x-1 模 s ^（n + 1）的表示形式，因此获得 -x ，只需将 1 添加到 y 。例如，在 x = [01201] 的情况下，我们会有 y = [21021] ，因为数字总和 3-1 = 2 每个位置。

is what we could call the complement to s of x. It is also the representation of -x - 1 modulo s^(n+1) and therefore to obtain -x you only have to add 1 to y. For example in the case x=[01201] we would have y=[21021] because the digits sum 3-1=2 at each position.

原因很简单：

[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位）取模。从这个意义上说，二进制情况没有什么特别的。

So, things work similarly as how they work when s=2 and, say, modulo 2^32 (32 bits). In this sense there is nothing special about the binary case.

这篇关于2s称赞一般形式的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！