2.5  Signed Integer Formats

For any given positive integer $ w$, the $ w$-bit signed integer format is the mapping of the set of $ 2^w$ integers $ x$ in the range $ -2^{w-1} \leq x < 2^{w-1}$ to the set of bit vectors of width $ w$ defined by

$\displaystyle x \longmapsto x[w-1:0].
$

This is also know as the $ w$-bit twos' complement encoding of $ x$.

With respect to this mapping, the most significant bit of the encoding of $ x$,

$\displaystyle x[w-1:0][w-1] = x[w-1],
$

is 0 if $ 0 \leq x < 2^{w-1}$ (by Lemma 2.3.9) and 1 if $ -2^{w-1} \leq x < 0$ (by Lemma 2.3.10), and is therefore known as the sign bit of the encoding.

The integer represented by a given encoding is computed by the following function, as affirmed by Lemma 2.5.1 below:

Definition 2.5.1   (si) If $ x$ is a $ w$-bit vector, where $ w \in \mathbb{N}$, then

$\displaystyle \mathit{si}(r, n) = \left\{\begin{array}{ll}
r - 2^n & \mbox{if $r[n-1] = 1$}\\
x & \mbox{if $r[n-1] = 0$.}\end{array}\right.$

  (si-bits) Let $ n \in \mathbb{N}$ and $ x \in \mathbb{Z}$. If $ -2^{n-1} \leq x < 2^{n-1}$, then

$\displaystyle \mathit{si}(x[n-1:0], n) = x.
$

PROOF: If $ 0 \leq x < 2^{n-1}$, then $ x[n-1:0] = x$ by Lemma 2.2.5, and $ x[n-1] = 0$ by Lemma 2.3.9. Thus,

$\displaystyle \mathit{si}(x[n-1:0], n) = \mathit{si}(x, n) = x.
$

If $ -2^{n-1} \leq x < 0$, then $ x[n-1:0] = x + 2^n$ by Lemma 2.2.6, and $ (x + 2^n)[n-1] = 1$ by Lemma 2.3.23. Thus,

$\displaystyle \mathit{si}(w, x[w-1:0]) = \mathit{si}(w, x + 2^w) = (x + 2^w) - 2^w = x. $

Lemma 2.5.2   (bits-si) If $ n \in \mathbb{N}$, $ r\in \mathbb{N}$, $ i \in \mathbb{N}$, and $ j \in \mathbb{N}$ with $ j \leq i < n$, then

$\displaystyle \mathit{si}(r, n)[i:j] = r[i:j].
$

An $ n$-bit integer encoding is converted to an $ m$-bit encoding, where $ m>n$, by sign extension:

Definition 2.5.2   (sextend) Let $ r$ be an $ n$-bit vector, where $ n \in \mathbb{N}$, and let $ m \in \mathbb{N}$, $ m \geq n$. Then

$\displaystyle \mathit{sextend}(m, n, r) = \mathit{si}(r, n)[m-1:0].
$

The next result establishes that an integer encoding and any sign extension of it represent the same integer value.

  (si-sextend) Let $ r$ be an $ n$-bit vector, where $ n \in \mathbb{N}$, and let $ m \in \mathbb{N}$, $ m \geq n$. Then

$\displaystyle \mathit{si}(\mathit{sextend}(m, n, r), m) = \mathit{si}(r, n).
$

PROOF: First suppose $ r[n-1] = 0$. Then $ \mathit{si}(r, n) = r$ and by Lemma 2.3.23, $ 0 \leq r < 2^{n-1}$. By Lemma 2.2.5,

$\displaystyle \mathit{sextend}(m, n, r) = \mathit{si}(r, n)[m-1:0] = r[m-1:0] = r,
$

and since Lemma 2.3.9 implies $ r[m-1] = 0$,

$\displaystyle \mathit{si}(\mathit{sextend}(m, n, x), m) = \mathit{si}(r, m) = r = \mathit{si}(r, n).
$

Now suppose $ r[n-1] = 1$. Then by Lemma 2.3.9, $ 2^{n-1} \leq r < 2^n$. Now $ \mathit{si}(r, n) = r - 2^n$, where $ -2^{m-1} \leq -2^{n-1} \leq r - 2^n < 0$. By Lemma 2.2.6,

$\displaystyle \mathit{sextend}(m, n, r) = \mathit{si}(r, n)[m-1:0] = (r - 2^n)[m-1:0] = r - 2^n + 2^m.
$

But since $ 2^{m-1} \leq r - 2^n + 2^m < 2^m$. Lemma 2.3.23 implies $ (r - 2^n + 2^m)[m-1] = 1$, and hence

$\displaystyle \mathit{si}(\mathit{sextend}(m, n, r), m) = \mathit{si}(r - 2^n + 2^m, m)
= r - 2^n + 2^m - 2^m - r - 2^n = \mathit{si}(rl, n). $

  (si-approx) Let $ X \in \mathbb{Z}$, $ Y \in \mathbb{Z}$, and $ n \in \mathbb{Z}$, with $ n > 0$. If $ \vert\mathit{si}(X \bmod 2^n,n)\vert < 2^{n-1} - \vert X-Y\vert$, then

$\displaystyle \mathit{si}(X \bmod 2^n,n) - \mathit{si}(Y \bmod 2^n,n) = X - Y.
$

PROOF: Let $ \bar{X} = X \bmod 2^n$, $ \bar{Y} = Y \bmod 2^n$, and $ k = \vert X-Y\vert$.



Case 1: $ \left\lfloor \frac{X}{2^n}\right\rfloor = \left\lfloor \frac{Y}{2^n}\right\rfloor$.

In this case, $ \bar{X} - \bar{Y} = X - Y$.

Suppose $ \bar{X} \leq \bar{Y}$. If $ \bar{X} \geq 2^{n-1}$, then $ \bar{Y} \geq 2^{n-1}$ and

$\displaystyle \mathit{si}(\bar{X},n) - \mathit{si}(\bar{Y},n) = (\bar{X} - 2^n) - (\bar{Y} - 2^n) = \bar{X} - \bar{Y} = X - Y,
$

but if $ \bar{X} < 2^{n-1}$, then $ \bar{X} = \mathit{si}(\bar{X},n) < 2^{n-1} - k$, which implies $ \bar{Y} < 2^{n-1}$ and

$\displaystyle \mathit{si}(\bar{X},n) - \mathit{si}(\bar{Y},n) = \bar{X} - \bar{Y} = X - Y.
$

On the other hand, suppose $ \bar{X} > \bar{Y}$. If $ \bar{X} < 2^{n-1}$, then $ \bar{Y} < 2^{n-1}$ and

$\displaystyle \mathit{si}(\bar{X},n) - \mathit{si}(\bar{Y},n) = \bar{X} - \bar{Y} = X - Y,
$

but if $ \bar{X} \geq 2^{n-1}$, then $ \mathit{si}(\bar{X},n) = \bar{X} - 2^n$, and since $ \mathit{si}(\bar{X},n) > -2^{n-1} + k$, $ \bar{X} > 2^{n-1} + k$, which implies $ \bar{Y} > 2^{n-1}$ and

$\displaystyle \mathit{si}(\bar{X},n) - \mathit{si}(\bar{Y},n) = (\bar{X} - 2^n) - (\bar{Y} - 2^n) = \bar{X} - \bar{Y} = X - Y.
$

Case 2: $ \left\lfloor \frac{X}{2^n}\right\rfloor \neq \left\lfloor \frac{Y}{2^n}\right\rfloor$.

Suppose $ X < Y$. Let $ m = \left\lfloor \frac{X}{2^n}\right\rfloor$. Then

$\displaystyle 2^nm \leq X < 2^n(m+1) \leq Y < X + 2^{n-1} < 2^n(m+2).
$

Thus, $ \bar{X} = X - 2^nm$ and

$\displaystyle \bar{Y} = Y - 2^n(m+1) = k + X - 2^n(m+1) = k + (\bar{X}+2^nm) - 2^n(m+1) = k - 2^n + \bar{X} < k < 2^{n-1}.
$

But then

$\displaystyle \bar{X} = \bar{Y} + 2^n - k \geq 2^n - k > 2^{n-1}
$

and

$\displaystyle \mathit{si}(\bar{X},n) - \mathit{si}(\bar{Y},n) = \bar{X} - 2^n - \bar{Y} = (\bar{Y} + 2^n - k) - 2^n - \bar{Y}
= -k = X - Y.
$

The case $ X>Y$ is similar. 

David Russinoff 2017-08-01