Integer Arithmetic

We want to perform the standard collection of integer arithmetic operations: addition $(x + y)$ , unary negation/additive inverse $(- x)$ , subtraction $(x - y)$ , multiplication $(x * y)$ , division $(x / y)$ .

Everything can be defined from addition and additive inverse

We can’t do mathematical addition with $n$ -bit representations

We defined the operations $x ⨁ y$ , $x ⨀ y$

Unsigned Integer Addition: $x ⨁_{u}^{n} y$

Operationally:

Starting at position $x$ on the unsigned $n$ -wheel, move $y$ positions clockwise, ending at the sum

Definition:

$r = x ⨁_{u}^{n} y = def (x + y) mod 2^{n}$

If we go past the red flag (largest representable value) in doing this, we have an unsigned carry.

Properties of Integer Addition $⨁_{u}^{n}$

$⨁_{u}^{n}$ is commutative and associative

The element $0$ is the unique identity for $⨁_{u}^{n}$

i.e., $\forall x \in U_{n} : x ⨁_{u}^{n} 0 = x$ .

Every element $x$ has a unique additive inverse $⊖_{u}^{n}$

i.e., $\forall x \in U_{n} : x ⨁_{u}^{n} (⊖_{u}^{n} x) = 0$

Unsigned Integer Subtraction: $x ⊖_{u}^{n} y$

Operationally:

Starting at position $x$ on the unsigned $n$ -wheel, move $⊖_{u}^{n} y$ positions clockwise (equivalent to moving $y$ positions counter-clockwise), ending at the difference

Definition:

$r = x ⊖_{u}^{n} y = def x ⨁_{u}^{n} (⊖_{u}^{n} y)$

If we go past the red flag in doing this, we have an unsigned carry.

Same properties as integer addition.

Signed Integer Addition: $x ⨁_{s}^{n} y$

Operationally:

Starting at position $x$ on the signed $n$ -wheel, move $y$ positions clockwise, ending at the sum.
- What if $y < 0$ ?

Definition:

Let $s = x + y$ , this is the mathematical sum
Then $r = x ⨁_{s}^{n} y =$

Signed Overflow: $⨁_{s}^{n}$

If we go past the red flag in either direction while doing this, we have a signed overflow

Detection is value based

Properties of $⨁_{s}^{n}$

$⨁_{s}^{n}$ is commutative and associative

The element $0$ is the unique identity for $⨁_{s}^{n}$

i.e., $\forall x \in S_{n} : x ⨁_{u}^{n} 0 = x$

Every element $x$ has a unique additive inverse $⊖_{u}^{n} x$

i.e., $\forall x \in S_{n} : x ⨁_{u}^{n} (⊖_{u}^{n} x) = 0$

Example Additive Inverse $⊖_{s}^{3} x$

Repr $x$	$x$	$⊖_{s}^{3} x$	Repr( $⊖_{s}^{3} x$ )	~Repr( $x$ )	~Repr( $x$ )+1
000	0	0	000	111	000
001	1	-1	111	110	111
010	2	-2	110	101	110
011	3	-3	101	100	101
100	-4	-4	100	011	100

Multiplication: $⨀_{u}^{n}$ and $⨀_{s}^{n}$

Operationally (not very useful):

Iterated addition — literally definitionally what multiplication is
Adjust appropriately for signed

Definition:

Unsigned: $x ⨀_{u}^{n} y = def (x \cdot y) mod 2^{n}$
Signed: $x ⨀_{s}^{n} y = def U 2 S_{n} ((x \cdot y) mod 2^{n})$
- First calculate the unsigned value, then convert to a signed value.

$U 2 S_{n}$ means Unsigned to Signed - We need this one because of the definition of the mod operator.

$S 2 U$ means Signed to Unsigned

Ex: $x ⨀_{u}^{3} y$ with $x = 5$ and $y = 6$

2^{n} = 2^{3} = 8 5 \times 6 = 30 = 3 \times 8 + 6

Ex: $x ⨀_{u}^{3} y$ with $x = 3$ and $y = - 2$

2^{n} = 2^{3} = 8 3 \times - 2 = - 6 = - 1 \times 8 + 2

Ex: $x ⨀_{u}^{3} y$ with $x = 3$ and $y = - 3$

2^{n} = 2^{3} = 8 3 \times - 3 = - 9 = - 2 \times 8 + 7

The number’s $- 2$ and $7$ are chosen because we have defined $mod$ to not be negative. So we must go farther and then step back.

In this case, we go to $- 16$ and then move upwards back to $- 9$ .

Multiplication by Constants

For $0 \leq k < n$ :

$x ⨀_{u}^{n} 2^{k} = x << k$
$x ⨀_{s}^{n} 2^{k} = x << k$

This gives us a way of simplifying multiplying by constants using shifts and adds (strength reduction).

Ex: $x \times 14 = x \times 8 + x \times 4 + x \times 2 = (x << 3) + (x << 2) + (x << 1)$ .

Floor and Ceiling Functions

For any real number $x$ , we define:

floor( $x$ ), written $⌊ x ⌋$ , to be the greatest integer less than or equal to $x$
ceil( $x$ ), written $⌈ x ⌉$ , to be the smallest integer greater than or equal to $x$

If $n$ is an integer, then $⌊ n ⌋ = ⌈ n ⌉ = n$

Otherwise, $⌊ n ⌋ = ⌈ n ⌉ - 1$

Integer Division by Constants

For $0 \leq k < n$ :

Unsigned: $x > >_{L} k$ yields $⌊ x / 2^{k} ⌋$
Signed: $x > >_{A} k$ yields $⌊ x / 2^{k} ⌋$
Signed: $(x + (1 << k) - 1) > >_{A} k$ yields $⌈ x / 2^{k} ⌉$
- We first bias the value and then perform the shift
- $1 << k = 1 \times 2^{k} = 2^{k} - 1$

Implementing Addition

Very, very similar to a grade school addition algorithm.

s	0	1
0	0	1
1	1	0

+	0	1
0	00	01
1	01	10

C	0	1
0	0	0
1	0	1

$n$ -bit Adder

We want $(s [n - 1 : 0], c) = S U M (a [n - 1 : 0], b [n - 1 : 0])$

Literally think of regular addition but in base 2, so instead of reaching 10 and then carrying, we carry when we reach 2.

We use the ripple-carry adder scheme

$(s [0], c_{o u t} [0]) = F A (a [0], b [0], 0)$
$\forall i \in [1 : n - 1], (s [i], c_{o u t} [i]) = F A (a [i], b [i], c_{o u t} [i - 1])$
$c = c_{o u t} [n - 1]$

$n$ -bit Subtractor

We want $(d [n - 1 : 0], c) = D I FF (a [n - 1 : 0], b [n - 1 : 0])$

We will implement this by using the definition of subtraction in terms of addition and additive inverse:

a - b = a + (- b) = a + \overline{b} + 1

Literally think of regular addition but in base 2, so instead of reaching 10 and then carrying, we carry when we reach 2.

We still use the ripple-carry adder scheme

$(d [0], c_{o u t} [0]) = F A (a [0], b [0], 1)$
$\forall i \in [1 : n - 1], (d [i], c_{o u t} [i]) = F A (a [i], b [i], c_{o u t} [i - 1])$
$c = c_{o u t} [n - 1]$

Notes

Explorer

Integer Arithmetic

Integer Arithmetic

Unsigned Integer Addition: $x ⨁_{u}^{n} y$

Properties of Integer Addition $⨁_{u}^{n}$

Unsigned Integer Subtraction: $x ⊖_{u}^{n} y$

Signed Integer Addition: $x ⨁_{s}^{n} y$

Signed Overflow: $⨁_{s}^{n}$

Properties of $⨁_{s}^{n}$

Example Additive Inverse $⊖_{s}^{3} x$

Multiplication: $⨀_{u}^{n}$ and $⨀_{s}^{n}$

Ex: $x ⨀_{u}^{3} y$ with $x = 5$ and $y = 6$

Ex: $x ⨀_{u}^{3} y$ with $x = 3$ and $y = - 2$

Ex: $x ⨀_{u}^{3} y$ with $x = 3$ and $y = - 3$

Multiplication by Constants

Floor and Ceiling Functions

Integer Division by Constants

Implementing Addition

$n$ -bit Adder

$n$ -bit Subtractor

Graph View

Table of Contents

Backlinks

Repr $x$	$x$	$⊖_{s}^{3} x$	Repr( $⊖_{s}^{3} x$ )	~Repr( $x$ )	~Repr( $x$ )+1
000	0	0	000	111	000
001	1	-1	111	110	111
010	2	-2	110	101	110
011	3	-3	101	100	101
100	-4	-4	100	011	100

Repr $x$	$x$	$⊖_{s}^{3} x$	Repr( $⊖_{s}^{3} x$ )	~Repr( $x$ )	~Repr( $x$ )+1
000	0	0	000	111	000
001	1	-1	111	110	111
010	2	-2	110	101	110
011	3	-3	101	100	101
100	-4	-4	100	011	100

Notes

Explorer

Integer Arithmetic

Integer Arithmetic

Unsigned Integer Addition: x⨁un​y

Properties of Integer Addition ⨁un​

Unsigned Integer Subtraction: x⊖un​y

Signed Integer Addition: x⨁sn​y

Signed Overflow: ⨁sn​

Properties of ⨁sn​

Example Additive Inverse ⊖s3​x

Multiplication: ⨀un​ and ⨀sn​

Ex: x⨀u3​y with x=5 and y=6

Ex: x⨀u3​y with x=3 and y=−2

Ex: x⨀u3​y with x=3 and y=−3

Multiplication by Constants

Floor and Ceiling Functions

Integer Division by Constants

Implementing Addition

n-bit Adder

n-bit Subtractor

Graph View

Table of Contents

Backlinks

Unsigned Integer Addition: $x ⨁_{u}^{n} y$

Properties of Integer Addition $⨁_{u}^{n}$

Unsigned Integer Subtraction: $x ⊖_{u}^{n} y$

Signed Integer Addition: $x ⨁_{s}^{n} y$

Signed Overflow: $⨁_{s}^{n}$

Properties of $⨁_{s}^{n}$

Example Additive Inverse $⊖_{s}^{3} x$

Multiplication: $⨀_{u}^{n}$ and $⨀_{s}^{n}$

Ex: $x ⨀_{u}^{3} y$ with $x = 5$ and $y = 6$

Ex: $x ⨀_{u}^{3} y$ with $x = 3$ and $y = - 2$

Ex: $x ⨀_{u}^{3} y$ with $x = 3$ and $y = - 3$

$n$ -bit Adder

$n$ -bit Subtractor

Repr $x$	$x$	$⊖_{s}^{3} x$	Repr( $⊖_{s}^{3} x$ )	~Repr( $x$ )	~Repr( $x$ )+1
000	0	0	000	111	000
001	1	-1	111	110	111
010	2	-2	110	101	110
011	3	-3	101	100	101
100	-4	-4	100	011	100