|
Table of Contents
|
Most of the optimization methodologies you utilize in creating your data structures, conditional testing, and arithmetic tasks will hinge on the type of data you're handling. There are a multitude of different data types that are set up by default in most languages, and we'll look at those types here, but you can always create your own data types with their own algebra rules as we have done with the Vector3D data type in this course.
Data Types
Characters
Character Arrays
Strings
ASCII vs ANSI vs Unicode
Boolean (Logical)
Integers
Integer data types in C# can be 8, 16, 32, or 64 bits long, and they may either be signed or unsigned. For each of these variations, each bit represents a power of two except for the most significant bit (MSB) which for signed integers also indicates the sign of the number. Before we look at signed integers, let's examine the simpler unsigned integer datatypes first.
Unsigned Integers
The base-10 value of an unsigned integer, $w$, of any number of bits, is the sum of power of two each bit represents. The least significant bit (LSB) represents $2^0$ and the MSB represents $2^{N-1}$ where $N$ is the number of bits used for the integer.
(1)In order of 8, 16, 32, and 64-bit versions, the C# unsigned integer data type classes are byte, ushort, uint, and ulong. For example of how these data types store values in memory, let's keep it small and examine an 8-bit byte value. Storage of the integer value follows the format
| $a_7$ | $a_6$ | $a_5$ | $a_4$ | $a_3$ | $a_2$ | $a_1$ | $a_0$ |
|---|---|---|---|---|---|---|---|
| $2^7$ | $2^6$ | $2^5$ | $2^4$ | $2^3$ | $2^2$ | $2^1$ | $2^0$ |
Let's look at a couple of examples.
Example
Give the base-10 value of the unsigned 8-bit integer 0010 1101.
Populating the definition table show above for a byte data type yields
$a_7$ $a_6$ $a_5$ $a_4$ $a_3$ $a_2$ $a_1$ $a_0$ $0$ $0$ $1$ $0$ $1$ $1$ $0$ $1$ Writing this out as an arithmetic sum of powers of two allows us to then calculate the value.
$w = 0*2^7 + 0*2^6 + 1*2^5 + 0*2^4 + 1*2^3 + 1*2^2 + 0*2^1 + 1*2^0$
$w = 0 + 0 + 32 + 0 + 8 + 4 + 0 + 1$
$w = 45$
Note that the MSB is always $2^{N-1}]$. This means that the maximum value for an N-bit unsigned integer is always $2^{N}-1$Exercise
Give the base-10 value of the unsigned 8-bit integer 1011 1001
| N bits | C# Data Type | Minimum Value | Maximum Value |
|---|---|---|---|
| 8 | byte | 0 | $2^{8}-1 = 255$ |
| 16 | ushort | 0 | $2^{16}-1 = 65,535$ |
| 32 | uint | 0 | $2^{32}-1 = 4,294,967,295$ |
| 64 | ulong | 0 | $2^{64}-1 = 18,446,744,073,709,551,615$ |
Signed Integers
Floating-Point Numbers
Single Precision
Double Precision
Quad Precision
Machine Arithmetic
Boolean Algebra
Understanding Boolean algebra, its rules and theorems, can help you structure your conditional statements (if-then-else) efficiently. Conditional statements can be expensive. Careful structuring of an if-then-else statement can save you a dozen or more CPU instructions. This may not sound like much when you have eight cores each running at 3+ GHz, but if you have to execute that same if-then-else statement on the 10,000 particles in your particle effects systems 60 or more times a second, those extra CPU instructions can add up quickly.
Let's first look at the three basic operators that form the foundation of Boolean algebra: AND, OR, and NOT.
Operators
AND (& and &&)
AND tests to see if two values or expressions are both true. For example, consider the statement C = A && B. C will be true if and only if both A and B are true. If either A or B are false, C will be false. We can summarize this in a table which contains all possible combinations of values for A and B and the resulting value of C. This is called a truth table.
| A | B | A && B |
|---|---|---|
| F | F | F |
| F | T | F |
| T | F | F |
| T | T | T |
OR (| and ∥)
OR tests to see if either or both of the two values or expressions are true. In the expression C = A ∥ B, C will be true any time either A or B or both are true. The only time C will be false is if neither A nor B are true.
| A | B | A ∥ B |
|---|---|---|
| F | F | F |
| F | T | T |
| T | F | T |
| T | T | T |
XOR (^)
An Exclusive OR, XOR, tests to see if one or the other of two values or expressions are true, but not both. In the expression C = A ^ B, C will be true only when either A or B are true, but will be false if neither are true or if both are true. Think of this as the logical equivalent of a three-way light switch.
| A | B | A ^ B |
|---|---|---|
| F | F | F |
| F | T | T |
| T | F | T |
| T | T | F |
NOT (!)
The NOT operation changes the logical value of a variable. If A = True, then !A = False. The NOT operator can be combined with the AND and OR operators to create NAND and NOR operators. In digital electronics, NAND and NOR gates are far more common and easier to construct than their positive AND and OR counterparts.
| NAND | ||
|---|---|---|
| A | B | !(A && B) |
| F | F | T |
| F | T | T |
| T | F | T |
| T | T | F |
| NOR | ||
|---|---|---|
| A | B | (A ∥ B) |
| F | F | T |
| F | T | F |
| T | F | F |
| T | T | F |
With these three operators, we can create complex logic equations to test the state of a system. Let's examine a couple of such equations and their associated truth tables.
Example
Create a truth table for the following expression D = A && (!B ∥ C).
Just like in algebra, there is an order of operations. The NOT operator always takes precedence followed by the AND operator with OR being evaluated last. This default order can be altered by the use of parentheses, as seen in the equation above. In this case, B is negated, followed by !B OR C . That result is then tested via an AND with A. It should also be noted that both the AND and OR operators commute. That is A && B == B && A, and A ∥ B == B ∥ A.
A B C D = A && (!B ∥ C) Reason F F F F A is F, so anything AND A will also be F F F T F A is F, so anything AND A will also be F F T F F A is F, so anything AND A will also be F F T T F A is F, so anything AND A will also be F T F F T !B is T, so anything AND !B will also be T T F T T C is T, so anything AND C will also be T T T F F Neither !B or C are T, so (!B ∥ C) is F T T T T C is T, so anything AND C will also be T
Now that you've seen an example, try to complete the following exercise. Click on the Solution link when you're ready to see the answer and compare your results.
Exercise
Create a truth table for the following expression: D = !(A ∥ B ) && C .
Identities, Axioms, and Theorems
One of the best ways to improve the efficiency of your code is to improve the efficiency of your if-then-else statements. The fewer logical operations and comparisons you need to make, the less CPU time you'll demand during each frame. There are a variety of Identities, Axioms, and Theorems that will enable us to take complex logic equations and simplify them. Here is a list of some common rules.
| Expression | Simplification | Rule Name |
|---|---|---|
| !(!A) | A | Double Negative |
| A && False | False | Annulment |
| A ∥ True | True | Annulment |
| A && True | A | Identity |
| A ∥ False | A | Identity |
| A && A | A | Idempotent |
| A ∥ A | A | Idempotent |
| A && !A | False | Compliment |
| A ∥ !A | True | Compliment |
| !(A && B) | !A ∥ !B | de Morgan’s Theorem |
| !(A ∥ B) | !A && !B | de Morgan’s Theorem |
| A && (B ∥ C) | (A && B) ∥ (A && C) | Distribution |
| A ∥ (B && B) | (A ∥ B) && (A ∥ C) | Distribution |
Let's examine the expression from the previous Exercise and see if it can be simplified using the list of identities and theorems in the table above.
Example
Simplify the expression D = !(A ∥ B ) && C
Using de Morgan's Theorem, we can rewrite the term !(A ∥ B) as !A && !B resulting in the new expression
D = !A && !B && C
Written in this way, we can create a set of nested IF-THEN-ELSE statements that checks !A, !B, and C in turn. Since the only operation between !A, !B, and C is an AND, and the AND operator commutes, we can test these variables in any order that we wish. Also, since this is a series of AND operations, any time that !A, !B, or C are false, the whole statement is false allowing us to check them one at a time and if one check results in a false, we can return the value that D is false without having to check the other variables.
//Test the expression !A && !B && C using a nested set of IF-THEN-ELSE statements public static TestExpression(bool A, bool B, bool C) { if (A == true) { return false; } else { if (B == true) { return false; } else { if (C == false) { return false; } else { return true; } } } }
Notice in the above code, we check to see if A and B are true rather than if !A and !B are false. This eliminates one more operation in each of our checks since if !A is false, then necessarily A is true. This can be further simplified by reducing the IF statements for A and B to if (A) and if (B) since this implicitly tests if A and B are true. We've explicitly included the == true in the above code example for clarity.