Computer Algorithms I CS 305 Class Notes

Lecture Notes for Computer Algorithms I

9 September 2003 - Basic Data Types

Pre-defined data types.
- The data types that come with the language.
- Pre-defined data types are usually better supported and integrated than other data types.
- What are the properties of the pre-defined data types?
  - What are they called?
  - What are the values and literals of that type. Are there any literals of that type?
  - What are the limits? Their size? The relation between size and value, if any?
  - What are their operators?
  - What are their quirks, if any (and they all have quirks)?
  - What is the relation between data types?
- Be careful: pre-defined doesn't mean "simple".
The Boolean Data Type
- The Boolean data types represent the logical values true and false.
  - George Boole was a 19th century English mathematician.
- The Boolean values are denoted by the keywords true and false.
- Boolean variables are declared with the bool type-name.
- A function returning a Boolean value is called a predicate.
  - Think carefully when defining a predicate.
    bool is_positive(int x) if x > 0 return true else return false
    
    bool is_positive(int x) return x > 0
- Boolean Conversions
  - Pre-standard C++ (and C to this day) did not have a Boolean type.
    - Scalar values served as booleans.
      - Zero values were false.
      - Non-zero values were true.
  - For compatibility, C++ has conversions between Boolean and integer types.
    - Going from integers to Booleans is common.
      Zero values convert to false.
      Non-zero values convert to true.
    - Going from Booleans to integers is less so.
      false converts to 0.
      true converts to 1.
  - conversions are the basis of the count-test idiom.
    if count(a, x, n) // one or more x in a. else // no x in a.
    
    if count(a, x, n) != 0 // one or more x in a. else // no x in a.
  - Boolean-to-integer conversions are less frequent; avoid them.
    - They are used in formatted I-O, however.
  - Also avoid using integers for Booleans.
```
int found = 0;

bool done = false;
```
- Boolean Operators
  - The three Boolean operators are and &&, or ||, and negation !.
    - Don't confuse pipe | with bang !.
  - The precedence is ! high, &&, and || low, all lower than most other operators.
```
not x > 7  &&  y > 7  ||  x + y > 14

((((not x) > 7)  &&  (y > 7))  ||  (x + y > 14))
```
    - Don't guess - use parenthesis to make your intention clear.
```
(x <= 7  &&  y > 7)  ||  (x + y > 14)
```
  - The Boolean operators also exist in keyword form.
    - and for &&, or for ||, and not for !.
```
if !done && !is.eof() { ... }

if not done and not is.eof() { ... }
```
    - This means and, or, and not are not available as names.
- Short-Circuit Evaluation
  - and and or behave almost the same way as the mathematical and and or.
    
    || t f
    
    t t t
    
    f t f
    
    && t f
    
    t t f
    
    f f f
  - Short-circuit evaluation avoids evaluating b if possible.
    bool and(bool a, bool b) if not a return false else if b return true else return false
    
    bool or(bool a, bool b) if a return true else if b return true else return false
  - Short-circuit evaluation makes the test-then-access idiom work.
```
while (ptr  and  ptr->value != x) ptr++;

while (i < n  and  a[i] != x) i++;
```
  - Be careful when b is a function.
```
if x < 10  and  f(x) > 20 { ... }
```
    - f() may or may not be called.
    - f() must be side-effect free (no I-O in particular).
The Character Data Type
- The character data type used to be simpler than it is now.
- Character values are eight-bit integers.
  - Which eight-bit values, however, are implementation defined.
  - They can be either [0..255] or [-128..127].
  - This is the difference between signed characters and unsigned characters.
- Character variables are declared with the char type-name.
  - When it's important, use the signed and unsigned modifiers with char.
```
typedef  unsigned char  byte;
```
- Given the uncertainty over signed-ness, avoid mixed type operations.
  - The implicit conversions will get you in the end.
The Integer Data Type
- Integers come in three sizes and two signs.
  - long, int (the default), and short.
    - There's also long long to give a true long integer.
  - signed (the default) and unsigned.
  - The only thing it's safe to conclude is
```
sizeof(short) <= sizeof(int) <= sizeof(long) < sizeof(long long)
```
    Any other requirements you should establish explicitly in your program (or elsewhere).
```
if sizeof(long long) != 8
  std::cerr "long long ints aren't eight bytes"
  exit(1)
```
- If it's important, declare integer types explicitly.
```
  typedef  signed char  s_1byte
  typedef  short        s_2byte
  typedef  int          s_4byte
  typedef  long long    s_8byte
```
Signed vs. Unsigned Integers
- There are more positive unsigned values than signed values.
  - About twice as many: 127 vs. 255 for 8-bit values.
- This is useful to know if you're counting things.
  - There aren't too many negative things.
- In addition, valid array indices are never negative.
  - Using unsigned array indices may make your indexing problems easier to find.
Integer Overflow and Wrap-Around
- Can either of these code fragments ever print anything?
  i = 65535 j = 1 if (j > i) std::cerr << "?\n";
  
  if (i > i + 1) std::cerr << "!\n";
- Bits can spill-over into the sign bit (in two's compliment representation).
  - Storing 65535 into a (signed) short sets the sign bit, turning the value into -1.
  - Adding one to 32767 carries a one into the sign bit, turning the value negative.
- n-bit numbers can only represent 2ⁿ values.
  - But I can add 1 to a value infinitely many times.
- Unsigned arithmetic is performed modulo the largest representable value.
  - Adding one to that value causes it to wrap-around to zero.
Integer Conversions
- Be careful when using mixed integer types in operations.
- C++ automatically promotes smaller n-bit integral values to int values.
  - This is known as integral promotion.
- Converting larger integer values to smaller integer values is system dependent.
  - Bits are chopped to fit, but which bits?
- Integer operands are promoted to int values, if needed.
  - And then converted to the largest common integral type.
Floating Point
- Floating-point values can represent really big numbers inexactly.
  - And they also represent small values inexactly.
- The floating point types are float, double (the default), and long double.
- Numerical methods studies the properties of floating-point numbers and arithmetic.
- The Golden Rule: Never directly compare two floating-point numbers.
```
if (x > y) { ... }

if (x == y) { ... }
```
- Always compare the difference between two floating-point numbers.
```
if (x - y > 0.001) { ... }

if (tabs(x - y) < 0.0001) { ... }
```

This page last modified on 9 September 2003.