Inverse of a bit conversion equation

Question

I'm reading a computer science book that gives several functions, in the mathematical sense. There are two that are the basis of this question.

These are equations used to convert a number represented in base ten to a bit representation using two's complement and back.

One function makes the conversion from binary two's complement to decimal, $B2T_w$, defined as $$B2T_w(x) = -x_{w-1}2^{w-1} + \sum_{i=0}^{w-2} x_i2^i$$ where x is a vector of length w.

It then goes to define another function, $T2B_w$ as the inverse of $B2T_w$; which it does not define using mathematical notation.

I understand how to convert between a two's complement bit representation of a number to it's decimal representation, but for the sake of understanding I'd like to know how to derive the inverse of $B2T_w$

How do I find $B2T_w^{-1}$?

Answer 1

Your book's terminology is a bit misleading. From a mathematical viewpoint, it's important to note that $B2T_w$ does not convert from a two's complement representation to a decimal representation of a number.

It simply converts from a two's complement representation of a number to the number it represents.

"2017" (in decimal notation) is neither more, nor less, a 'representation' of a particular number than "011111100001" is (in two's complement notation using $12$ bits). It's not like the number is "truly" 2017, instead of 011111100001; they are just two different names for the same abstract thing.

That being said, I think what you are asking is, given that "abstract thing" (e.g., whose name, in decimal notation, is "2017"), and given some $n$, how do we calculate what $x_{n}$ is in the $w$-bit two's complement notation for that number?

Well, we aren't going to get something particularly clean looking, but here's an approach that may satisfy via a recurrence, and is reasonably close to how one might generate the two's complement "in the usual way"...

Assume the number in question is $X$. First, $n = w-1$ is a bit of a special case:

$$x_{w-1} = \begin{array}{lr} 0 & \text{if } X\geq 0\\ 1 & \text{if } X < 0 \end{array}$$

So given that, and replacing $B2T_w(x)$ with $X$ and rearranging a term, we can adjust the formula you gave as:

$$X + x_{w-1}2^{w-1} = \sum_{i=0}^{w-2}x_i 2^{i}$$

For $0 \leq n < w-1$, then

$$X + x_{w-1}2^{w-1} = \sum_{i=0}^{n-1}x_i 2^{i} + x_n 2^n + \sum_{j=n+1}^{w-2}x_j 2^{j}$$

which we can juggle around to read as...

$$x_n 2^n = (X - \sum_{i=0}^{n-1}x_i 2^{i}) + x_{w-1}2^{w-1} - \sum_{j=n+1}^{w-2}x_j 2^{j}$$

Note that $2^{n+1}$ divides $x_n 2^n$ if and only if $x_n = 0$. Now $2^{n+1}$ always divides $2^{w-1}$; and $2^{n+1}$ always divides $\sum_{j=n+1}^{w-2}x_j 2^{j}$. Therefore, for $0 \leq n < w-1$,

$$x_{n} = \begin{array}{lr} 0 & \text{if } {2^{n+1}} \text{ divides } {(X -\sum_{i=0}^{n-1}{x_i 2^i})}\\ 1 & \text{otherwise} \end{array}$$

gives us a recurrence: $x_0$ is $0$ iff $X$ is even, $x_1$ is $0$ iff $(X -x_0)/2$ is even, $x_2$ is $0$ iff $(X- (2x_1 + x_0))/4$ is even; and so on and so forth.

Answer 2

The encoding of a signed-magnitude integer as an $n$-bit two's complement numeral is best described as the composition of two functions. The first encodes the absolute value in base $2$:

$$ b(x) = \sum_{0 \leq i < n-1} (\lfloor |x| / 2^i\rfloor \bmod 2) 2^i \enspace. $$

If $x / 2^{n-1} \neq 0$, overflow occurs unless $x = -2^{n-1}$. The second function takes care of the sign.

$$ s(x) = \text{ if } x \geq 0 \text{ then } b(x) \text{ else } 2^n - b(x) \enspace. $$

Note that while $2^n$ clearly requires $n+1$ bits, the most significant bit of the subtraction is guaranteed to be $0$.

In practice, the operations are carried out in a related manner, but not following the above "instructions" verbatim. (I understand you already know that.) In particular, no operation needs $n+1$ bits, and no integer divisions or remainders are required.