Table of Contents

Previous: 1. An Overview of Computer Hardware and Software Systems

Next: 3. Basic Computer Operations

2  Data Representations in Computers

The contents of computer storage are strings of 1's and 0's. Different types of data, e.g., characters, integers, and real numbers, have different representations in computers. In this chapter, we will give an overview of terminologies, called binary prefixes, that quantify computer storage, length, and time. The numeral system frequently used in a computer is not decimal numerals. The most three numeral systems are binary numerals, octal numerals, and hexadecimal numerals. We will explain theses three numeral systems and data representations of characters, integers, and real numbers. Finally, we describe primitive data types of C programming language.

2.1 Binary Prefix

The smallest unit of data storage in a computer is a bit. A single bit has a binary state which is state of 0 or 1, or a true or false, or two mutually exclusive states. A collection of bits, usually of length 8, is called a byte, which is the basic unit of computer storage. Another term "word" refers to a consecutive bytes with the length of CPU's largest register or largest addressable memory location. For example, for IBM-compatible PC's, a word is equivalent to 16 bits, i.e., 2 bytes, due to early Intel 80x86 processors. However, for many recent CPU's, a word is  equivalent to 32 bits or even 64 bits.

There are binary prefixes to quantify large amount of bits, bytes, and words.

The first three names are mostly used in computer science. The term kilo-bytes means 2¹⁰ bytes, i.e., 1,024 bytes, about 1,000 bytes; the term mega-bytes means 2²⁰ bytes, i.e., 1,048,576 bytes, about 1,000,000 bytes; the term giga-bytes means 2³⁰ bytes, i.e., 1,073,741,824 bytes, about 1,000,000,000 bytes. The three terms are usually written in short as KB, MB, and GB, respectively. Hence, a 1.8 KB file means that the file is about of the size 1,800 bytes; a 128 MB RAM means that the memory is about of the size 128,000,000 bytes, a 40 GB hard disk means that the disk is about of the size 40,000,000,000 bytes.

There are also terminologies for quantifying small seconds of time, length, and weight. These terms are expressed in base 10.

One millisecond, 1 ms, is one thousandth of a second, i.e., 10^-3 seconds. One microsecond, 1 ms, is on millionth of a second, i.e., 10^-6 seconds. One nanosecond, 1 ns, is one billionth of a second, i.e., 10^-9 seconds.

Several terminologies are frequently used in computer science. We give some examples below:

2.2  Binary Numerals, Octal Numerals, and Hexadecimal Numerals

The numeral system we use daily is decimal numerals, i.e., base 10 numbers. In the decimal number system, there are ten symbols, 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9, with decimal points and plus (+) and minus (-) signs to express decimal numbers.

Three other numeral systems are used in computer science, binary numerals (base 2), octal numerals (base 8), and hexadecimal numerals (base 16), For binary numerals, there are only two digit symbols 0 and 1. Octal numerals are composed of 8 digit symbols, 0, 1, 2, 3, 4, 5, 6, and 7. Hexadecimal numerals are composed of 16 digit symbols, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, and F. The English digits, A, B, C, D, E, and F, of hexadecimal numerals, denote decimal values 10, 11, 12, 13, 14, and 15, respectively. The following table shows the equivalent values of decimal number, binary numbers, octal numbers, and hexadecimal number from 0₁₀ to 15₁₀.

A decimal number, say 25084, is actually an expression of powers of 10, i.e.,

25084=2´10⁴+5´10³+0´10²+8´10¹+4´10⁰.

Similarly, a binary number, say 101101₂ is actually an expression of powers of 2, i.e.,

101101₂=1´2⁵+0´2⁴+1´2³+1´2²+0´2¹+1´2⁰=45.

Note that when there is a chance of ambiguity, a subscript is used to indicate the base of a number. Often, terms with coefficient 0 are omitted and 101101₂ is written as:

101101₂=1´2⁵+1´2³+1´2²+1´2⁰.

An octal number, say 763₈, is an expression of powers of 8, i.e.,

763₈=7´8²+6´8¹+3´8⁰=499.

A hexadecimal number, say 9E4B₁₆, is an expression of powers of 16, i.e.,

9E4B₁₆=9´16³+14´16²+4´16¹+11´16⁰=40523.

For a number with a fixed length of digits, leading zeros will be added if the length of this number is shorter than the given fixed length. For example, if we designate a binary number of 8 bits, then 101101₂ is often written as 00101101₂. We show examples of converting a number from a numeral system to the other numeral systems.

Example 1: Convert decimal number 40206 to a binary number, an octal number, and a hexadecimal number.

The stepwise conversion to a binary number is illustrated as below:

The stepwise conversion to an octal number is illustrated as below:

The stepwise conversion to a hexadecimal number is illustrated as below:

If the binary number 1001110100001110 is grouped into 3 bits each from left to right, 1 001 110 100 001 110, it is easy to convert each group of  three bits to an octal digit and obtain 116416₈. Similarly, if the binary number 1001110100001110 is grouped into 4 bits each from left to right, 1001 1101 0000 1110, it is easy to convert each group of  four bits to a hexadecimal digit and obtain 9D0E₁₆. Conversely, it is possible to convert a decimal into an octal or a hexadecimal number and then convert each octal digit or hexadecimal digit into binary bits. This procedure requires fewer steps to convert a large decimal number to a binary one.

Similarly to decimal arithmetic operations, we can add and multiply a pair of binary numbers, octal numbers, and hexadecimal numbers. Addition of two binary numbers, 10010010+00111011, is shown as the following:

Addition of two octal numbers, 2614+1356, is similar:

Let us examine the addition operation  2614₈+1356₈ = 1420₁₀ + 750₁₀ = 2170₁₀ = 4172₈. We leave addition of two hexadecimal numbers as exercise.

Multiplication of two binary numbers, 10110´1010, is shown as the following:

Multiplication of octal numbers, we first consider products of two single octal digits, e.g., 5₈´7₈=43₈, 6₈´7₈=52₈, and 3₈´7₈=25₈, and products of multiple digits and a single digit, e.g., 563₈´7₈=4300₈+520₈+25₈=5045₈. Multiplication of two octal numbers 563´247 is illustrated as below:

Binary numbers, octal numbers, and hexadecimal numbers with decimal points are similar to that of decimal numbers. For example, binary fractional number 11.101 is converted to a decimal fractional number as below:

11.101₂=1´2¹+1´2⁰+1´2^-1+0´2^-2+1´2^-3=2+1+0.5+0.125=3.625₁₀.

The conversion of a decimal fractional number to a binary number is done in two steps. First, convert the integer part, and then convert the fractional part. For example, the conversion of 3.625₁₀ to a binary fractional number is done by first converting the integer part 3₁₀ to to 11₂ as before. The second step is to convert the fractional part 0.625₁₀ to a binary fraction. The fraction conversion is described and illustrated below.

Therefore, decimal number 3.625₁₀ is converted to 11.101₂. However, conversion of decimal fractions to binary fractions is not always perfect. Let us try to convert 0.8₁₀ to a binary fraction.

Practically, a decimal fraction is converted to a binary fraction of its approximation with a specific length. For example, if the binary fraction is fixed to 8 bits, 0.8₁₀ is converted to 0.11001100₂ which is actually 0.796875₁₀, an approximation of 0.8₁₀.

Binary numbers with the negative sign are expressed in a specific number of bits, too. We will consider 8-bit signed binary numbers. A positive binary number, say, 37₁₀, is expressed as 00100101₂. There are two methods for representing negative binary numbers. The first representation is one's complement which is the bitwise NOT of a binary number, e.g., -37₁₀ = 00100101₂ = 11011010₂. For 8-bit signed numbers using one's complement, only integers ranges from -127₁₀ (10000000₂) to 127₁₀ (01111111₂) can be expressed. For example, 320₁₀ cannot be expressed as an 8-bit signed binary number, since 320₁₀ = 1 0100 0000₂ which requires at least 9 bits. In one's complement, the most significant bit is used as the sign bit. If the most significant bit is 0, the binary number is a positive number; if the most significant bit is 1, the binary number is a negative number. One's complement has a drawback of two zero's, 00000000₂ and 11111111₂.

The second representation of signed binary numbers is two's complement. For an 8-bit binary number, the most significant bit is used as the sign bit. The representation of a negative binary number using two's complement is taking the one's complement of its absolute value then adding one to it. For example, -37₁₀ = 00100101₂ + 1₂ = 11011010₂ + 1₂ = 11011011₂. For 8-bit signed numbers using two's complement ranges from -128₁₀ (10000000₂) to 127₁₀ (01111111₂). Note that there is no 128₁₀ of 8-bit two's complement binary numbers.

Two's complement representation is suitable for binary number arithmetic. Consider 8-bit signed binary numbers. Addition of two positive numbers is the same as the previous case 27₁₀ + 12₁₀ = 00011011₂ + 00001100₂ = 00100111₂. Additions of negative numbers are illustrated as below:

Subtraction of two positive numbers is first converting the second operand using two's complement than adding the two numbers. For example,

27₁₀-12₁₀=27₁₀+(-12₁₀)=00011011₂+11110100₂=00001111₂=15₁₀.

However, the following addition results in an error of overflow. It is considered as an invalid operation.

Multiplication of negative numbers is to convert negative operand(s) to its/their absolute values, to calculate the product of two positive numbers, and then to convert the product back to its two's complement representation if only one of the operands is negative.

2.3  Characters

Characters are represented in a computer as a bit string. The most popular encoding scheme of English characters is ASCII encoding (American Standard Code for Information Interchange). Each character of ASCII code occupies one byte, but only seven bits are used. The most significant bit of ASCII code is always 0. The character set ASCII code is divided into two categories: control characters (in green color) and printable characters (in blue color). The printable characters range from decimal values 32 to 126. The table of ASCII code is shown as below.

A computer does not process only English text that it must be able to deal with text in other languages such as Chinese, Japanese, and Spanish. To accommodate other languages, various character encoding schemes have been developed. For examples, two Chinese character encoding schemes are used in different area,  Big5 for original Chinese characters, GB for simplified Chinese characters.  Big5 and GB are all 16-bit encoding schemes.

Unicode is an international standard of character encoding of all human written languages developed by International Organization for Standardization (ISO). Unicode has been adopted by many computer systems to support multilingual environments, including Microsoft windows such as Windows NT, Windows 2000, Windows XP, Unix based operating system such as GNU/Linux, BSD, Mac OS X. Unicode is designed as both 8-bit, UTF-8, and 16-bit, UTF-16, coding schemes for different languages.

2.4  Integers

In mathematics, the set of integers have infinite number of elements. However, a computer has only finite resource, a given size of memory storage,  that it is not possible to represent all integers in a computer. There are two basic types of integer representations: unsigned and signed integers.

Unsigned integers are non-negative integers and are represented in their binary values with a fixed number of bits. For Intel 80x86 processors, a word is 16 bit long and an integer is represented as a 16-bit binary numbers. However, the 16-bit string is too long to read. For easy reading, a 16-bit binary number is usually written as a four-digit hexadecimal number. For example, 5876 is represented as binary number 0001 0110 1111 0100 and is written as hexadecimal number 16F4. Another example, 39741 is represented as binary number 1001 1011 0011 1101 and hexadecimal number 9B3D. Note that the most significant bit of 39741 is one, but it is a positive integer. For 16-bit unsigned integers, the values range from 0 to 2¹⁶-1 (65535₁₀).

Signed integers are zero, negative, and positive integers and are represented using two's complement. For a 16-bit processor, the most significant bit is used as the signed bit. The values a signed integer range from -2¹⁵ (-32768₁₀) to 2¹⁵-1 (32767₁₀). Usually, the representation of a signed integer is expressed in hexadecimal numbers for easy reading. Positive integer 5876₁₀ is still represented as  16F4₁₆. However, 39741₁₀ is too large to be represented as a 16-bit signed integer; its corresponding hexadecimal number 9B3D₁₆ is indeed the two's complement of signed negative integer -25795₁₀.

2.5  Real Numbers

Real numbers are represented in a computer using two method: fixed-point format and floating-point format. In a computer, it is not possible to represent a real number precisely. For example, 1/3 is 0.3333.... that cannot be exactly stored in a finite length of memory storage. Both fixed-point numbers and floating-point numbers are only approximation of real numbers.

The representation of fixed-point numbers uses a specific number of bits that part of the bits are used to store the integer part and the rest of the bits are used to store the fractional part after the decimal point. Consider 16-bit representation of fixed-point numbers that the higher eight bits are the integer part and the lower eight bits are the fractional part. For example, fixed-point number 0100 0011 1001 0100 is the representation of

For signed fixed-point numbers, a bit is used to represent the plus and minus sign. In the case of 16-bit processors, only 15 bits are left to store the integer and fractional parts, e.g., 7 bits for the integer part and 8 bits for the fractional part.. To express a decimal numbers in the fixed-point format, the decimal real number is converted to a binary number with decimal points with the specified bit length. The decimal real number -18.625₁₀ is converted to -10010.101₂ and its fixed-point representation is 1 0010010 10100000.

A floating-point number contains three parts: a sign, an exponent, and a fraction. Floating point numbers are written in the scientific notation: ±fractionEexponent. For examples, 1.432456E5 means 1.432456´10⁵=143245.6 and 3.214065E-3 means 3.214065´10^-3=0.003214065.

In a computer, floating point number representation uses scientific notation of the binary number system. A popular standard of floating-point number representation is IEEE 754. The 32-bit single precision floating-point format of IEEE 754 is shown as below:

where the most significant bit (bit 31) denotes the sign bit, bits 23 to 31 are exponent bits, and bits 0 to 22 are fraction bits. These three parts have the following meanings:

1. The sign bit is either 0 or 1 that denotes positive or negative floating point numbers, respectively.

2. The 8-bit exponent (bits 23 to 31) has values ranged from 1 to 254 (0 and 255 are not used) with bias 127, i.e., the actual exponent value is the value of the 8-bit exponent e₇e₆e₅e₄e₃e₂e₁e₀ subtracted by 127.

3. The 23-bit fraction (bits 0 to 22) is the value of a binary fraction, i.e., the fractional value has the integer part of value 1 and the fractional part is f₂₂f₂₁f₂₀f₁₉f₁₈f₁₇f₁₆f₁₅f₁₄f₁₃f₁₂f₁₁f₁₀f₉f₈f₇f₆f₅f₄f₃f₂f₁f₀.

Let sing(s) be the plus sign (+), if the sign bit is 0, and be the minus sign (-), if the sign bit is 1. Let e be the binary number e₇e₆e₅e₄e₃e₂e₁e₀. Also, let f be the binary fractional number 0.f₂₂f₂₁f₂₀f₁₉f₁₈f₁₇f₁₆f₁₅f₁₄f₁₃f₁₂f₁₁f₁₀f₉f₈f₇f₆f₅f₄f₃f₂f₁f₀. The floating point number of 32-bit IEEE 754 standard is calculated as

sign(s) (1 + f) ´ 2^{e - 127}.

The value of 0 01111011 01100000000000000000000 is

1.011₂ ´ 2^123-127 = 1.011₂  ´ 2^-4 = 0.0001011₂ = 0.0859375₁₀,

where the exponent 01111011₂ equals to 123₁₀. The value of 1 10000101 10110000000000000000000 is

-1.1011₂ ´ 2^133-127 = -1.1011₂ ´ 2⁶ = -1101100₂ = -108₁₀,

where the exponent 10000101₂ equals to 133₁₀.

To express a decimal numbers in the floating-point format, the decimal number is converted to a binary number with decimal points. Then calculate the exponent part and the fraction part. Consider the decimal number -18.625₁₀.

 -18.625₁₀ = -10010.101₂ = -1.0010101₂ ´ 2⁴.

We obtain the results that the sign bit is 1, the exponents is 4 +127 = 131₁₀ = 10000011₂, and the fraction is 0010101. The floating-point representation of -18.625 is written as 1 10000011 00101010000000000000000. If both the exponent part and the fraction part are 0, the floating point number is 0.

2.6  Primitive Data Types in C

A C program contains a number of variables each of which represents a memory location. (Issues on program variables will be discussed in Section 3.3.) Each  program variable must be declared as an instance of a data type. Three basic types are supported in C programming language, characters, integers, and floating-point numbers. Integer and  floating-point types have several variations. The primitive data types, sizes (in bytes), and value rages are listed in the following table:

The size of a data type depends on the size of a computer's CPU. The sizes in the above table may vary from one computer to another. The following C program size_of.c outputs the size of each data type using a C library function sizeof() which receives a type name and returns the number of bytes of that type.

The output of size_of.c is shown as below:

Character Data Type

In C programs, a character constant is expressed with a pair of single quotation, e.g., 'A', 'a', ';', etc., and is encoded using ASCII encoding scheme. Most of the printable characters can appear as a character by itself. However, a small set of characters must be attached a backslash symbol at the front to form a character in order to avoid ambiguity. A character with a backslash at the front is called an escape sequence. Escape sequences including some control characters of C programming language is listed below:

In C programs, a string is declared as an array of multiple characters ending with a null character. (Arrays will be discussed in details in Section 5.2.) Program characters.c manipulates a string and prints out the original and new string. Line 4 declares string as an array of 10 characters and assign the initial values as ABC. Line 6 outputs the original string. Lines 7 through 13, change the contents of string.

Octal number 131₈ is the ASCII code of character Y and hexadecimal number 5A₁₆ is the ASCII code of character Z. Hence,  Lines 11 and 12 are equivalent to:

In C programming language, characters are treated as integers, i.e., it is possible to do arithmetic operation on characters. Hence, Lines 11 and 12 can be written with character arithmetic operations:

The content of character array string is shown below:

The ASCII code has the values ranged from 0 to 127. Since a character is of size 8 bit, its values are ranged from -128 to 127. In another words, it is possible to store multi-byte characters, such as Chinese characters, in a character string. However, C programming language does not allow direct assignment of a multi-byte character to a character variable or array. For example the assignment

will cause compiler warnings (in the gray color background) using Dev-C⁺⁺:

To read multi-byte character strings, a program can use scanf() or functions in standard library string.h. Program character_big5_encoding.c reads a string and outputs the hexadecimal values of each character code.

From the input string and output codes, it is easy to observe that 資 is encoded to B8EA, 訊 is encoded to B054, 工 is encoded to A475, 程 is encoded to B57B, 學 is encoded to BEC7, and 系 is encoded to A874, using Big5 encoding scheme. This encoding can be verified using program character_big5_decoding.c:

Integer Data Type

Integer types in C have many variations. The most commonly used type is int. All signed integer types are stored using two's complement and the size and range are listed in the table of primitive types. Program integer_max_min.c shows the maximum and minimum values of type int.

The next program integer_short_long.c shows that assigning a variable of the normal integer type to a variable of the short integer type (Line 10) may cause the overflow problem. But, it is not a problem of assigning a variable of the normal integer type to a variable of the long integer type (Line 12) is allowed.

Floating-point Data Type

Floating-point numbers in C program can be printed in the fixed-point format or floating-point format. Program float_format.c shows the output of 134.56789 in fixed-point format (Line 7) and floating-point format (Line 8). Also, note that the output values are not exactly 134.5678 since floating-point representation is only an approximation. This fact will make equality test of floating numbers more complicated. We will discuss this issue in Section 4.2.

Additional format specification can be added to an integer specifier or a floating-point specifier to make the output more friendly. For example, %4d will output an integer occupying at least four character positions by filling spaces at the left-hand-side, if the length of the integer (including sign symbol) is less than 4; the output will occupy whatever the length of the integer, if this length is greater than or equal to four. Specifier %6.2f will print a floating point number of minimum width six positions such that at least three integer digits, the decimal point, and two fractional digits (two-digit precision). Program specifier.c shows some examples of length and precision format. Lines 5 and 6 produce the first two output lines which have two spaces at the beginning and Line 7 produces the third output line which occupies five character positions. Lines 8 and 9 generates the fourth and fifth output lines which has a space at the beginning and each floating-point number has two fractional digits. The output of Line 10 has total seven characters.

In the theory of programming languages, a strongly typed language allows a compiler to check type errors during compile time. However, C programming language is not strictly confined to strongly type checking for it allows assignment of variables of different type to each other. Program primitve_type_not_casting.c tries to print variables of character type, integer type, and floating-point type. The program goes through compilation without any error, but the output shows some of the values have incorrect results.

The output shows printing a character as an integer (Line 9) or an integer as a character (Line 12) yields a correct answer. However, printing a character or an integer as a floating-point number (Lines 10 and 13) or printing a floating-point number as a character or an integer (Lines 15 and 16) will yield and incorrect answer.

To ensure program correctness, proper type casting (鑄型) must be added in front of a variable. Type casting is explicitly to add the name of the intentional type in front of a variable or an expression that it will converted to. For example, in Lines 10 and 12 of program primitve_type_casting.c, character variable c and integer variable i are explicitly casted to type float. In Lines 15 and 16, float-point variable r is casted to type char and int.

The output of program primitve_type_casting.c is shown as below:

With proper castings, the output gives correct values. Character A is converted to floating-point number 6.500000E+001 and integer 49 is converted to floating-point number 4.900000E+001. When a floating-point number is casted to char or int, its fractional part is simply removed. Integer 97 is exactly the decimal value of ASCII code of character a. Of course, the floating point numbers can be printed using fixed-point specifier %f.

Table of Contents

Previous: 1. An Overview of Computer Hardware and Software Systems

Next: 3. Basic Computer Operations