Integers
 4-10  A NOTE ON INTEGERS 
 ************************
 Signed and unsigned integers
 ----------------------------
 FORTRAN integers are SIGNED INTEGERS, half the possible bit patterns 
 are used to represent positive values (and 0), the other half is used 
 for the negative values.
 A table showing the bit patterns that can be constructed with 4 bits,
 and the integers that are associated with them:
   Bit             Signed      Unsigned
   Pattern         integer     integer
   ------------    --------    --------
    1111             -1          15
    1110             -2          14
    1101             -3          13
    1100             -4          12
    1011             -5          11
    1010             -6          10
    1001             -7           9
    1000             -8           8
    0111              7           7
    0110              6           6
    0101              5           5
    0100              4           4
    0011              3           3
    0010              2           2
    0001              1           1
    0000              0           0
 Of course no FORTRAN integer type is really made of half a byte, 
 but that is enough to illustrate the general principles. 
 CPU hardware adds integers bit by bit, from the Least Significant
 Bit (LSB) to the Most Significant Bit (MSB), taking into account
 the value carried from the previous binary bit addition.
 We will call the correspondence between the possible bit patterns
 and unsigned integers the natural representation.

 Natural binary representation of positive integers
 --------------------------------------------------
 The binary representation of a positive integer N is:
    N = A0*1 + A1*2 + A2*4 + A3*8 + A4*16 + ...     Ai = {0,1}
 The Ai coefficients are the reminders on repeated divisions 
 by 2:
    A0 = N - (2 * (N / 2)) = MOD(N, 2)
    N  = N / 2
    A1 = N - (2 * (N / 2)) = MOD(N, 2)
    ......................
 The resulting binary number can be written:
    ... A4 A3 A2 A1 A0

 Other binary representations of positive integers
 -------------------------------------------------
 Two more representation methods were invented for positive integers, 
 offset binary and the binary coded decimal family (BCD). 
 These methods are better understood in the context of extending the
 representation to include negative integers, and so will be discussed
 in the next paragraph.

 Number systems that include negative & positive integers
 --------------------------------------------------------
 Extending the 'natural' binary representation of positive integers 
 to negative integers can be done in at least 3 different schemes: 
 sign-magnitude, one's complement and two's complement.
   SIGN-MAGNITUDE    The most significant bit (MSB) is reserved to 
                     the sign, 0 is positive, 1 is negative.
                     All other bits are used to store the
                     magnitude in the natural representation.
                     Addition and subtraction are complicated. 
                     There are two representations for zero!
   ONE'S COMPLEMENT  Positive integers are like in the natural
                     representation, negative numbers are obtained
                     by complementing each bit of the corresponding
                     positive number (i.e. the absolute value)
                     There are two representations for zero!
                     Bitwise addition of  N  and  -N  gives -0.
                     Positive integers still have MSB = 0, and 
                     negative integers have MSB=1.
   TWO'S COMPLEMENT  Like one's complement, but negative numbers
                     are having 1 added after complementation.
                     Bitwise addition of  N  and  -N  gives 0
                     if you ignore the carry out of the MSB.
                     Positive integers still have MSB = 0, and 
                     negative integers have MSB=1.
                     Only one representation for zero. 
 Negating an integer is always done using the operation of bitwise
 complementation, i.e. reversing the value of each bit: 
   0  --->  1
   1  --->  0
 The only integer representation used in modern computers is two's
 complement (One's complement was used in the classic CDC machines).
 Two's complement allows the same CPU circuitry to perform addition 
 and subtraction, subtraction is just addition of the negated number.
 See Appendix A for a method to diagnose the type of integer arithmetic
 on your computer.
 Two other number systems that are not extensions of the 'natural' 
 binary representation of positive integers, i.e. they give other 
 values to the positive integers are offset binary and BCD.
   OFFSET BINARY     Rarely used method, the value assigned to a bit
                     pattern is the 'natural value' minus the bit
                     pattern 100...0.
                     Forms an 'ascending' series from the negative to
                     the positive numbers.
                     Equals two's complement but with MSB complemented.
                     Only one representation for zero. 
   BCD               A family of coding systems, all of them generated
                     by taking the decimal representation and coding
                     each decimal digit (and the sign) with 4 bits.

 The following table illustrates the representation methods with
 4 bits bit patterns: 
              Sign-       One's        two's        Offset  
    Integer   magnitude   complement   complement   binary  
    -------   ---------   ----------   ----------   ------  
      +7        0111        0111         0111        1111   
      +6        0110        0110         0110        1110   
      +5        0101        0101         0101        1101   
      +4        0100        0100         0100        1100   
      +3        0011        0011         0011        1011   
      +2        0010        0010         0010        1010   
      +1        0001        0001         0001        1001   
       0        0000        0000         0000        1000   
      -1        1001        1110         1111        0111   
      -2        1010        1101         1110        0110   
      -3        1011        1100         1101        0101   
      -4        1100        1011         1100        0100   
      -5        1101        1010         1011        0011   
      -6        1110        1001         1010        0010   
      -7        1111        1000         1001        0001   
      -8        ----        ----         1000        0000   
     (-0)       1000        1111         ----        ----   
                          
 The following table shows the three common BCD coding systems
 (BCD 8421 is known as just BCD):
      Pattern    BCD 8421   Excess-3   BCD 2421
      --------   --------   --------   --------
       1111                               9
       1110                               8
       1101                               7
       1100                    9          6
       1011                    8          5
       1010                    7
       1001         9          6
       1000         8          5
       0111         7          4
       0110         6          3
       0101         5          2         
       0100         4          1          4
       0011         3          0          3
       0010         2                     2
       0001         1                     1
       0000         0                     0

 BCD arithmetic on strings is really a kind of multiple precision 
 arithmetic (bignums). Old computers implemented BCD in hardware, 
 but it is inefficient compared with integers and reals.
 Excess-3 and BCD 2421 were devised so that bitwise complementation
 will give the 9's complement (the radix 2 analog of 1's complement) 
 of the decimal number, making hardware implementation require more 
 simple circuitry.

 Using integers in place of floating-point numbers
 -------------------------------------------------
 Integers are sometimes called fixed-point numbers because they can
 be viewed as floats with radix point after the least significant 
 digit, and zero fractional digits:
      1      1.000...
     10     10.000...
    100    100.000...
 This strange representation hints at a possible use of integers as
 a replacement for floats. Instead of a float X with p digits decimal 
 mantissa, we can use an integer N: 
    N = INT(X * (10**p))     (Float to integer transformation)
    X = N / (10**p)          (Recovering the float from the integer)

 Addition is simple, you just add the integers.
    X1 + X2 = N1 / (10**p)  +  N2 / (10**p) = (N1 + N2) / (10**p)

 Multiplication is more tricky:
    X1 * X2 = [N1 / (10**p)] * [N2 / (10**p)] 
            = (N1 * N2) / [(10**p)**2]
            = [(N1 * N2) / (10**p)] / (10**p)
 Division by an extra (10**p) factor is needed to get the right answer.
 A common INTEGER type is the INTEGER*4 which has range: 
    [-2,147,483,648 : 2,147,483,647]
 that means that with a 3 digits decimal mantissa you will get only
 the range: 
    [-2,147,483.648 : 2,147,483.647]
 The advantage of using integers instead of floats is that roundoff
 errors are eliminated on addition and subtraction (problematic 
 operations with floats). Radix conversions between the internal
 binary representation and external decimal are also errorless.
 Integer operations takes about the same CPU time as the corresponding 
 float operations.

 Unsigned integers
 -----------------
 If you work with quantities that are always positive, and even 
 intermediary and temporary results are positive, half of the integer
 range is 'wasted'. However, unsigned integers are awkward to emulate 
 with signed integer arithmetic(?).
 You may get the output of a measuring device in a file containing 
 unsigned integers, or get a file created by a program written in
 a language that supports unsigned integers, e.g. C. 

 Comparing unsigned integers
 ---------------------------
 Unsigned integers can be compared with a small routine that uses the 
 ordinary FORTRAN comparison operators:
      LOGICAL FUNCTION UGE(I, J)
C     ------------------------------------------------------------------
      INTEGER   I, J
C     ------------------------------------------------------------------
      IF (I .GE. 0) THEN
        IF (J .LT. 0) THEN
          UGE = .FALSE.
          RETURN
        ENDIF
      ELSE
        IF (J .GE. 0) THEN
          UGE = .TRUE.
          RETURN
        ENDIF
      ENDIF
C     ------------------------------------------------------------------
      IF (I .GE. J) THEN
        UGE = .TRUE.
      ELSE
        UGE = .FALSE.
      ENDIF
C     ------------------------------------------------------------------
      RETURN
      END
 This little monster can be further optimized ...
 
Prev Contents Next