Clemson University  CPSC 231  Spring 2010
Basic Arithmetic (adding and subtracting)
Unsigned arithmetic
half adder logic  two onebit inputs (a, b) and
two onebit outputs (carry_out, sum)
a 0 0 1 1
+ b + 0 + 1 + 0 + 1
    
carry_out sum 00 01 01 10
a b  carry_out sum
+
0 0  0 0 carry_out = a and b
0 1  0 1
1 0  0 1 sum = a xor b
1 1  1 0
for adding multibit fields/words, e.g., 4 bits
a_3 a_2 a_1 a_0
+ b_3 b_2 b_1 b_0

sum_3 sum_2 sum_1 sum_0
we also need to add a carry_in with a_i and b_i, where i>0
full adder for a_i + b_i + carry_in given in Figure 4.2 on page 118
 three onebit inputs (a, b, carry_in) and
two onebit outputs (carry_out, sum)
 cascade two half adders (sum output bit of first attached to one
input line of the other) and or together the carry_outs
nbit adder built by connecting n full adders, with carries propagating
from right to left (i.e., connect the carry_out of an adder to the
carry_in of the adder in the next leftmost bit position; the initial,
that is, rightmost, carry_in is zero)
a_3 b_3 a_2 b_2 a_1 b_1 a_0 b_0
  ..   ..   ..   . 0
              
v___v___v  v___v___v  v___v___v  v___v___v
 full    full    full    full 
__adder__  __adder__  __adder__  __adder__
          
v  `'  `'  `' 
carry_out v v v v
sum_3 sum_2 sum_1 sum_0
overflow occurs when a number is too large to represent
for unsigned arithmetic, overflow occurs when a carry out occurs from
the most significant (i.e., leftmost) bit position
(there are faster forms of addition hardware where the carries do not have
to propagate from one side to the other, e.g., carrylookahead adder)
Signed arithmetic
fundamental idea #1
finite width arithmetic
 modulus r**n, where r is radix, n is number of digits wide
 wraps around from biggest number to zero, ignoring overflow
e.g., 4bit arithmetic => modulus is 2^4 = 16
0, 1, 2, ..., 15 then wrap around back to 0
thus an addition of r**n to an ndigit finite width value has no effect
on the ndigit value
fundamental idea #2
subtraction is equivalent to adding the negative of number
e.g., a  b = a + (b)
observation
a  b == a  b + r**n == a + (r**n  b)
\__________/ \____________/
#1 #2
\______/
this term is our representation for (b)
it turns out that we can more easily perform r**n  b than a  b
digit complement for n digits == (r**n  1)  number
in binary, this is called one's complement and equals a value of n ones
minus the bits of the number
for binary, one's complement (2**n  1  number) is equivalent to
inverting each bit
in decimal, this is called nine's complement and equals a value of n
nines minus the digits of the number
in hexadecimal, this is n `f's (fifteens) minus the digits of the number
radix complement for n digits == (r**n  1)  number + 1
two's complement in binary
ten's complement in decimal
for binary, two's complement (2**n  1  number + 1) is equivalent to
inverting each bit and adding one
two's complement encoding  note one zero and asymmetric range
first (leftmost) bit is sign bit (1 => )
binary signed magnitude one's complement two's complement
0000 +0 +0 0
0001 +1 +1 +1
0010 +2 +2 +2
0011 +3 +3 +3
0100 +4 +4 +4
0101 +5 +5 +5
0110 +6 +6 +6
0111 +7 +7 +7
1000 0 7 8
1001 1 6 7
1010 2 5 6
1011 3 4 5
1100 4 3 4
1101 5 2 3
1110 6 1 2
1111 7 0 1
we can easily make a full adder do subtraction by adding an inverter in
front of each b sub i and setting carry into the rightmost adder to one
a_3 not a_2 not a_1 not a_0 not
 b_3  b_2  b_1  b_0
  ..   ..   ..   . one
              
v___v___v  v___v___v  v___v___v  v___v___v
 full    full    full    full 
__adder__  __adder__  __adder__  __adder__
          
v  `'  `'  `' 
carry_out v v v v
diff_3 diff_2 diff_1 diff_0
range for nbit field: unsigned is [ 0, (2**n)  1 ]
2's compl. signed is [ (2**(n1)), (2**(n1))  1 ]
signed overflow occurs whenever the sign bits of the two operands agree, but
the sign bit of the result differs (i.e., add two positives and result
appears negative, or add two negatives and result appears nonnegative)
range diagrams for three bits
000 001 010 011 100 101 110 111 ++++
unsigned  b2b1b0
0 1 2 3 4 5 6 7 ++++
100 101 110 111 000 001 010 011 ++++
signed  signb1b0
(2's compl) 4 3 2 1 0 +1 +2 +3 ++++
modulo arithmetic (keep adding +1 and wraps around)
..
`>000>001>010>011>100>101>110>111'
(unsigned) 0 1 2 3 4 5 6 7
(or 2's compl) 0 +1 +2 +3 4 3 2 1
^^ carry occurs
on wrap around
3bit examples
bits unsigned signed
111 = 7 = (1)
+001 = +1 = +(+1)
  
000 0 ( 0)
(carry) OVF
^^^ this is what the ALU computes for either unsigned or signed;
but, while it is an unsigned overflow, it is CORRECT for
signed
bits unsigned signed
011 = 3 = (+3)
+001 = +1 = +(+1)
  
100 4 (4)
OVF
^^^ this is what the ALU computes for either unsigned or signed;
but, while it is correct for unsigned, it is SIGNED OVERFLOW!
16bit signed (2's complement) examples
in 16bit arithmetic, we can represent values as four hex digits;
if the leading hex digit is between 0 and 7 (thus it has a leading bit
of 0), it is a nonnegative value; if the leading hex digit is between
8 and f (thus it has a leading bit of 1), it is a negative value
hexadecimal hexadecimal decimal
0x7654 = 0x7654 = (+30292)
+0xffed = +(0x13) = +( 19)
  
0x7641 0x7641 (+30273)
(carry)
carry occurs but there is no signed overflow (thus carry is ignored)
(+) added with () cancels out, so signed overflow is not possible
hexadecimal decimal
0x7654 = (+30292)
+0x1abc = +( +6844)
 
0x9110 (28400) should be 37136, but is > max positive 32767
no carry occurs but there is signed overflow
(+) added with (+) giving () => SIGNED OVERFLOW!
hexadecimal
0x7654 change subtraction to addition by ffff
0xff8d taking two's complement of 0xff8d ff8d
 
0072
+ 1

0073
hexadecimal hexadecimal decimal
0x7654 = 0x7654 = (+30292)
0xff8d = +0x0073 = +( +115)
  
0x76c7 = (+30407)
no carry occurs and no signed overflow
(+) added with (+) giving (+) => no signed overflow
Sign extension
for the given size of a data item, the sign bit will be extended to
the left to fill out any unused significant bits in the representation
e.g., for decimal +6 and 6 when represented in two's complement
nibble byte halfword word doubleword
4 bits 8 bits 16 bits 32 bits 64 bits
+6 0x6 0x06 0x0006 0x00000006 0x0000000000000006
6 0xa 0xfa 0xfffa 0xfffffffa 0xfffffffffffffffa
Extended precision
will use carry bit  addx and subx operations
will set carry bit  addcc and subcc operations
will both use and set carry bit  addxcc and subxcc operations
start with rightmost word and work left in forming the result
a b c d addcc %d_r, %h_r, %l_r ! rightmost add only needs to set carry
+ e f g h addxcc %c_r, %g_r, %k_r ! interior add needs to use and set
 addxcc %b_r, %f_r, %j_r ! " " " " " " "
i j k l addx %a_r, %e_r, %i_r ! leftmost add only needs to use carry
4bit registers / signed (2's complement) example
0000 0000 0001 0100
+1111 1111 1111 1111

^ ^ ^ ^
   addcc 0100 + 1111 = 0011 (carry is set to 1)
  
  addxcc 0001 + 1111 + (carry==1) = 0001 (carry is set to 1)
 
 addxcc 0000 + 1111 + (carry==1) = 0000 (carry is set to 1)

addx 0000 + 1111 + (carry==1) = 0000 (output carry is ignored)
.carry. .carry. .carry.
v  v  v 
0000 0000 0001 0100 = 0x0014 = (+20)
+1111 1111 1111 1111 = +0xffff = +( 1)
  
0000 0000 0001 0011 0x0013 (+19)