1 Unsigned place value numbers

Unsigned place value numbers require two idea:

A set of $b$ digits, each with an integer meaning between zero and $b-1$ . $b$ is called the base of the place value number system.

We’ll use the digits 0 through 9, then switch to A though Z (either upper- or lower-case) for ten through thirty-five. For $b>36$ we don’t have a standard notation, though we’ll note one special notation for $b=256$ below.
A way of writing a sequence of digits from low-order to high-order. In English we use horizontal sequences with low-order on the right and high-order on the left.

If we need to refer to specific places we’ll use index 0 to refer to the low-order place, index 1 for the next place, and so on. When we need to reference a digit in symbolic form we’ll call it $d_i$ , where $d$ is the name of the number and $i$ is the index of the digit.

We’ll draw these like so:

1.1 Meaning

The numeric meaning of an unsigned base- $b$ number $x$ is the sum of $x_i b^i$ for all indices $i$ .

= $0 \cdot 10^0 + 4 \cdot 10^1 + 3 \cdot 10^2 = 340$

= $4 \cdot 16^0 + 5 \cdot 16^1 + 1 \cdot 16^2 = 340$

= $0 \cdot 2^0 + 0 \cdot 2^1 + 1 \cdot 2^2 + 0 \cdot 2^3 + 1 \cdot 2^4 + 0 \cdot 2^5 + 1 \cdot 2^6 + 0 \cdot 2^7 + 1 \cdot 2^8 = 340$

What is ?

224

What is ?

95

What is ?

2766

What is ?

13406

1.2 Finding the value in a given base

Finding a value in a given base cane be done by repeated division with remainder.

Find the smallest $b^i$ that is larger than $x$ . You’ll need $i$ places.
For $k$ $k$ from $i-1$ $i - 1$ to $0$ $0$ , inclusive of both endpoints:
1. Divide $x$ by $b^k$ , keeping the whole number quotient and remainder
2. Put the quotient in place $k$
3. Replace $k$ with the remainder for the next iteration of this loop

To convert 340 to base 3,

$3^6 = 729$ , the smallest power of $3$ which is greater than $340$ . Thus we’ll have 6 places:
Repeat for $k$ from 5 to 0, inclusive of both endpoints:

$k=5$

$340 \div 3^5 = 1 \text{ remainder } 97$

$k=4$

$97 \div 3^4 = 1 \text{ remainder } 16$

$k=3$

$16 \div 3^3 = 0 \text{ remainder } 16$

$k=2$

$16 \div 3^2 = 1 \text{ remainder } 7$

$k=1$

$7 \div 3^1 = 2 \text{ remainder } 1$

$k=0$

$1 \div 3^0 = 1 \text{ remainder } 0$

Thus $340$ is 110121 in base-3.

1.3 Bases that are powers of other bases

If $b = \beta^n$ then each base- $b$ digit maps to exactly $n$ base- $\beta$ digits.

Because $16 = 2^4$ , each digit of a base-16 number maps directly to 4 digits of a base-2 number.

We use this feature extensively in computing. Processors typically operate in base-2 (binary), but we find base-2 hard to read (too many 0s and 1s and we get lost) so we write base-8 (octal: $2^3=8$ ) or base-16 (hexadecimal: $2^4 = 16)$ instead. Memory, files, and network communication is typically defined in base-256 (bytes) but we find base-256 hard to read (we only have 36 digits) so we write each byte in base-16 ( $16^2 = 256$ ) using two characters for one digit.

This document is stored on a file and transmitted over a network in a byte-oriented format called HTML. The first eight bytes are 3C 21 44 4F 43 54 59 50.

I started writing this example 1705682415 seconds after the POSIX epoch. In base-256 that is

2 Addition

To add two numbers represented in the same base,

Initialize a carry digit to 0
Work from index $i=0$ up; for each index $i$ ,

Add the digits at index $i$ and the carry digit
Replace the carry digit with index 1 of the sum
Use index 0 of the sum as index $i$ of the result

When we run out of digits in a number, use 0s
Stop once all digits in both numbers are used up and the carry is 0

It is common to draw this entire process by putting the two numbers to add one atop the other, the carry digits above them both, and the result below them both.

To add base-10 numbers 340 and 173 we

add carry 0 and digits 0 and 3 to get result 3 and carry 0
add carry 0 and digits 4 and 7 to get result 1 and carry 1
add carry 1 and digits 3 and 1 to get result 5 and carry 0

We’d draw this like so:

To add base-2 numbers 100111 and 1011 we

add carry 0 and digits 1 and 1 to get result 0 and carry 1 ( $0+1+1=2$ which is 10 in base-2)
add carry 1 and digits 1 and 1 to get result 1 and carry 1 ( $1+1+1=3$ which is 11 in base-2)
add carry 1 and digits 1 and 0 to get result 0 and carry 1
add carry 1 and digits 0 and 1 to get result 0 and carry 1
add carry 1 and digits 0 and 0 to get result 1 and carry 0
add carry 0 and digits 0 and 0 to get result 0 and carry 0
add carry 0 and digits 1 and 0 to get result 1 and carry 0

We’d draw this like so:

3 Subtraction

There are several models of subtraction taught in schools, but the one that works best on computers is generally not one of them.

Define b’s complement of a digit $d$ to be $b-1-d$ . When working in base b we always use b’s complements and just call them the complement of the digit.

Complements in two example bases are shown below

Digit	two’s complement	ten’s complement
0	1	9
1	0	8
2		7
3		6
4		5
5		4
6		3
7		2
8		1
9		0

With this definition, we can subtract $x-y$ by adding $x$ and the digit-by-digit complement of $y$ (including complimenting the extra-digit 0s) using an initial carry of $1$ instead of $0$ . We stop once we’ve used up all digits and the carry is 1.

To subtract base-10 numbers 340 and 124 we

compliment 0…0124 as 9…9875
add 0…0340 + 9…9875 + 1 in the usual way, stopping when the digits are used and the carry is 1

If we’d not stop we still would get the same answer:

4 Signed place-value numbers, computer style

Signed place-value numbers in computers use a finite number of digits. They do addition and subtraction the same way they do for unsigned numbers, but they discard high-order digits that they can’t store.

In this model, $-x$ is $0-x$ and is the complement of the digits of $x$ , plus 1.

The 6-digit base-10 value of −340 is 999659 + 1 = 999660.

The 8-digit base-2 value of −101101 is 11010010 + 1 = 11010011.

When using signed numbers like this, we also need to distinguish between positive and negative numbers. For addition, subtraction, and multiplication it doesn’t matter if a number if positive or negative, but for comparisons and some division algorithms it does. The most common approach is to make half of all numbers negative, meaning in particular that a number is negative if the highest-order digit is $b \over 2$ or larger.

For base-2 (binary) numbers, the most common in computing, this means a signed integer is negative if the highest-order bit is 1, and is non-negative if that bit is 0.

In C and C++, the signed char and unsigned char types are 8-digit base-2 numbers.¹¹ Annoyingly, char might be shorthand for signed char on one machine and unsigned char on another. If you are using char as a number type, always include an explicit signedness indicator.

Let’s consider a few numbers’ base-2 representation:

base 10	8-digit base 2
124
225
340

To make these into 8-digit numbers, empty boxes will be receive the digit 0 and digits that don’t have a box will be discarded. Thus, the following code stores the values indicated in the comments

  signed char s124 = 124; // +124
unsigned char u124 = 124; // +124
  signed char s225 = 225; //  -31
unsigned char u225 = 225; // +225
  signed char s340 = 340; //  +84
unsigned char u340 = 340; //  +84