Data Types and Machine Arithmetic

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

## 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)
\begin{align} w = \sum_{i=0}^{N-1} a_{i} 2^{i} \end{align}

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$

Exercise
Give the base-10 value of the unsigned 8-bit integer 1011 1001

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$
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$

# 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 F F T F T T T F T T T F
NOR 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.

## Floating-Point Arithmetic

page revision: 18, last edited: 11 Sep 2018 14:26