.Open Number Systems

. 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.
 
.As_is  8 4 2 1 <-two raised to the power of bit position
.As_is +-+-+-+-+
.As_is |0|1|1|0|
.As_is +-+-+-+-+
.As_is  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?

.As_is 1. 107 / 2 = 53 with remainder of 1, binary string = 1
.As_is 2. 53 / 2 = 26 with remainder of 1, binary string = 11
.As_is 3. 26 / 2 = 13 with remainder of 0, binary string = 011
.As_is 4. 13 / 2 = 6 with remainder of 1, binary string = 1011
.As_is 5. 6 / 2 = 3 with remainder of 0, binary string = 01011
.As_is 6. 3 / 2 = 1 with remainder of 1, binary string = 101011
.As_is 7. 1 / 2 = 0 with remainder of 1, binary string = 1101011 
.As_is 8. new quotient is zero, we are done, and the binary string is 1101011 that represents 107 decimal.

Check our work! 

.As_is 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.

.As_is 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:

.As_is 0010101, and adding the sign bit in the $msb, we have: 10010101, which is the binary representation of -107! Note, this is
just for 8 bit signed integer, what if this were 32 bit signed integer? Simple! The 32 bit unsigned representation of 107 would be

.As_is 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:

.As_is 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:

.As_is 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.
 
.As_is  512 64 8 1 <-eight raised to the power of the digit position
.As_is +---+--+-+-+
.As_is | 1 |4 |3|7|
.As_is +---+--+-+-+
.As_is   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:

.As_is 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?

.As_is 1. 117 / 8 = 14 with remainder of 5, octal string = 5
.As_is 2. 14 / 8 = 1 with remainder of 6, octal string = 65
.As_is 3. 1 / 8 = 0 with remainder of 1, octal string = 165
.As_is 4. new quotient is zero, we are done, and the octal string is 165 that represents 117 decimal.

Check our work! 

.As_is 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.
 
.As_is  4096 256 16 1 <-sixteen raised to the power of the digit position
.As_is +----+---+--+-+
.As_is | 0  | A | 3|C|
.As_is +----+---+--+-+
.As_is   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:

.As_is 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?

.As_is 1. 32117 / 16 = 2007 with remainder of 5, hex string = 5
.As_is 2. 2007 / 16 = 125 with remainder of 7, hex string = 75
.As_is 3. 125 / 16 = 7 with remainder of 13, hex string = C75 <- remember that 13 decimal is C in hex!
.As_is 4. 7 / 16 = 0 with remainder of 7, hex string = 7C75
.As_is 5. new quotient is zero, we are done, and the hex string is 7C75 that represents 32117 decimal.

Check our work! 

.As_is 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:

.As_is 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

.As_is 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:

.As_is 0.2 * 2 = 0.4; binary string = 0.0 <- this zero is our 0 in the whole number portion of the result
.As_is 0.4 * 2 = 0.8; binary string = 0.00
.As_is 0.8 * 2 = 1.6; binary string = 0.001
.As_is 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
.As_is 0.2 * 2 = 0.4; binary string = 0.00110 <- notice we have dealt with 0.4 before! this is going to repeat forever...
.As_is ...
.As_is 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.

.As_is 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!

.As_is 0011 1110 0100 1100 1100 1100 1100 1101 1100 1100 1100 1100 1100 1100 110
.As_is    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!

sign_bit::= generally is the leading bit of a IEEE 754 floating point number in binary.

exponent::= the binary exponent of a IEEE 754 floating point number in binary. It is computed off of a $bias, which has its value
depend on the precision of the floating point number.

mantissa::= the fractional part of the floating point number, normalized to 1.xxxxxxxxxxx binary, with the leading 1 being
disregarded (it is "always" there in the floating point number, not just included).

bias::= a number that we offset the exponent by in order to have exponents to be able to represent both tiny and huge values. The 
table below shows the bias of the various floating point data type sizes, along with the exponent size, and mantissa size.

.As_is Type	Total Bits	Exponent Size	Mantissa Size	Bias (2^(exp_size-1)-1)
.As_is Single	32		8		23		127
.As_is Double	64		11		52		1023
.As_is Extended	80		15		64		16383

octal_digits_table::= Table of Octal Digits and their Binary / Decimal Equivalents

.As_is Binary	Octal	Decimal
.As_is 001	1	1
.As_is 010	2	2
.As_is 011	3	3
.As_is 100	4	4
.As_is 101	5	5
.As_is 110	6	6
.As_is 111	7	7

hexadecimal_digits_table::= Table of Hexadecimal Digits and their Binary / Octal / Decimal Equivalents

.As_is Binary	Octal	Hexadecimal	Decimal
.As_is 0001	1	1		1
.As_is 0010	2	2		2
.As_is 0011	3	3		3
.As_is 0100	4	4		4
.As_is 0101	5	5		5
.As_is 0110	6	6		6
.As_is 0111	7	7		7
.As_is 1000	10	8		8
.As_is 1001	11	9		9
.As_is 1010	12	A		10
.As_is 1101	13	B		11
.As_is 1100	14	C		12
.As_is 1101	15	D		13
.As_is 1110	16	E		14
.As_is 1111	17	F		15

atomic::= In Computer Science and computer programming, when something is broken down the smallest it can be, it is considered atomic.

binary::= Base 2 number system, with the digits 0 and 1 available.

octal::= Base 8 number system, with the digits 0 through 7 available. Three $binary digits make up one octal digit.

hexadecimal::= Base 16 number system, with digits 0 - 9, and the letters A - F representing the digits, 10 through 15, 
respectively. Four $binary digits make up one hexadecimal digit.

lsb::= is short for least significant bit, this is the bit in position 0 of a binary number. When a digit in this position is set,
it is 2 to the 0th power, or 1.

msb::= is short for most significant bit, this is the bit in the highest position of an n-digit binary number. For example, a
16 bit binary number, the digit in position 15 is the most significant digit, and if set, has the value of 2 to the 15th power.

endianness::= The endianness of a binary number dictates which side of the binary number the most significant bit 
and least significant bit are located, and the ordering of the binary digit positions in between. Two types of endianness
are: $big_endian and $little_endian. List of $common_cpu_endianness is also given in this page.

big_endian::=  store the most significant bit, or $msb, of a word in the smallest address and the least significant bit, or $lsb,
is stored in the largest address. 

little_endian::= store the most significant bit, or $msb, of a word in the largest address and the least significant bit, or $lsb,
is stored in the smallest address. 

common_cpu_endianness::= $big_endian_cpus, $little_endian_cpus

big_endian_cpus::= some big endian cpus are: Motorola 6800, Motorola 68k, System/370, ESA/390, z/Architecture, and pre version 9 SPARC.

little_endian_cpus::=  some little endian cpus are: Intel x86, Intel x86-64, 6502, 65802, 65C816, Z80, MCS-48, 8051, DEC Alpha, VAX, and PDP-11.

twos_complement::= binary numbering system that allows us to represent negative binary numbers.

.Close Number Systems