Motivation
To discuss the various number systems that are used in Computer Science.
Introduction
In Computer Science and computer programming, we can work with various number systems. Some of these number systems are binary,
octal, and hexadecimal. This page will also cover how to convert to and from IEEE floating_point formats as well. With the
binary system, and the idea that computers deal with data as bits of either 0 or 1, we work with number systems in powers of two.
Binary
The simplest and most atomic number system we work with is binary. It is a base-2 number system with digits being either a
zero (0) or a one (1). Each bit position is a power of two. The least significant bit, or lsb, is the bit in position 0 of the
binary number. One has to watch the endianness of the binary number depending on the CPU architecture. There are CPUs that
are big_endian, and others that are little_endian. At this point, for now, we are talking about unsigned integers.
An example of a binary number is as follows: 0110
What is the value of this number? The diagram below can help answer that.
8 4 2 1 <-two raised to the power of bit position
+-+-+-+-+
|0|1|1|0|
+-+-+-+-+
3 2 1 0 <- bit position
We add up the powers of two in which there is a corresponding one (1) bit set, and we have in this example 4 + 2 = 6 In the diagram, 1 is the lsb, or 2 to the power 0 which is 1. The 8 is 2 to the power of 3. Note that when counting the bit positions we start with 0 and end with one less than the actual number of digits, which in this case is a 4 digit number, the most significant bit, or msb, in this case is 4 - 1 = 3.
How about an example of a big endian 32 bit integer like 0111 1001 1110 1001 1100 0000 1111 1010?
We only care about the powers of two of the bits that contain a 1 since the bits that contain a zero are zero due to 0 x 2^n = 0.
The binary number in this example can be converted to a decimal (base 10) by done by expanding out the powers of twos to that contain a one bit in the following:
2^30 + 2^29 + 2^28 + 2^27 + 2^24 + 2^23 + 2^22 + 2^21 + 2^19 + 2^16 + 2^15 + 2^14 + 2^7 + 2^6 + 2^5 + 2^4 + 2^3 + 2^1 = ?
When computed, we have: 2045362426 in decimal.
What about converting from decimal to binary? We do the following, we divide our number (quotient) by our base, in this case two - for binary, construct a string of remainders that will be read from right to left until our quotient is zero, the dividend becomes our new quotient. Note, this is integer division!
Example: What is 107 decimal in binary?
1. 107 / 2 = 53 with remainder of 1, binary string = 1
2. 53 / 2 = 26 with remainder of 1, binary string = 11
3. 26 / 2 = 13 with remainder of 0, binary string = 011
4. 13 / 2 = 6 with remainder of 1, binary string = 1011
5. 6 / 2 = 3 with remainder of 0, binary string = 01011
6. 3 / 2 = 1 with remainder of 1, binary string = 101011
7. 1 / 2 = 0 with remainder of 1, binary string = 1101011
8. new quotient is zero, we are done, and the binary string is 1101011 that represents 107 decimal.
Check our work!
2^6 + 2^5 + 2^3 + 2^1 + 2^0 = 64 + 32 + 8 + 2 + 1 = 107!
What about dealing with signed integers? Simple! The most significant bit, or msb, becomes the sign bit. A positive number, has the sign bit set to zero, and a negative number has the sign bit set to a one. We use twos_complement representation to represent a signed integer in binary.
In the above example, 107 decimal is 1101011 binary, what about -107? Well, first of all, our sign bit is going to be set as one, and it has to be the most significant bit, or msb; next, we have to take the one's complement of our unsigned binary number by flipping all of the bits, all of the zeroes become ones, and likewise all of the ones become zeroes.
1's complement of 1101011 is 0010100
Next, to convert from 1's complement to 2's complement, we add 1 to the least significant bit, or lsb, which yields the following:
0010101, and adding the sign bit in the $msb, we have: 10010101, which is the binary representation of -107! Note, this isjust for 8 bit signed integer, what if this were 32 bit signed integer? Simple! The 32 bit unsigned representation of 107 would be
1101011, with all of the higher bits being zero like: 0000 0000 0000 0000 0000 0000 0110 1011, nothing particular about this!
Now, the 1's complement would look like:
1111 1111 1111 1111 1111 1111 1001 0100, nothing particular here either other than the long string of 1's
And adding 1 to our 1's complement 32 bit intger yields:
1111 1111 1111 1111 1111 1111 1001 0101, which is the 32 bit representation of -107.
What about 64 bit signed integer or 128 bit signed integer? Nothing different! Just pad with 1's in the higher bits to fill in!
Octal
It is a base-8 number system with digits being between zero (0) and seven (7). Each digit position is a power of eight. For octal
digits, see the octal_digits_table.
An example of an octal number is as follows: 1437
What is the value of this number? The diagram below can help answer that.
512 64 8 1 <-eight raised to the power of the digit position
+---+--+-+-+
| 1 |4 |3|7|
+---+--+-+-+
3 2 1 0 <- digit position
We add up sum of the products of the digit and its respective the power of eight, and we have in this example:
1 * 512 + 4 * 64 + 3 * 8 + 7 * 1 = 512 + 256 + 24 + 7 = 799 decimal
What about converting from decimal to octal? Simple! We do like we did in the decimal to binary example, except, divide by eight this time, instead of by two. In fact, the steps introduced in the decimal to binary conversion algorithm will work for any base of numbers.
We do the following, we divide our number (quotient) by our base, in this case eight - for octal, construct a string of remainders that will be read from right to left until our quotient is zero, the dividend becomes our new quotient. Note, this is integer division!
Example: What is 117 decimal in octal?
1. 117 / 8 = 14 with remainder of 5, octal string = 5
2. 14 / 8 = 1 with remainder of 6, octal string = 65
3. 1 / 8 = 0 with remainder of 1, octal string = 165
4. new quotient is zero, we are done, and the octal string is 165 that represents 117 decimal.
Check our work!
1 * 64 + 6 * 8 + 5 * 1 = 64 + 48 + 5 = 117!
What about dealing with signed integers? Well... best approach is to convert our octal number to binary, and find the two's complement of our number, and convert back to octal.
Based on the octal_digits_table, we can quickly convert 165 octal to 001 110 101 binary! Our 2's complement will be 1 111 111 110 001 011, which in turn will be 177613 octal, and that happens to be -117 decimal!
What about -107 decimal 32 bit signed integer in octal? From our discussion on binary, -107 is 1111 .... 1111 1001 0101 binary, so convert to the appropriate octal, 1 111 111 111 111 111 111 111 110 010 101 = 37777777625 octal
Hexadecimal
It is a base-16 number system with digits being between zero (0) through nine (9), and A through F to represent 10 - 15 respectively.
Each digit position is a power of sixteen. For hexadecimal digits, see the hexadecimal_digits_table.
An example of a hexadecimal number (often called hex) is as follows: A3C
What is the value of this number? The diagram below can help answer that.
4096 256 16 1 <-sixteen raised to the power of the digit position
+----+---+--+-+
| 0 | A | 3|C|
+----+---+--+-+
3 2 1 0 <- digit position
We add up sum of the products of the digit and its respective the power of sixteen, and we have in this example:
0 * 4096 + 10 * 256 + 3 * 16 + 13 * 1 = 2560 + 48 + 31 = 2621 decimal
What about converting from decimal to hex? Simple! We do like we did in the decimal to binary example, except, divide by sixteen this time, instead of by two. In fact, the steps introduced in the decimal to binary conversion algorithm will work for any base of numbers.
We do the following, we divide our number (quotient) by our base, in this case eight - for octal, construct a string of remainders that will be read from right to left until our quotient is zero, the dividend becomes our new quotient. Note, this is integer division!
Example: What is 32117 decimal in hex?
1. 32117 / 16 = 2007 with remainder of 5, hex string = 5
2. 2007 / 16 = 125 with remainder of 7, hex string = 75
3. 125 / 16 = 7 with remainder of 13, hex string = C75 <- remember that 13 decimal is C in hex!
4. 7 / 16 = 0 with remainder of 7, hex string = 7C75
5. new quotient is zero, we are done, and the hex string is 7C75 that represents 32117 decimal.
Check our work!
7 * 4096 + 13 * 256 + 7 * 16 + 5 * 1 = 64 + 48 + 5 = 32117!
What about dealing with signed integers? Well... best approach is to convert our hex number to binary, and find the two's complement of our number, and convert back to hex.
Based on the hexadecimal_digits_table, we can quickly convert 7C75 hex to 0111 1101 0111 0101 binary! Our 2's complement will be 1000 0010 1000 1011, which in turn will be 828B hex, and that happens to be -32117 decimal!
What about -32117 decimal 32 bit signed integer in hex? From our discussion on binary, 32117 is 00007C75 hex in unsigned integer, so convert to the appropriate binary: 0000 0000 0000 0000 0111 1101 0111 0101, and get the 2's complement of it which yields:
1111 1111 1111 1111 1000 0010 1000 1011, and convert to hex: FFFF828B!
Note, that to make it somewhat easier to read, I break up the binary digits into groups of four, which happens to be 2 to the power of 4, which is 16! The same number base that hexadecimal is!
IEEE Floating Point Formats
This section discusses how to convert decimal numbers to IEEE 754 floating point. It covers, 32 bit, 64 bit, and 80 bit floating
point data types. There are three parts to floating point numbers, the sign_bit, the exponent, and the mantissa.
When converting from decimal to floating point, we go through a similar process as if we were converting integers in decimal to binary, except we have to take into consideration exponents, fractional values, and normalizing the binary result.
Consider the following decimal number: 7.125
First of all, our sign bit will be a zero since this is a positive number! Next, we have to convert 7.125 to binary, which can be found as 111.001, just like all of the bit positions to the left of the radix point, everything to the right of the radix point are powers of two, but they are negative powers. The one three places to the right of the binary decimal point is 2 to the -3, or 1/8 or 0.125; warning, not all fractions are going to come out clean like this!
Now, normalizing is the tricky part at first, but once it has been practiced a bit, it is rather easy. We want our binary floating point number to be in the format of 1.xxxxxxxxxx .... xxxxx * 2^exp
The leading 1 will not be actually stored in the final number, because we are normalizing to it and it will "always" be there, the value for exp is a biased exponent using a bias. The value of exp is found by adding the number of binary decimal place moves to the bias value. Moves to the left is a positive value, and moves to the right are negative values.
So, 111.001 normalized looks like 1.11001, with the radix point moved left two positions, this makes the exp = 127 + 2 = 129. In binary, 129 decimal is 10000001 binary; now piecing all of this together, we have
0 10000001 11001 000000000000000000, in 4 bit nibbles: 0100 0000 1110 0100 0000 0000 0000 0000 => 40E40000 hex.
Now, converting back, break the number back into the three parts, sign, exponent, and mantissa. Sign bit is zero, so our number is positive. The biaed exponent is 10000001, or 129 decimal - 127 is 2, the mantissa is 110010000000 .... 0; normalized number is 1.110010000.....0 * 2^2; we have 111.001, convert back to decimal and we have 7.125.
Earlier I warned that not all decimal fractions will come out clean, we can have fractions in base 10 that are non-repeating fractions, but are repeating fractions in base 2!
Consider the decimal 0.2 in base 10, what is it in binary? We have a modified algorithm for finding the fractional binary digits. It is as followed: take the fraction and multiply by two, the fractional binary digit is the whole number of the result. If the whole number of the result is one, after adding the one to our binary number string, we replace the whole number 1 with a zero, and repeat this algorithm until the desired number of bits has been completed (this can take some time on pencil and paper!)
Converting 0.2 goes as follows:
0.2 * 2 = 0.4; binary string = 0.0 <- this zero is our 0 in the whole number portion of the result
0.4 * 2 = 0.8; binary string = 0.00
0.8 * 2 = 1.6; binary string = 0.001
0.6 * 2 = 1.2; binary string = 0.0011 <- 0.6 is 1.6 with the whole number 1 removed after adding to our string
0.2 * 2 = 0.4; binary string = 0.00110 <- notice we have dealt with 0.4 before! this is going to repeat forever...
...
0.2 in binary is 0.001100110011001100110011001100110 ...
Now convert this to IEEE 754, the sign bit is a zero since it is a positive number, the normalized binary number is 1.100110011001100110011001100110 ..., with 3 radix point moves to the right, so the biased exponent is 127 + (-3) = 124 or 01111100 binary.
0 01111100 10011001100110011001100110011001100110011001100110 ...
As in base 10 fractions, we have to keep in mind about rounding up the last digit, we have to do the same with binary!
0011 1110 0100 1100 1100 1100 1100 1101 1100 1100 1100 1100 1100 1100 110
3 E 4 C C C C D <- the 32nd bit was a 0 but rounded up to a 1 because the 33rd bit was a 1!
This is just like if 1.239 was rounded to 1.24 in base 10, if in binary, the next digit after our last digit of precision is a 0, no rounding is needed, if the rounding digit is a 1 and the last digit is a zero, round up, otherwise leave last digit alone!
Type Total Bits Exponent Size Mantissa Size Bias (2^(exp_size-1)-1)
Single 32 8 23 127
Double 64 11 52 1023
Extended 80 15 64 16383
Binary Octal Decimal
001 1 1
010 2 2
011 3 3
100 4 4
101 5 5
110 6 6
111 7 7
Binary Octal Hexadecimal Decimal
0001 1 1 1
0010 2 2 2
0011 3 3 3
0100 4 4 4
0101 5 5 5
0110 6 6 6
0111 7 7 7
1000 10 8 8
1001 11 9 9
1010 12 A 10
1101 13 B 11
1100 14 C 12
1101 15 D 13
1110 16 E 14
1111 17 F 15
. . . . . . . . . ( end of section Number Systems) <<Contents | Index>>