The foundation of this material is to enable an easy understanding of the chapter on computer data representation. A basic knowledge of number systems and mathematical logic is necessary.
Number System Numbers have a base. The commonly used one is base 10, or decimal.
Given a number: 5736
Examples of other bases commonly encountered:
- The clock system, which uses base 12.
- Calculating days, which uses base 7 (for example, assuming Sunday=1, Monday=2, ... Saturday=0). In a number system with base N, digits 0,1,...,N-1 are used.
Examples:
- The decimal system (base 10) uses digits 0,1,2,3,...,9.
- The binary system (base 2) uses digits 0 and 1.
If X is a value represented in a base N number system, forming a sequence of digits like (b_i...b_2b_1b_0), then:
In theory, number systems can be created with any base (positive integer >1).
Base Conversion Every specific value or quantity can be represented in various number systems. Therefore, base conversion can also be done.
From Base N to Base 10 Conversion from base N to base 10 can be done using the formula above.
Example:
For digits after the decimal point in fractional numbers, the same formula applies.
Example:
From Base 10 to Base N Conversion from base 10 to base N is done with integer division and modulus (remainder) operations by N. Example:
For digits after the decimal point in fractions, conversion is done by multiplying the fraction by the base. The integer part of the result is then taken.
Example:
Arithmetic in Base N Addition and subtraction can be performed on two numbers in the SAME base. Arithmetic calculations in base N are similar to those in base 10.
If the numbers in the above examples are converted to base 10, the calculated results remain the same.
Basic Mathematical Logic Set Theory A set is a collection of various elements with similar characteristics. A set exists within a particular universe that limits its scope.
Examples:
- Set of positive integers < 10
- Set of prime numbers < 100
- Set of Computer Science students
- etc.
Set Relations
- Set A is a subset of B, (A \subseteq B), if and only if every element of A is also an element of B.
- Set A equals B, (A = B), if and only if (A \subseteq B) and (B \subseteq A).
- The complement of set A, (A = { x | x \notin A }).
Set Combinations There are several types of set relations:
- Union of sets A and B, (A \cup B)
- Intersection of sets A and B, (A \cap B)
- Symmetric difference (not yet discussed).
Example: From the following Venn Diagram:
Set Algebra Here are the basic operations in set algebra:
Logic In mathematical logic, each question or combination of statements has a value of TRUE or FALSE. Statements can be combined in logical operations, with the following basic operations:
Negation (NOT): Gives the opposite truth value of a statement. The truth table for Negation is as follows:
Disjunction (OR): In this operation, if either statement is true, the combination is true. The truth table for Negation is as follows.
Conjunction (AND): In this operation, if either statement is false, the combination is false. The truth table for Negation is as follows.
Boolean Algebra Rules:
Understanding Basic Data Types There are three basic data types in computers:
- Integer numbers
- Floating-point numbers
- Symbols or characters Computers represent data in binary form because each data cell/bit in a computer can only store two states: high voltage and low voltage. This voltage difference represents TRUE and FALSE, or bit '1' and '0'.
Representation of Integer Numbers Unsigned integers can be represented by:
- Binary numbers – octal – hexadecimal
- Gray code
- BCD (Binary-Coded Decimal)
- Hamming code
Signed integers (positive or negative) can be represented by:
- Sign/Magnitude (S/M)
- 1's complement
- 2's complement
For positive integers, there is no difference between the three representations above. In all three representations, the MSB (Most Significant Bit) is used as a sign indicator. The MSB is '0' for positive numbers and '1' for negative numbers.
Sign/Magnitude The negative representation of a number is obtained by changing the MSB of the positive form to 1. If N bits are used to represent data, the representable range is:
Example: if 5 bits are used for number representation
- +3 = 00011
- -3 = 10011
1's Complement The negative representation of a number is obtained by complementing all bits of its positive value. If N bits are used for data representation, the range of values representable is:
Example: if 5 bits are used for number representation
- +3 = 00011
- -3 = 11100
2's Complement The negative representation of a number is obtained by subtracting (2^n) from its positive value. If N bits are used for data representation, the representable range is:
Comparison Below is a comparison table for the three ways of representing signed integers.