C++ Programming/Chapter Learning the Basics

A Wikibookian has nominated this page for cleanup. You can help make it better. Please review any relevant discussion.

A Wikibookian has nominated this page for cleanup. You can help make it better. Please review any relevant discussion.

The Binary Number System

Most computer systems operate using binary logic. The computer represents value using two voltage levels, usually 0V for logic 0 and either +3.3V or +5V for logic 1. These two voltage levels represent exactly two different values and by convention, the values are zero and one. These two values coincidentally, correspond to the two digits used by the binary number system. Since there is a correspondence between the logic levels used by the computer and the two digits used in the binary numbering system, it should come as no surprise that computers employ the binary system.

Binary Number Formats

The binary number system uses base 2 which includes only the digits 0 and 1.

In the United States among other countries, every three decimal digits is separated with a comma to make larger numbers easier to read. For example, 123,456,789 is much easier to read than 123456789. We adopt a similar convention for binary numbers. In order to make binary numbers more readable, we add a space every four digits starting from the least significant digit, on the left of the decimal point. For example, the binary value 1010111110110010 will be written as 1010 1111 1011 0010.

Using the above example 1010 1111 1011 0010:

• The rightmost sequence (0010) is in bit position zero, holding value 0. Bit zero is referred to as the least significant bit, or lsb
• Each bit to the left is given the next successive bit number. bit 1, bit 2 and so on...
• The left-most bit (1010) is typically called the most significant bit, or msb, holding value 1.

We typically write binary numbers as a sequence of bits. There are defined boundaries for the different sizes of a bit:

Name	Size (bits)	Example
Bit	1	1
Nibble	4	0101
Byte	8	0000 0101
Word	16	0000 0000 0000 0101
Double Word	32	0000 0000 0000 0000 0000 0000 0000 0101

In any number base, we may add as many leading zeroes without ever changing its value, but in the binary number system, adding leading zeroes adjusts the bit to a desired size. For example, we can represent the number 5 as a:

Bit 101;

Nibble 0101;

Byte 0000 0101;

Word 0000 0000 0000 0101; or

Double Word 0000 0000 0000 0000 0000 0000 0000 0101

Notes on Names

The Word

The boundary for a Word can be defined as either 16-bits or the size of the data bus for the processor. Therefore, a Word and Double Word is not a fixed size but varies from system to system - depending on the processor.

For the 8085 and 8086 microprocessors, a word is a group of 16 bits. We number the bits in a word starting from bit zero (b0) through fifteen (b15) as follows:

b15

b14

b13

b12

b11

b10

b9

b8

b7

b6

b5

b4

b3

b2

b1

b0

Remember, b0 is the LSB and b15 is the msb and when referencing the other bits in a word use their bit position number. Notice that a word contains exactly two bytes. b0-b7 form the low order byte, b8-b15 form the high order byte. Naturally, a word may be further broken down into four nibbles. Nibble zero is the low order nibble (b0-b4) and nibble three is the high order nibble (b12-b15) of the word. The other two nibbles are "nibble one" and "nibble two".

With 16 bits, you can represent 2^16 or 65,536 different values. These could be the unsigned numeric values in the range of 0 => 65,535, signed numeric values which include both positive and negative values in the range of -32,768 => +32,767, or any other data type with no more than 65,536 values. The three major uses for words are

• 16-bit integer data values
• 16-bit memory addresses
• any number system requiring 16 bits or less

The Double Word

A double word is exactly that, two words, so a double word quantity is 32 bits. Naturally, this double word can be divided into a high order word and a low order word, four bytes, or eight nibbles.

Double words can represent all kinds of different data:

• an unsigned double word in the range of 0 => 4,294,967,295
• a signed double word in the range - 2,147,483,648 => +2,147,483,647
• a 32-bit floating point value
• any data that requires 32 bits or less

Number Base Conversion

Binary to Decimal

It is very easy to convert from a binary number to a decimal number.

For example let's breakdown the binary value 1100 1010:

digit	1	1	0	0	1	0	1	0
bit number	b7	b6	b5	b4	b3	b2	b1	b0
base 2	2^7	2^6	2^5	2^4	2^3	2^2	2^1	2^0

Now just like the decimal system, we multiply each digit by base 2 and its weighted position value, then find the sum, like this:

1(2^7)	1(128)	128
1(2^6)	1(64)	64
0(2^5)	0(32)	0
0(2^4)	0(16)	0
1(2^3)	1(8)	8
0(2^2)	0(4)	0
1(2^1)	1(2)	2
0(2^0)	0(1)	0
		=202

Decimal to Binary

To convert from decimal to binary is slightly more difficult.

There are two methods, division by 2 and subtraction by the weighted position value.

The Division Method

For this, we divide the decimal number by 2, if the remainder is 0 write down a 0. If the remainder is 1, then write down a 1. This process is continued until the quotient is 0.

The remainders will represent the binary equivalent of the decimal number. The remainder values are written from the least significant digit to the more significant digit. So each new remainder value is written to the left of the previous.

For example, consider the number 2671.

Division	Quotient	Remainder	Binary Number
2671 / 2	1335	1	1
1335 / 2	667	1	11
667 / 2	333	1	111
333 / 2	166	1	1111
166 / 2	83	0	0 1111
83 / 2	41	1	10 1111
41 / 2	20	1	110 1111
20 / 2	10	0	0110 1111
10 / 2	5	0	0 0110 1111
5 / 2	2	1	10 0110 1111
2 / 2	1	0	010 0110 1111
1 / 2	0	1	1010 0110 1111

The Subtraction Method

Start with a weighted position value greater than the number. If the number is less than the weighted value, write down a 0 and subtract 0. If the number is greater than the weighted value, write down a 1 but subtract the weighted value instead. This process is continued until the result is 0.

When performing the subtraction method, the digits will represent the binary equivalent of the decimal number from the most significant digit to the lesser significant digit. So each new digit is written to the right of the previous.

Consider the same number, 2671

Weighted Value	Subtraction	Remainder	Binary Number
2^12 = 4096	2671 - 0	2671	0
2^11 = 2048	2671 -2048	623	01
2^10 = 1024	623 - 0	623	010
2^9 = 512	623 - 512	111	0101
2^8 = 256	111 - 0	111	0 1010
2^7 = 128	111 - 0	111	01 0100
2^6 = 64	111 - 64	47	0 1010 01
2^5 = 32	47 - 32	15	0 1010 011
2^4 = 16	15 - 0	15	0 1010 0110
2^3 = 8	15 - 8	7	0 1010 0110 1
2^2 = 4	7 - 4	3	0 1010 0110 11
2^1 = 2	3 - 2	1	0 1010 0110 111
2^0 = 1	1 - 1	0	0 1010 0110 1111

The Octal Number System

Although this was once a popular number base, especially in the Digital Equipment Corporation PDP/8 and other old computer systems, it is rarely used today. The Octal system is based on the binary system with a 3-bit boundary.

The Octal system uses base 8 which includes only the digits 0,1,2,3,4,5,6 and 7 (any other digit would make the number an invalid octal number).

Octal digits in binary form

Octal Digit	Binary Number
0	000
1	001
2	010
3	011
4	100
5	101
6	110
7	111

And now the weighted values for each octal position

8^6	8^5	8^4	8^3	8^2	8^1	8^0
262144	32768	4096	512	64	8	1

Binary to Octal Conversion

It is easy to convert a binary value to an octal number.

First, break the binary number into 3-bit sections from the LSB to the MSB then convert the 3-bit binary number to its octal equivalent.

Let's breakdown the binary value 1010111110110010:

3-bit	001	010	111	110	110	010
	MSB					LSB
Octal Digit	1	2	7	6	6	2

Octal to Binary Conversion

It is also easy to convert from an octal number to a binary value.

Convert the decimal number to its 3-bit binary equivalent, then combine the 3-bit sections.

Let's take the above octal number, 127662 and break it down:

Octal Digit	3-bit
1	001
2	010
7	111
6	110
6	110
2	010

This yields the binary number 001010111110110010 or 0000 1010 1111 1011 0010 in our more readable format.

Octal to Decimal Conversion

To convert from Octal to Decimal, multiply the value in each position by its Octal weight and add each value.

Again, let's take the Octal value, 127662

1(8^5)	1(32768)	32768
2(8^4)	2(4096)	8192
7(8^3)	7(512)	3584
6(8^2)	6(64)	384
6(8^1)	6(8)	48
2(8^0)	2(1)	2
		=44978

Decimal to Octal Conversion

To convert decimal to octal is slightly more difficult.

The typical method to convert from decimal to octal is repeated division by 8. For this method, divide the decimal number by 8, and write the remainder on the side as the least significant digit. This process is continued by dividing the quotient by 8 and writing the remainder until the quotient is 0. When performing the division, the remainders which will represent the octal equivalent of the decimal number are written beginning at the least significant digit (right) and each new digit is written to the next more significant digit (the left) of the previous digit. Consider the number 44978.

Division	Quotient	Remainder	Octal Number
44978 / 8	5622	2	2
5622 / 8	702	6	62
702 / 8	87	6	662
87 / 8	10	7	7662
10 / 8	1	2	27662
1 / 8	0	1	127662

As you can see, we are back with the original number.

Hexadecimal Number System

A big problem with the binary system is verbosity. For example, eight binary digits are required to represent the value 202 while the decimal version requires only three decimal digits. Especially with large values, binary numbers become too unwieldy. The hexadecimal numbering system solves these problems.

Hexadecimal numbers are very compact and it is easy to convert from hex to binary and binary to hex. Since we'll often need to enter hexadecimal numbers into the computer system, we need a different mechanism for representing hexadecimal numbers since you cannot enter a subscript to denote the radix of the associated value.

The Hexadecimal system is based on the binary system using a Nibble or 4-bit boundary. In Assembly Language programming, most assemblers require the first digit of a hexadecimal number to be 0, and we place an H at the end of the number to denote the number base.

The hexadecimal number system uses base 16, which includes only the digits 0 through 9 and the letters A, B, C, D, E, and F.

This table provides all the information you'll ever need to convert from one number base into any other number base for the decimal values from 0 to 16.

Decimal	Hex	Binary	Octal
00	00H	0000	00Q
01	01H	0001	01Q
02	02H	0010	02Q
03	03H	0011	03Q
04	04H	0100	04Q
05	05H	0101	05Q
06	06H	0110	06Q
07	07H	0111	07Q
08	08H	1000	10Q
09	09H	1001	11Q
10	0AH	1010	12Q
11	0BH	1011	13Q
12	0CH	1100	14Q
13	0DH	1101	15Q
14	0EH	1110	16Q
15	0FH	1111	17Q
16	10H	1 0000	20Q

Hexadecimal to Binary

To convert a hexadecimal number into a binary number:

1. Breakdown the hexadecimal number into each individual Hexa digit

2. Substitute the corresponding binary value for each Hexa digit

3. Each binary value is written from the beginning of the MSB (left) to the LSB (right)

For example, to convert 0ABCDH into a binary value, simply convert each hexadecimal digit according to the table above.

Hexa Digit	Binary Value
0	0000
A	1010
B	1011
C	1100
D	1101

0ABCDH = 0000 1010 1011 1100 1101

Binary to Hexadecimal

To convert a binary number into the hexadecimal format is almost as easy.

For example, given the binary number 1011001010, the first step would be to add two zeros in the MSB position so that it contains 12 bits. Then separate the binary value into groups of four bits, so the revised binary value reads 0010 1100 1010. Then we look up the binary values in the table above and substitute the appropriate hexadecimal digit:

0010	2
1100	C
1010	A

Therefore 0010 1100 1010 = 2CA

Another example, 1010111110110010 converts into AFB2.

Hexadecimal to Decimal conversion

The weighted values for each position is as follows:

16^0	1
16^1	16
16^2	256
16^3	4096

To convert from Hex to Decimal, multiply the value in each position by its weighted value then add. Using the table above and the previous example, 0AFB2H, we expect to obtain the decimal value 44978.

A(16^3)	10(4096)	40960
F(16^2)	15(256)	3840
B(16^1)	11(16)	176
2(16^0)	2(1)	2
		=44978

Decimal to Hex

To convert from decimal to hex is slightly more difficult. The typical method is repeated division by 16.

While we may also use repeated subtraction by the weighted position value, it is more difficult for large decimal numbers.

The Division Method

Divide the decimal number by 16, and write the remainder on the side as the least significant digit. This process is continued until the quotient is 0. When performing the division, the remainders which will represent the hex equivalent of the decimal number are written beginning at the least significant digit (right) and each new digit is written to the next more significant digit (the left) of the previous digit. Consider the number 44978.

Division	Quotient	Remainder	Hex Number
44978 / 16	2811	2	2
2811 / 16	175	11	B2
175 / 16	10	15	FB2
10 / 16	0	10	0AFB2

44978 = 0AFB2

When you use hex numbers in an 8085 program, the Assembler usually requires the most significant hex digit to be 0 even if this number of digits exceed the size of the register. This is an Assembler requirement and your value will be assembled correctly.

Hex Addition

Add as if decimal numbers, except:

If individual digits are A through F, we must convert to its decimal equivalent (values from the table above) then add.

For example:

find the sum of D + C

0DH = 13 and 0CH = 12 so;

13 + 12 = 25 therefore;

D + C = 25 but;

If the sum is greater than or equal to 16, we replace the sum with the sum minus 16 and carry over 1.

For example:

25 - 16 = 9; then

D + C = 19; and finally

3) if the sum is between 10 and 15 (decimal), we replace the sum with the equivalent hexadecimal digit, for example:

carries	-->	1 1
		DF6D
	+	246C
overflow	--> 1	03D9

More examples of binary and hex addition:

carries	-->		11111
			111011
		+	100111
overflow	-->	1	100010

carries	-->		1 1
			11001
		+	01101
overflow	-->	1	00110

		1235
	+	567A
no overflow	-->	68AF

carries	-->		111
			A9876
		+	FDCA0
overflow	-->	1	A7516

Conversion Between Different Number Systems

Positional number systems

Our decimal number system is known as a positional number system because the value of the number depends on the position of the digits. For example, the number 123 is different from 321 even though the same digits are used. Other ancient number systems used additional symbols to represent larger values, but in a positional number system the value of each digit is determined by its place in the full number. The lowest place value is the rightmost position, and each successive position to the left has a higher place value. The rightmost position represents the "ones" column, the next position represents the "tens" column, the next position represents "hundreds", etc. Therefore, the number 123 represents 1 hundred and 2 tens and 3 ones, whereas the number 321 represents 3 hundreds and 2 tens and 1 one.

The values of each position correspond to powers of the base of the number system. So for our decimal number system, which uses base 10, the place values correspond to powers of 10:

10^0	= 1
10^1	= 10
10^2	= 100
10^3	= 1000

Converting from other number bases to decimal

Other number systems use different bases. The binary number system uses base 2, so the place values of the digits of a binary number correspond to powers of 2.

For example, the value of the binary number 10011 is determined by computing the place value of each of the binary digits of the number:

1	0	0	1	1	the binary number
(2^4)	(2^3)	(2^2)	(2^1)	(2^0)	place values

So the binary number 10011 represents the value

1 (2^4)	+ 0(2^3)	+ 0 (2^2)	+ 1 (2^1)	+1 ( 2^0)
= 16	+ 0	+ 0	+ 2	+ 1
= 19

The same principle applies to any number base. For example, the number 2132 base 5 corresponds to

2	1	3	2	number in base 5
(5^3)	(5^2)	(5^1)	(5^0	place values

So the value of the number 2132 base 5 is

2(5^3)	+1(5^2)	+3(5^1)	+2(5^0)
=2(125)	+1(25)	+3(5)	+2(1)
= 250	+25	+15	+2
= 292

Converting from decimal to other number bases

In order to convert a decimal number into different number bases, we have to be able to express the number in terms of powers of the other base. To convert the decimal number 100 to base 4, we must figure out how to express 100 as the sum of powers of 4, for example:

100=	1(64)	+ 2(16)	+ 1(4)	+ 0(1)
	= 1(4^3)	+ 2(4^2)	+ 1(4^1)	+ 0(4^0)

Then we use the coefficients of the powers of 4 to form the number as represented in base 4:

100

= 1

2

1

0

base 4

Another method is to repeatedly divide the decimal number by the base in which it is to be converted until the quotient becomes zero. As the number is divided, the remainders - in reverse order - form the digits of the number in the other base. For example:

Convert the decimal number 82 to base 6:

82/6	= 13 remainder 4
13/6	= 2 remainder 1
2/6	= 0 remainder 2

The answer is formed by taking the remainders in reverse order: 2 1 4 base 6

Example conversions between number systems:

Decimal	Binary	Hex
255	1111 1111	FF
93	0101 1101	5D

Fixed length binary numbers

Computer arithmetic is performed on data stored in fixed length memory locations, typically 8, 16, or 32 bits.

Special problems occur in manipulating fixed length numbers. The number 280 (base 10) is larger than the maximum 8-bit number; this results in a carry beyond 8 bits in the binary representation and a carry beyond two digits in the hexadecimal representation. When doing arithmetic using fixed length numbers, these carries are potentially lost.

Decimal	Binary	Hex
201	11001001	C9
+79	+01001111	+4F
280	1 00011000	1 18

Negative numbers

Signed magnitude - Use one bit for sign, 7 bits for number.

Example: -1 (in an 8-bit system) could be 1000 0001 (base 2)

2's complement (most often used in computing)

Example: the 2's complement number representing -1 (in an 8-bit system) would be 1111 1111 (base 2)

Complement numbers

Consider odometer numbers on a bicycle: Consider odometer numbers on a bicycle:

Decimal examples Odometer numbers are useful for both addition and subtraction (complements) of signed numbers. - 2 + 998 + 3 + 003 + 1 1 001

In the second example, the correct result is just the +001; the overflow is ignored in fixed-length complement arithmetic. Do subtraction as addition by using complements, i.e. A - B = A + (-B) Important: It is easier to compute -B and add than to subtract directly. Example: - 005 + 995 + 003 + 997 + 008 1 992

Note that 995 and 997 were added in the normal fashion, the overflow was ignored, and the result was 992, which can be converted from the complement (or odometer) system back to -8, the correct answer.

signed   3-bit complement
    +3   003
    +2   002
    +1   001
     0   000
    -1   999
    -2   998
    -3   997
    -4   996
    -5   995
    -6   994
    -7   993
    -8   992

decimal 2's complement binary

  +127   01111111
  +126   01111110
  +125   01111101
   ...   ........
    +2   00000010
    +1   00000001
     0   00000000
    -1   11111111
    -2   11111110
   ...   ........
  -127   10000001
  -128   10000000

There are 256 numbers in an 8-bit fixed length 2's complement number system. Why are these numbers called 2's complement? M - N = M + (-N) where -N is the complement of N.

Example: decimal

   + 1   =     00000001
   - 1   =   + 11111111
     0   =   1 00000000

which does not equal 2^8, or 256; ignore the overflow, and the correct answer is zero. Now we need an easy way to do 2's complement operations.

Example: What is the representation of -27 (base 10) in 2's complement 8-bit notation?

 2^8 - 1     11111111

- 27 - 00011011

             11100100   corresponds to flipping all the bits;
                        also known as 1's complement
   add 1   + 00000001
  result     11100101   -27 in 2's complement representation

This approach is necessary because: 1. Fixed-length nature of numbers stored in a computer 2. More computationally efficient to implement a fast adder than an adder and a subtractor ________________________________________ Examples of 2's complement number operations Addition and subtraction in 2's complement form • Addition: To compute N1 + N2, add N1 to N2 • Subtraction: To compute N1 - N2, add N1 to -N2 Examples: decimal binary hex

   11   =     00001011   =     000B
 + 21   =   + 00010101   =   + 0015
   32   =     00100000   =     0020

   21   =     00010101   =     0015
 - 11   =   + 11110101   =   + FFF5
   10   =     00001010   =     000A

   11   =     00001011   =     000B
 - 21   =   + 11101011   =   + FFEB
 - 10   =     11110110   =     FFF6

 - 11   =     11110101   =     FFF5
 - 21   =   + 11101011   =   + FFEB
 - 32   =   1 11100000   =     FFE0

How we got the 2's complements of -11 and -21:

11     00001011

~11 - 11110100 1's complement + 1 + 00000001 add 1 -11 11110101 2's complement representation

Algorithm 1. Store N. 2. Obtain ~N, the 1's complement of N, by replacing (bit by bit) every 0 with a 1 and vice versa in the number's binary representation. 3. Add 1 and ignore any carry after the eighth bit. Note: This algorithm works in hex by replacing each digit x with its hex complement, i.e. 15 - x. Example: The hex equivalent of 11 is $000B; its hex complement is then $FFF4, where each digit was computed as $F - x. Adding 1 to $FFF4 gives the result $FFF5 for the 2's complement of 11. (Using a dollar sign ($) before a number indicates that it is base 16.) Example: In binary:

N     0000 0110 0100 0111

~N - 1111 1001 1011 1000 1's complement +1 + 0000 0000 0000 0001 add 1 -N 1111 1001 1011 1001 2's complement representation

In hex:

N     0647

~N - F9B8 1's complement +1 + 0001 add 1 -N F9B9 2's complement representation

A calculator will always give you the 2's complement directly. The Most Significant Bit (MSB) is the binary digit corresponding to the largest power of 2 and is always 1 for a negative 2's complement number. As a result it is often called the sign bit. In 2's complement, -0 = +0. Technically, 0 is the complement of itself.

N     00000000

~N - 11111111 1's complement +1 + 00000001 add 1 -N 00000000 2's complement representation

________________________________________ Problems with fixed-length arithmetic Overflow and underflow For a 16-bit fixed-length number system,

Adding signed numbers can easily exceed these limits. first digit

      0011   $3000
      0110   $6000
      1001   $9000

This result, from adding two positive numbers in the number system, results in $9000, which is larger than $7FFF, the largest allowed positive number. In fact, $9000 equals 1001 0000 0000 0000, which is a negative number. The sign of the result is different from that of the operands. Rule: If there is a sign change in adding two positive 2's complement numbers, then overflow has occurred. We can generalize these rules to signed addition and subtraction.

Sign extension How about if numbers are of different length? decimal 2's complement binary

         3-bit 4-bit  8-bit
    +3   011   0011   00000011
    +2   010   0010   00000010
    +1   001   0001   00000001
     0   000   0000   00000000
    -1   111   1111   11111111
    -2   110   1110   11111110
    -3   101   1101   11111101
    -4   100   1100   11111100

To extend a 2's complement number to a greater number of binary digits, you just continue the sign bit to the left. Examples: Extend $9B to 16 bits. $9B = 1001 1011 = 1111 1111 1001 1011 = $FF9B

Extend $5F to 16 bits. $5F = 0101 1111 = 0000 0000 0101 1111 = $005F

Adding two 2's complement numbers of different length 43A0 43A0

 9B     FF9B   need to sign extend; you can't just add zeros.

???? 1 433B

Note that the 8-bit $9B and the 16-bit $FF9B both represent -101 in their respective number systems.