Clemson University -- CPSC 231 -- Fall 2009 Basic Arithmetic (adding and subtracting) Unsigned arithmetic half adder logic - two one-bit inputs (a, b) and two one-bit 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 multi-bit 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 one-bit inputs (a, b, carry_in) and two one-bit 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 n-bit 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., carry-lookahead 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., 4-bit arithmetic => modulus is 2^4 = 16 0, 1, 2, ..., 15 then wrap around back to 0 thus an addition of r**n to an n-digit finite width value has no effect on the n-digit 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 n-bit field: unsigned is [ 0, (2**n) - 1 ] 2's compl. signed is [ -(2**(n-1)), (2**(n-1)) - 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 |----|----|----|----|----|----|----| |b2|b1|b0| 0 1 2 3 4 5 6 7 +--+--+--+ 100 101 110 111 000 001 010 011 +----+--+--+ signed |----|----|----|----|----|----|----| |sign|b1|b0| (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 3-bit 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! 16-bit signed (2's complement) examples in 16-bit 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 4-bit 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)