doc/specifications/arith.int.html

   1 <html>
   2 <head>
   3 <title> Lecture notes - Chapter 5 - Integer Arithmetic</title>
   4 </head>
   5
   6 <BODY>
   7 <h1> Chapter 5 -- integer arithmetic</h1>
   8
   9 <pre>
  10
  11 all about integer arithmetic.
  12 -------------------------------
  13
  14
  15 operations we'll get to know (and love):
  16     addition
  17     subtraction
  18     multiplication
  19     division
  20     logical operations (not, and, or, nand, nor, xor, xnor)
  21     shifting
  22
  23
  24 the rules for doing the arithmetic operations vary depending
  25 on what representation is implied.
  26
  27 A LITTLE BIT ON ADDING
  28 ----------------------
  29   an overview for unsigned integers
  30
  31
  32         carry in  a  b | sum  carry out
  33         ---------------+----------------
  34            0      0  0 |  0    0
  35            0      0  1 |  1    0
  36            0      1  0 |  1    0
  37            0      1  1 |  0    1
  38            1      0  0 |  1    0
  39            1      0  1 |  0    1
  40            1      1  0 |  0    1
  41            1      1  1 |  1    1
  42                        |
  43
  44        a      0011
  45       +b     +0001
  46       --     -----
  47      sum      0100
  48
  49
  50   its really just like we do for decimal!
  51     0 + 0 = 0
  52     1 + 0 = 1
  53     1 + 1 = 2  which is 10 in binary, sum is 0 and carry the 1.
  54     1 + 1 + 1 = 3  sum is 1, and carry a 1.
  55 \f
  56
  57
  58
  59 ADDITION
  60 --------
  61
  62 unsigned:
  63   just like the simple addition given.
  64
  65   examples:
  66
  67       100001           00001010 (10)
  68      +011101          +00001110 (14)
  69      -------          ---------
  70       111110           00011000 (24)
  71
  72   Ignore (throw away) carry out of the msb.
  73
  74   We do unsigned addition with the assumption that we are
  75   working of a fixed precision value. Fixed precision means
  76   that the number of bits can not change.
  77
  78
  79
  80 sign magnitude:
  81
  82   rules:
  83     - do unsigned addition on magnitudes only (do not carry into the sign bit)
  84     - throw away any carry out of the msb of the magnitude
  85     - add only integers of like sign ( + to +    or    - to -)
  86     - sign of result is same as sign of the addends
  87
  88   examples:
  89
  90     0  0101 (5)        1  1010 (-10)
  91   + 0  0011 (3)      + 1  0011 (-3)
  92   ---------          ---------
  93     0  1000 (8)        1  1101 (-13)
  94
  95
  96     0  01011 (11)
  97   + 1  01110 (-14)
  98   ----------------
  99   don't add! must do subtraction!
 100
 101   Again, we do sign magnitude addition with the assumption that we are
 102   working of a fixed precision value. Fixed precision means
 103   that the number of bits can not change.
 104 \f
 105
 106
 107
 108 one's complement:
 109
 110    by example (using the unsigned addition algorithm)
 111
 112
 113     00111 (7)         111110 (-1)            11110 (-1)
 114   + 00101 (5)       + 000010 (2)           + 11100 (-3)
 115   -----------       ------------           ------------
 116     01100 (12)      1 000000 (0) wrong!    1 11010 (-5) wrong!
 117                         +  1                  +  1
 118                       ----------             ----------
 119                       000001 (1) right!      11011 (-4) right!
 120
 121
 122    So, it seems that if there is a carry out of the msb, then
 123    the result will be off by 1, so add 1 again to get the correct
 124    result.  (Implementation in HW called an "end around carry.")
 125
 126
 127
 128
 129 two's complement:
 130
 131    rules:
 132      - just do unsigned addition
 133      - throw away any carry out of the msb
 134
 135    examples
 136
 137
 138     00011 (3)         101000               111111 (-1)
 139   + 11100 (-4)      + 010000             + 001000 (8)
 140   ------------      --------             --------
 141     11111 (-1)        111000             1 000111 (7)
 142                                          ^
 143                                          this bit is thrown away
 144
 145 After seeing examples for all these representations, you may see
 146 why 2's complement addition requires simpler hardware than
 147 sign mag. or one's complement addition.
 148 \f
 149
 150
 151 SUBTRACTION
 152 -----------
 153   general rules:
 154     1 - 1 = 0
 155     0 - 0 = 0
 156     1 - 0 = 1
 157    10 - 1 = 1
 158     0 - 1 = borrow!
 159
 160
 161
 162
 163 unsigned:
 164
 165   -  it only makes sense to subtract a smaller number from a larger one
 166
 167   example
 168
 169      1011 (11)   must borrow
 170   -  0111 (7)
 171   ------------
 172      0100 (4)
 173
 174
 175
 176 sign magnitude:
 177
 178   - if the signs are the same, then  do subtraction
 179   - if signs are different, then change the problem to addition
 180   - Compare magnitudes, then subtract smaller from larger.
 181     If the order is switched, then switch the sign too.
 182
 183   - when the integers are of the opposite sign, then do
 184         a - b    becomes   a + (-b)
 185         a + b    becomes   a - (-b)
 186
 187
 188      examples
 189
 190    0 00111 (7)             1 11000 (-24)
 191  - 0 11000 (24)          - 1 00010 (-2)
 192  --------------          --------------
 193                            1 10110 (-22)
 194 do 0 11000 (24)
 195  - 0 00111 (7)
 196  --------------
 197    1 10001 (-17)
 198    (switch sign since the order of the subtraction was reversed)
 199
 200 \f
 201
 202
 203 one's complement:
 204
 205      figure it out on your own
 206
 207
 208
 209
 210 two's complement:
 211
 212   - change the problem to addition!
 213
 214        a - b  becomes   a + (-b)
 215
 216   - so, get the additive inverse of b, and do addition.
 217
 218     examples
 219
 220    10110 (-10)
 221  - 00011 (3)    -->       00011
 222  ------------
 223                           11100 (after taking the 1's complement)
 224                         +     1
 225                         -------
 226                           11101 (-3)
 227  so do
 228
 229      10110 (-10)
 230    + 11101 (-3)
 231    ------------
 232      10011  (-13)
 233   (throw away carry out)
 234 \f
 235
 236 OVERFLOW
 237 ---------
 238
 239 OVERFLOW DETECTION IN ADDITION
 240
 241   unsigned -- when there is a carry out of the msb
 242
 243            1000 (8)
 244           +1001 (9)
 245           -----
 246          1 0001 (1)
 247
 248   sign magnitude -- when there is a carry out of the msb of the magnitude
 249
 250          1 1000 (-8)
 251        + 1 1001 (-9)
 252           -----
 253          1 0001 (-1)  (carry out of msb of magnitude)
 254
 255   2's complement -- when the signs of the addends are the same, and the
 256                     sign of the result is different
 257
 258           0011 (3)
 259         + 0110 (6)
 260         ----------
 261           1001 (-7)   (note that a correct answer would be 9, but
 262                        9 cannot be represented in 4-bit 2's complement)
 263
 264   a detail -- you will never get overflow when adding 2 numbers of
 265               opposite signs
 266
 267
 268 OVERFLOW DETECTION IN SUBTRACTION
 269
 270    unsigned -- never
 271    sign magnitude -- never happen when doing subtraction
 272    2's complement -- We never do subtraction. If the addition operation
 273       causes overflow, then overflow occurs.
 274 \f
 275
 276
 277
 278 MULTIPLICATION of integers
 279
 280      0 x 0 = 0
 281      0 x 1 = 0
 282      1 x 0 = 0
 283      1 x 1 = 1
 284
 285      -- longhand, it looks just like decimal
 286
 287      -- the result can require 2x as many bits as the larger operand
 288
 289      -- in 2's complement, to always get the right answer without
 290         thinking about the problem, sign extend both integers to
 291         twice as many bits (as the larger).  Then take the correct number
 292         of result bits from the least significant portion of the result.
 293         Note that the HW that implements multiplication does not
 294         use this algorithm.
 295
 296
 297     2's complement example:
 298
 299
 300              1111 1111        -1
 301            x 1111 1001     x  -7
 302       ----------------    ------
 303               11111111         7
 304              00000000
 305             00000000
 306            11111111
 307           11111111
 308          11111111
 309         11111111
 310    +   11111111
 311        ----------------
 312         1  00000000111
 313               --------  (correct answer underlined)
 314
 315
 316       WRONG !                Sign extended:
 317         0011 (3)               0000 0011 (3)
 318       x 1011 (-5)            x 1111 1011 (-5)
 319       ------                 -----------
 320         0011                    00000011
 321        0011                    00000011
 322       0000                    00000000
 323    + 0011                    00000011
 324    ---------                00000011
 325      0100001               00000011
 326   not -15 in any          00000011
 327    representation!     + 00000011
 328                       ------------------
 329                               1011110001
 330                                 --------
 331                           take the least significant 8 bits 11110001 = -15
 332 \f
 333
 334 more about integer multiplication.
 335 -------------------------------------
 336
 337    multiplicand
 338  x   multiplier
 339  ----------------
 340     product
 341
 342
 343 If we do NOT sign extend the operands (multiplier and multiplicand),
 344 before doing the multiplication, then the wrong answer sometimes
 345 results.  To make this work, sign-extend the partial products
 346 to the correct number of bits.
 347
 348 To ease our work, classify which do work, and which don't.
 349
 350
 351     +          -            +            -      (muliplicands)
 352   x +        x +          x -          x -      (mulipiers)
 353   ----       ----         ----         ----
 354    OK        sign          |            |
 355            extend          | take       |
 356           partial          | additive   |
 357           products         | inverses   |
 358
 359                             -            +
 360                           x +          x +
 361                           ----          ----
 362                           sign           OK
 363                         extend
 364                        partial
 365                        products
 366
 367
 368
 369 Example:
 370
 371   without                          with correct
 372   sign extension                   sign extension
 373
 374       11100 (-4)                         11100
 375     x 00011 (3)                        x 00011
 376     ------------                      ---------
 377       11100                         1111111100
 378      11100                         1111111100
 379     ------------                ---------------
 380     1010100 (-36)                   1111110100  (-12)
 381      WRONG!                            RIGHT!
 382
 383 \f
 384
 385
 386
 387 Another example:
 388
 389
 390     without adjustment              with correct adjustment
 391
 392       11101 (-3)                       11101 (-3)
 393     x 11101 (-3)                     x 11101 (-3)
 394    -------------                    -------------
 395       11101                           (get additive inverse of both)
 396     11101
 397    11101                               00011 (+3)
 398  +11101                              x 00011 (+3)
 399  -----------                        -------------
 400  1101001001 (wrong!)                   00011
 401                                     + 00011
 402                                    ---------
 403                                       001001 (+9) (right!)
 404 \f
 405
 406
 407 DIVISION of integers
 408      unsigned only in this class!
 409      (Don't worry, you'll do lots of division in CS/ECE 552!)
 410
 411                 quotient
 412              ----------------
 413      divisor | dividend
 414
 415
 416      written as fractions:      dividend
 417                                 --------
 418                                 divisor
 419
 420      example:
 421       15 / 3         1111 / 011
 422
 423                0101
 424              -----------
 425         011  | 1111
 426               -0
 427               --
 428                11
 429              - 11
 430              ----
 431                 01
 432                 -0
 433                 --
 434                  11
 435                - 11
 436                ----
 437                   0  (remainder)
 438 \f
 439
 440
 441      another example:
 442
 443       20 / 3         010100 / 011
 444
 445
 446                000110 (quotient = 6)
 447              -----------
 448         011  | 010100
 449               -0
 450              ---
 451                01
 452                -0
 453               ---
 454                010
 455                 -0
 456                ---
 457                0101
 458               - 011
 459                ----
 460                00100
 461                - 011
 462                 ----
 463                  0010
 464                 -   0
 465                  ----
 466                    10 (remainder = 2)
 467 \f
 468
 469
 470 LOGICAL OPERATIONS
 471 -------------------
 472    They are done bitwise.
 473
 474    Bitwise means corresponding bits of the operands are operated
 475    on, with the single bit result going into the corresponding
 476    bit of the result.
 477
 478    bit 0 of X goes with bit 0 of Y, and the result goes in bit 0.
 479
 480                      X =  0011
 481                      Y =  1010
 482
 483        X  AND  Y is       0010
 484        X   OR  Y is       1011
 485        X  NOR  Y is       0100
 486        X  XOR  Y is       1001
 487                 etc.
 488
 489
 490 SHIFT OPERATIONS
 491 ----------------
 492   A way of moving bits around within a word.
 493   A shift by n places is the same as n shifts by 1 place.
 494
 495   3 types:     logical, arithmetic and rotate
 496                (each type can go either left or right)
 497
 498   logical left - move bits to the left, same order
 499                - throw away the bit that pops off the msb
 500                - introduce a 0 into the lsb
 501
 502
 503                00110101
 504
 505                01101010 (logically left shifted by 1 bit)
 506
 507
 508   logical right - move bits to the right, same order
 509                - throw away the bit that pops off the lsb
 510                - introduce a 0 into the msb
 511
 512                00110101
 513
 514                00011010  (logically right shifted by 1 bit)
 515
 516
 517   arithmetic left - move bits to the left, same order
 518                - throw away the bit that pops off the msb
 519                - introduce a 0 into the lsb
 520                - SAME AS LOGICAL LEFT SHIFT!
 521 \f
 522
 523
 524   arithmetic right - move bits to the right, same order
 525                - throw away the bit that pops off the lsb
 526                - reproduce the original msb into the new msb
 527                - another way of thinking about it:  shift the
 528                  bits, and then do sign extension
 529
 530                00110101 ->  00011010 (arithmetically right shifted by 1 bit)
 531
 532                1100 -> 1110   (arithmetically right shifted by 1 bit)
 533
 534
 535
 536   rotate left - move bits to the left, same order
 537               - put the bit that pops off the msb into the lsb,
 538                 so no bits are thrown away or lost.
 539
 540                00110101 -> 01101010 (rotated left by 1 place)
 541                1100 -> 1001 (rotated left by 1 place)
 542
 543
 544   rotate right - move bits to the right, same order
 545               - put the bit that pops off the lsb into the msb,
 546                 so no bits are thrown away or lost.
 547
 548                00110101 -> 10011010 (rotated right by 1 place)
 549                1100 ->  0110 (rotated right by 1 place)
 550 \f
 551
 552
 553
 554 SAL INSTRUCTIONS FOR LOGICAL AND SHIFT OPERATIONS
 555
 556    SAL has instructions that do bitwise logical operations and
 557    shifting operations (ON .word OPERANDS!).
 558
 559
 560         not   x, y         x <-  NOT (y)
 561         and   x, y, z      x <-  (y) AND (z)
 562         or    x, y, z      x <-  (y) OR (z)
 563         nor   x, y, z      x <-  (y) NOR (z)
 564         nand  x, y, z      x <-  (y) NAND (z)
 565         xor   x, y, z      x <-  (y) XOR (z)
 566         xnor  x, y, z      x <-  (y) XNOR (z)
 567
 568         sll   x, y, value     x <- (y), logically left shifted by value bits
 569         srl   x, y, value     x <- (y), logically right shifted by value bits
 570         sra   x, y, value     x <- (y), arithmetically right shifted by
 571                                         value bits
 572         rol   x, y, value     x <- (y), rotated left by value bits
 573         ror   x, y, value     x <- (y), rotated right by value bits
 574 \f
 575
 576
 577
 578 A common student question occurs as a result of learning of
 579 the shift and logical operations:  what are they used for?
 580
 581 Here are some examples as a partial answer to the question.
 582
 583
 584   Example:
 585       A certain program has a bunch of boolean values that
 586       it will need to maintain.
 587
 588       Place all these (bit-sized) variables into one (word-sized)
 589       integer variable:
 590
 591       Bit number:     31     30 . . . .  2    1    0
 592       Contents       var31  var30       var2 var1 var0
 593
 594       So, we've got up to 32 variables placed into one integer.
 595       Let this integer be called var.
 596
 597       What would we want to do to these boolean variables?
 598       Answer:  individually set (make a 1) or clear (make a 0)
 599       a variable.
 600
 601
 602       SAL code to set var5:
 603
 604               or  var, var, 0x00000020
 605       Whatever was in all bits other than bit 5 remain the same,
 606       and bit 5 (called var5 for this example, but not in code)
 607       gets the value 1.
 608
 609
 610
 611       SAL code to clear var12 and var3:
 612
 613               and  var, var, 0xffffeff7
 614       Whatever was in all bits other than bits 12 and 3 remain the same,
 615       and bits 12 and 3 get the value 0.
 616
 617       The value 0xffffeff7 (or 0x00000020 in the previous example)
 618       is called a MASK.  It specifies the settings of bits.
 619       Here is the mapping of some of the bits to show how the
 620       mask was created.
 621
 622       bit #      15 14 13 12 11 10  9  8  7  6  5  4  3  2  1  0
 623       contents    1  1  1  0  1  1  1  1  1  1  1  1  0  1  1  1
 624
 625 \f
 626
 627   A completely different example:
 628       Suppose that we want to do operations on strings.
 629       (A string is a bunch of characters that happen to reside
 630       next to each other in memory.)
 631
 632       What operations might be appropriate?
 633          Insert characters?  Concatenate strings?  Switch order
 634          of characters?  Change lower case to upper case?
 635
 636       What do strings look like?
 637          The ASCII characters are placed into memory one following
 638          another.  Yet, to operate on parts of strings, we might
 639          want to work on integer-sized chunks. . .
 640          An operand the size of an integer is most often called
 641          a WORD on a computer.
 642
 643
 644          Part of a string in a 32-bit word:
 645
 646            -------------------------
 647            | 'A' | 'B' | 'C' | 'D' |
 648            -------------------------
 649
 650       Call this variable x.  Write a SAL code fragment that
 651       reverses the middle two characters, without changing
 652       the rest.
 653
 654
 655            and   temp1, x, 0x00ff0000   # extract out the 'B' byte
 656            and   temp2, x, 0x0000ff00   # extract out the 'C' byte
 657            and   x, x, 0xff0000ff       # clear middle 2 bytes
 658            srl   temp1, temp1, 8        # move the 'B' 1 byte to right
 659            sll   temp2, temp2, 8        # move the 'C' 1 byte to left
 660            or    x, x, temp1            # merge moved 'B' back in
 661            or    x, x, temp2            # merge moved 'C' back in
 662
 663
 664
 665 </pre>