Numeric Representation


Hexadecimal Notation

For byte addressable computers, hexadecimal notation is the most convenient way of representing many forms of data. The decimal system relies upon representing integer values in terms of powers of 10 as shown below.

x = 2 * 10² + 7 * 10 + 3 * 1 (base 10)

The successive powers of 10 that are used are 2, 1, and 0 (noting that any number to the power zero is 1). The same number (273 base 10) may be represented in hexadecimal notation as follows.

x = 1 * 16² + 1 * 16 + 1 * 1 (base 16)

Note that 16 * 16 = 256 (base 10) and that the base 10 form of the above calculation is as shown below.

x  =  256 + 16 + 1  =  273.

Working with base 16 implies that each digit within a number is representable by one of sixteen separate symbols. The symbols that are used are 0,1,2...8,9,a,b,c,d,e,f. A hexadecimal number is signified by prefixing it with the two letters 0x. The absence of this prefix implies that the number is decimal, provided that the high order digit is non-zero (the high order digit being zero implies that the number is an octal number - i.e. base 8). The following should now be clear.

0x10  = 1 * 16  = 16
0x20  = 2 * 16  = 32
0x30  = 3 * 16  = 48
0x40  = 4 * 16  = 64
0x80  = 8 * 16  = 128
0x100 = 1 * 16² = 256

0xff  = 15 * 16 + 15 * 1 = 255 = 0x100 - 1

The Binary Number System

Consider the following picture of a byte.

27 26 25 24 23 22 21 20
1 1 1 1 1 1 1 1

Shown above, is the maximum value that a byte can assume (where all the bits are set to 1). In decimal, this byte can be written as follows.

x = 1*128 + 1*64 + 1*32 + 1*16 + 1*8 + 1*4 + 1*2 + 1 = 255

Alternatively, rather than attempt to express the binary number in decimal, note that each four bits (a nibble) represent a single hex digit. So the above byte can be viewed as:

Hex f f
Binary 1 1 1 1 1 1 1 1

where the resultant hexadecimal representation is 0xff. Adding 1 to the binary number above yields the following:

 11111111 +
        1
100000000

When performing binary addition, 1+1=0, carry1 (as for 9+1=0,carry1 under base 10 arithmetic). In the above addition, the second digit yields 1+0+carry1=0,carry1). This happens seven times, and the last carry goes to the next byte. So what is the result in hex ? Well, the result does not fit in a single byte; rather, it carries to the next byte - as pictured below.

Hex 0 1 0 0
Binary 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0

That is, binary 11111111+1 = 0xff+1 = 0x100 = 256.

A convenient way to visualise a 32 bit integer is shown below:

Hex f f f f f f f f
Binary 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

where each byte is represented by two hexadecimal digits.

Two's Complement Arithmetic

When dealing with binary, negative numbers can be represented using two's complement notation.

Definition

The two's complement of the binary representation of a number is obtained by replacing each 1 with a 0 and each 0 with a 1, and then adding 1 to the result.

For example, consider the following 8 bit representation of 32 = 0x20.

Hex 2 0
Binary 0 0 1 0 0 0 0 0

Changing each 0 bit to 1 and each 1 bit to 0 yields:

Hex d f
Binary 1 1 0 1 1 1 1 1

and adding one produces:

Hex e 0
Binary 1 1 1 0 0 0 0 0

which is the 8 bit two's complement representation of -32. Taking the two's complement of the two's complement of a number yields the original number. That is, the operation of taking the two's complement is its own inverse (which is as it should be).

Note that negative numbers in two's complement format may be recognised immediately by the high order bit being set to 1. Conversely, if the high order bit is zero then the number is positive.

Adding 0xe0 to 0x20 gives:

Hex e 0
Binary 1 1 1 0 0 0 0 0

+

Hex 2 0
Binary 0 0 1 0 0 0 0 0

=

Hex 0 0
Binary 0 0 0 0 0 0 0 0

where 1 is carried out of the high order bit. The carry out is not an error and is discarded for 8 bit two's complement arithmetic. This result should not be surprising since -32 + 32 = 0.

Sign Extending a Two's Complement Number

As just mentioned, a negative number can be recognised by the high order bit being set. So how then can the 8 bit two's complement representation of the number -32 be converted to a 16 bit two's complement representation? To answer this question, the two's complement representation of -32 will be recalculated, this time using 16 bit precision. The result is shown below.

Hex 0 0 2 0
Binary 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0

Changing each 0 to 1 and each 1 to 0 yields:

Hex f f d f
Binary 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1

and adding one produces:

Hex f f e 0
Binary 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0

which may be compared to the 8 bit representation previously obtained and which is shown below.

Hex e 0
Binary 1 1 1 0 0 0 0 0

From this it is clear that when extending a negative number from 8 to 16 bit, the high order bit is propagated through the high order byte of the 16 bit result. If the number to be extended is positive then zeros will be propagated through the high order byte. Note that it is not always possible to convert from a 16 to 8 bit two's complement representation and obtain a correct result. Such conversions are possible only when the high order byte is either all zeros or all ones and matches the high order bit of the lower order byte. Only in such cases can the high order byte be dropped without changing the value of the number.

In C++, the signed and unsigned integer data types are treated differently when converting to and from short to long representations. Signed data types are sign extended, whereas unsigned data types are not.