PreviousContentsNext

D Integer Arithmetic

Computers operate on integers \(x\in \mathbb {Z}\) using modular arithmetic. Basically, given an unsigned integer

\[ x\in \mathbb {U}_n=\{0,1,\ldots ,2^n-1\} \]

we have

\[ x=\sum _{i=0}^{n-1}x_i2^i \]

The smallest possible value is when

\[ x_i=0\quad \forall i \qquad \Longrightarrow \qquad x=0 \]

and the largest is when

\[ x_i=1\quad \forall i \qquad \Longrightarrow \qquad x=2^n-1 \]

Let

\[ x=\sum _{i=0}^{n-1}x_i2^i, \qquad y=\sum _{i=0}^{n-1}y_i2^i \]

For a given \(x\), the remaining distance to the maximum value is

\[ 2^n-1-x \]

Thus, for \(x+y\), we experience unsigned overflow if

\[ y>2^n-1-x \]

or if you will

\[ x+y>2^n-1 \]

PIC

When this event happens, computers signal it using the carry flag \(C\):

\[ C=0 \quad \Longrightarrow \quad \text {no unsigned overflow}, \]
\[ C=1 \quad \Longrightarrow \quad \text {unsigned overflow} \]

The inverse of \(y\), i.e. \(-y\), in \(\mathbb {Z}_{2^n}\) is

\[ -y=2^n-y, \]

since

\[ y+(2^n-y)=0\pmod {2^n} \]

Thus computers can compute

\[ x-y=x+(2^n-y) \]

If

\[ x+(2^n-y)\geq 2^n \]

a carry is generated. In particular,

\[ x+2^n-y\geq 2^n \iff x\geq y \]

Thus we can compare two unsigned integers \(x\) and \(y\) using subtraction, if

\[ x-y=0 \]

then

\[ Z=1 \qquad \Longrightarrow \qquad x=y \]

Otherwise, the carry/borrow information tells us whether

\[ x>y \qquad \text {or}\qquad x<y \]

Now consider signed integers

\[ x=-x_{n-1}2^{n-1} +\sum _{i=0}^{n-2}x_i2^i \]

so

\[ x\in \left [ -2^{n-1}, 2^{n-1}-1 \right ] \]

For \(x>0\) and \(y>0\), \(x+y\) experiences signed overflow if

\[ x+y>2^{n-1}-1 \]

or for a given \(x\),

\[ y>2^{n-1}-1-x \]

For example,

\[ x+(2^{n-1}-x)=2^{n-1} \]

But \(2^{n-1}\) is not representable as a positive signed integer. Its \(n\)-bit representation corresponds to

\[ -2^{n-1} \]

so we went from a large positive value to a very small negative value (signed overflow).

Computers usually signal the occurence of this event using an overflow flag \(V\). For example,

\[ \operatorname {MSB}(x)=\operatorname {MSB}(y)=0, \qquad \operatorname {MSB}(x+y)=1 \]

implies

\[ V=1 \]

Similarly, if

\[ x<0,\qquad y<0 \]

the addition of two very small negative values can overflow to large positive values. Signed overflow occurs if

\[ x+y<-2^{n-1} \]

For example, if

\[ x=-1 \]

then any \(y\) such that

\[ -1+y<-2^{n-1} \]

will lead to signed overflow. In particular,

\[ -1+(-2^{n-1}) = -2^{n-1}-1 \]

Modulo \(2^n\),

\[ -2^{n-1}-1 \equiv 2^{n-1}-1 \pmod {2^n}. \]

Thus a negative result wraps to the largest positive signed value.

PIC

Computers detect this case when

\[ \operatorname {MSB}(x) = \operatorname {MSB}(y) = 1 \]

and

\[ \operatorname {MSB}(x+y)=0 \]

giving

\[ V=1 \]

Now consider

\[ x-y \]

First, we can only experience signed overflow in subtraction when

\[ \operatorname {sign}(x)\neq \operatorname {sign}(y) \]

If

\[ x>0,\qquad y>0 \]

then there is no signed overflow.

If

\[ x>y \]

then

\[ x-y>0 \qquad \Longrightarrow \qquad \operatorname {MSB}(x-y)=0 \]

If

\[ x<y, \]

then

\[ x-y<0 \qquad \Longrightarrow \qquad \operatorname {MSB}(x-y)=1 \]

And if

\[ x=y \]

then

\[ Z=1 \]

Similarly, if

\[ x<0,\qquad y<0, \]

there is no signed overflow.

If

\[ x>y \]

then

\[ x-y>0 \qquad \Longrightarrow \qquad \operatorname {MSB}(x-y)=0 \]

If

\[ x<y \]

then

\[ x-y<0 \qquad \Longrightarrow \qquad \operatorname {MSB}(x-y)=1 \]

Again,

\[ x=y \qquad \Longrightarrow \qquad Z=1 \]

Now observe that if

\[ x>0,\qquad y<0 \]

then

\[ x>y \]

The subtraction \(x-y\) can either have

\[ \operatorname {MSB}(x-y)=0,\qquad V=0 \]

or, if it overflows,

\[ \operatorname {MSB}(x-y)=1,\qquad V=1 \]

Thus in both cases

\[ \operatorname {MSB}(x-y)\oplus V=0 \]

On the other hand, if

\[ x<0,\qquad y>0 \]

then

\[ x<y \]

The subtraction can either have

\[ \operatorname {MSB}(x-y)=1,\qquad V=0 \]

or, if it overflows,

\[ \operatorname {MSB}(x-y)=0,\qquad V=1 \]

Thus in both cases

\[ \operatorname {MSB}(x-y)\oplus V=1 \]

Therefore we can decide whether

\[ x<y \]

by checking

\[ \operatorname {MSB}(x-y)\oplus V \]

where \(V\) detects signed overflow.

\[ x<y \iff \operatorname {MSB}(x-y)\oplus V=1 \]

and

\[ x>y \iff Z=0 \;\land \; \left (\operatorname {MSB}(x-y)\oplus V\right )=0 \]

PreviousContentsNext