1. Number Bases and Arithmetic

Counting

We start counting at $0$.

Numbers and Bases

For most of our lives, we have been used to positional number systems like the base-$10$ system. For instance, $2024$ can be rewritten as $2000+000+20+4$ or we can represent it in bases of 10 $2\cdot10^3+0\cdot10^2+2\cdot10^1+4\cdot10^0$. Since they are written positionally, the most significant digit is the leading and the least significant digit is the tailing. The number of symbols we have in our base-$10$ system is the same as the base, so we have $10$ symbols or $0,1,2,3,4,5,6,7,8,9$.

Let's take $2024$ or $2\cdot10^3+0\cdot10^2+2\cdot10^1+4\cdot10^0$ again, since $2024$ is a $4$ digit number, we can represent $10000$ or $10^4$ different numbers. The smallest non-negative number representable with 4 digits is $0$. The largest number representable with 4 digits is $9999$ or $10^4-1$.

Summary of Base-$10$

• A number represented by the digits is $d_{n-1}\dots d_1 d_0$.
• This has the value of $d_{n-1}\cdot10^{n-1}+\dots+d_{1}\cdot10^{1}+d_{0}\cdot10^{0}$
• Using $n$ digits we can represent $10^n$ different numbers
• The smallest non-negative number representable with $n$ digits is $0$.
• The largest number representable with $n$ digits is $10^n-1$
• Uses $10$ symbols: $0,1,2,3,4,5,6,7,8,9$.

Although we have used base-$10$ (decimal) most of our lives, we can actually use any number as a base. Like base-$2$ (binary), base-$16$ (hexadecimal), and (rarely) base-$8$ (octal).

Dealing With Multiple Bases

When dealing with multiple bases, use subscripts to denote the base. For examplem, $5_{10}=101_2$.

Remember our summary of base-$10$? Well, let's make that more general.

Summary of Base-$B$

• A number represented by the digits is $d_{n-1}\dots d_1 d_0$.
• This has the value of $d_{n-1}\cdot B^{n-1}+\dots+d_{1}\cdot B^{1}+d_{0}\cdot B^{0}$
• Using $n$ digits we can represent $B^n$ different numbers
• The smallest non-negative number representable with $n$ digits is $0$.
• The largest number representable with $n$ digits is $B^n-1$
• Uses $B$ symbols.

Number Representations

Now, let's explore those other number systems.

Binary

Binary has, shocker, two symbols in its number system. Each digit in a binary system is called a bit or a single $1$ or $0$. When saying an $n$-bit number, we mean one with $n$ binary digits.

Summary of Base-$2$

• A number represented by the digits is $d_{n-1}\dots d_1 d_0$.
• This has the value of $d_{n-1}\cdot 2^{n-1}+\dots+d_{1}\cdot 2^{1}+d_{0}\cdot 2^{0}$
• Using $n$ digits we can represent $2^n$ different numbers
• The smallest non-negative number representable with $n$ digits is $0$.
• The largest number representable with $n$ digits is $2^n-1$
• Uses $2$ symbols: $0, 1$.

Going from binary to decimal

To convert binary to decimal, ignore all of the $0$ values and add up place values wherever you see a $1$.

$10010110_{2} = 1\cdot2^7+0\cdot2^6+0\cdot2^5+1\cdot2^4+0\cdot2^3+1\cdot2^2+1\cdot2^1+0\cdot2^0 = 150_{10}$

Going from decimal to binary

Making change

Suppose you have $\$9.63$ in change, using the fewest bills and coins possible. How do you count it out?

$\$9.63-\$5 \cdot 1=\$4.63$
$\$4.63-\$1 \cdot 4=\$0.63$
$\$0.63-\$0.25 \cdot 2=\$0.13$
$\$0.13-\$0.10 \cdot 1=\$0.03$
$\$0.03-\$0.05 \cdot 0=\$0.03$
$\$0.03-\$0.01 \cdot 3=\$0.00$

So going from most significant to least significant, we will give the least amount needed for the amount given.

This princple also works with binary.

Convert $83_{10}$ to base-$2$

$83-0 \cdot 2^7 = 83$
$83-1 \cdot 2^6 = 19$
$19-0 \cdot 2^5 = 19$
$19-1 \cdot 2^4 = 3$
$3-0 \cdot 2^3 = 3$
$3-0 \cdot 2^2 = 3$
$3-1 \cdot 2^1 = 1$
$1-1 \cdot 2^0 = 0$

Thus, we have $01010011_{2}$

The most basic algorithm for binary is:

For each place from MSB:
If place value <= remainder:
    digit = 1
    remainder = remainder - place
Else:
    digit = 0

A bit is one binary digit, and its unit is lowercase b. A byte is an $8$-bit value, and its unit is upercase B. A nibble is a $4$-bit value or half of a byte. A word is the "most comfortable size" of number for a CPU. So when we say "$32$-bit CPU," we mean its word size is $32$ bits. This means it can, for example, add two $32$-bit numbers at once.

But watch out! Some things (Windows, x86) use word to mean $16$-bits and double word (or dword) to mean $32$-bits.

Conversions of Magnitude

Wording with these representations can get confusing because people sometimes leave out the i in KiB for example. Make sure to include correct units.

Potatoes	Bytes	Bytes
$1$g (gram)	$1$B (Byte)	$1$B (Byte)
$1$kg (Kilogram) = $1000$g	$1$kB (Kilobyte) = $1000$B	$1$kiB (Kibibyte) = $1024$B (power of $2$ nearest to $1000$)
$1$Mg (Megagram) = $1000$Kg	$1$MB (Megabyte) = $1000$kB	$1$MiB (Mebibyte) = $1024$kiB
$1$Gg (Gigagram) = $1000$Mg	$1$GB (Gigabyte) = $1000$MB	$1$GiB (Gibibyte) = $1024$MiB
$1$Tg (Teragram) = $1000$Gg	$1$TB (Terabyte) = $1000$GB	$1$TiB (Tebibyte) = $1024$GiB
$1$Eg (Exagram) = $1000$Tg	$1$EB (Exabyte) = $1000$TB	$1$EiB (Exbibyte) = $1024$TiB

Why Binary?

Binary generally requires more bits to represent the same thing. For instance, $10_{10}$ requires two digits while in binary $1010$ requires four bits (or simply take the log: $log_2(10)=3.322$). So, why use it? Well it's sooooo much easier to implement with hardware and it is robust. The arithmetic is also really easy.

As we can see above, it is really hard to tell which color is the base-$10$. However, it is very easy for binary to tell and especially so when considering electronics work by sending signals with either off or on.

Furthermore, everything on a computer is represented in binary. Like text and characters using standards like UTF-16 or ASCII. They are also used in images, colors, and videos by using various standards like RGB.

All information on computers is stored as patterns of bits, but... How these bits are interpreted, transformed, and displayed is up to the programmer and the user. So for example $11000100_{2}$ can be a signed integer ($-59$), unsigned integer ($196$), hexadecimal ($0xC4$), unicode (Ä), z80 instruction (z80 instruction), or color ($R3G3B2$).

Corollary

The same pattern of bits can be interpreted many different ways.

Hexadecimal

How many symbols does hexadecimal have? 16.

Binary numbers can get long, quickly, so let's use say base-$10$ to represent them. Well... they don't represent the binary well because $10$ is not a power of 2. So let's try base-$4$, base-$8$, base-$16$, base-$32$, etc. Base-$4$ still is not much more concise than binary, and base-$32$ and up require too many symbols. Base-$8$ and base-$16$ are the best bets.

Summary of Base-$16$

• A number represented by the digits is $d_{n-1}\dots d_1 d_0$.
• This has the value of $d_{n-1}\cdot 16^{n-1}+\dots+d_{1}\cdot 16^{1}+d_{0}\cdot 16^{0}$
• Using $n$ digits we can represent $16^n$ different numbers
• The smallest non-negative number representable with $n$ digits is $0$.
• The largest number representable with $n$ digits is $16^n-1$
• Uses $16$ symbols: $0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F$.

The digit symbols after $9$ are $A-F$, meaning $10-15$ respectively. We call one hexadecimal digit a hex digit.

Decimal to Hex, Hex to Decimal

Use a calculator, much much easier!

Convert $003BEE70_{16}$ to decimal

$003BEE70_{16}=0 \cdot 16^7 + 0 \cdot 16^6 + 3 \cdot 16^5 + 11 \cdot 16^4 + 14 \cdot 16^3 + 14 \cdot 16^2 + 7 \cdot 16^1 + 0 \cdot 16^0 = 3927664_{10}$

Convert $3927664_{10}$ to hex

$\frac{3927664}{16_{10}}=245479$, R $0$
$\frac{245479}{16_{10}}=15342$, R $7$
$\frac{15342}{16_{10}}=958$, R $14$
$\frac{958}{16_{10}}=59$, R $14$
$\frac{59}{16_{10}}=3$, R $11$

Then go from the last division answer, to the right, and up through the remainders.

$0, 0, 3, 11, 14, 14, 7, 0$

$003BEE70_{16}$ or $0x003BEE70$

Decimal to Binary

You can do the same thing with binary as above, just divde by $2$ or the base of any base number system.

Binary to Hexadecimal

Four bits are equivalent to one hex digit. This makes conversion super easy!

Binary to Hexadecimal

$1110111110111001110000_2$
$001110111110111001110000_2$
$0011 \space 1011 \space 1110 \space 1110 \space 0111 \space 0000$
$0x3BEE70$

And reverse this process to get hexadecimal to binary.

Binary	Hexadecimal
$0000$	$0$
$0001$	$1$
$0010$	$2$
$0011$	$3$
$0100$	$4$
$0101$	$5$
$0110$	$6$
$0111$	$7$
$1000$	$8$
$1001$	$9$
$1010$	$A$
$1011$	$B$
$1100$	$C$
$1101$	$D$
$1110$	$E$
$1111$	$F$

Powers of 2

	Decimal	Hexadecimal
$2^0$	$1$	$0x1$
$2^1$	$2$	$0x2$
$2^2$	$4$	$0x4$
$2^3$	$8$	$0x8$
$2^4$	$16$	$0x10$
$2^5$	$32$	$0x20$
$2^6$	$64$	$0x40$
$2^7$	$128$	$0x80$
$2^8$	$256$	$0x100$

Largest number in $n$-bit values

$8$-bit: $255_{10}=0xFF$

$16$-bit: $65535_{10}=0xFFFF$

Octal

Octal isn't really used any more, however, it is still essential to over.

Octal has $8$ symbols. Written as $6370_8$ or $06370$ or $0o6370$.

Summary of Base-$8$

• A number represented by the digits is $d_{n-1}\dots d_1 d_0$.
• This has the value of $d_{n-1}\cdot 8^{n-1}+\dots+d_{1}\cdot 8^{1}+d_{0}\cdot 8^{0}$
• Using $n$ digits we can represent $8^n$ different numbers
• The smallest non-negative number representable with $n$ digits is $0$.
• The largest number representable with $n$ digits is $8^n-1$
• Uses $8$ symbols: $0, 1, 2, 3, 4, 5, 6, 7$.

To convert decimal to octal: divide by 8.

To convert octal to binary: groups of 3.

Number Arithmetic

Instead of carrying $10_{10}$, you carry at $10_2$

• $1+1 = 10_2$
• $1+1+1=11_2$

Addition

$\space \space \space \space \overset{0}{1}\overset{1}{0}\overset{1}{1}\overset{1}{1}\space \overset{1}{0}\overset{1}{0}\overset{0}{1}0$
$\underline{+\space 0010\space 1111}$
$\space \space \space \space 1110\space 0001$

For each pair of bits starting at the LSB

• add the two bits and carry.
• the low bit of the sum goes into the sum row.
• the high bit of the sum is carry for the next higher bit.

Overflows

What happens with overflows??

Example:

int main() {
    positive_tiny number = 0;
    print << number << enter;

    return 0
}

output: 0, all good!

int main() {
    positive_tiny number = 2;
    print << number << enter;

    return 0
}

output: 2, all good!

int main() {
    positive_tiny number = 14;
    print << number << enter;

    return 0
}

output: 14, all good!

---

int main() {
    positive_tiny number = 14;
    print << number + 1 << enter;

    return 0
}

output: 15, all good!

int main() {
    positive_tiny number = 14;
    print << number + 2 << enter;

    return 0
}

output: 0, wait...

int main() {
    positive_tiny number = 14;
    print << number + 3 << enter;

    return 0
}

output: 1, what?

We can only store 4 bit numbers, so when you reach the end, it wraps around. This idea is overflow, it wrap around if it overflows.

This is okay since computers can hold really big numbers. We "can't" detect overflow, even though we can, we just choose not to. All arithmetic is modular arithmetic, so $a+b=(a+b) \% 2^n$ where $n$ is the number of bits we can store.

---

If you add two 2-digit numbers, what's the largest number you can get? 198, or 3-digits

Two 4-digit decimal numbers? 19998 or 5-digits

Two 4-bit numbers? 11110, or 5-bits

Two 32-bits numbers, we might get 33-bits

Overflow and Adding

If you add two $n$-digit numbers in any base the result will have at most $n+1$ digits.

If we have more bits than we can store in our number, that's overflow.

Handling Overflow

• Just ignore it
  • In MIPS: addu, subu.
  • This is usually a bad idea.
  • Its the default in most languages.
• We could fall on the floor, i.e. crash
  • In MIPS: add, sub.
  • Can be handled and recovered from.
  • But we introduce more complexity.
• We could store that 33rd bit somewhere else (Bit Bucket).

Bit Bucket

• Many other architectures do this.
  • MIPS does not.
• They have a "carry bit" register.
  • The can be checked by the program after an add/sub.
• This is very useful for arbitary precision arithmeitc.
  • If you want to add 2048-bit numbers, chain many 32-bit numbers.

Next Page →