4. Basic Unsigned Numeric Encoding

In order to represent and manipulate numeric values within the circuits of a computer system it is necessary to use some coding scheme whereby each number can be represented or "encoded" by the pattern of electrically on/off states in a collection of circuits. For a computer, the simplest and fastest scheme for encoding numeric values is the Unsigned Binary Encoding scheme.

Binary Encoding

replacement or representation of some discrete data object (number, character, etc.) by an on/off circuit pattern
a "binary encoding system" is a one-to-one function for encoding a set of related data object (for example, all integer values between 0 and 100 inclusive, or all the letters of the alphabet) into unique binary patterns.

Number of Circuits Required for Encoding

each circuit will be in either one of two states : "on" or "off" (for convenience we will write these using 1 for "on" and 0 for "off")
only two possible patterns are possible for a single circuit: 0 and 1
with two circuits, four patterns become possible: 00, 01, 10, and 11
each time another circuit is added, the number of patterns doubles; half of the new patterns will have this additional circuit turned on and the other half will have it turned off.

Number of Circuits	Number of Patterns
1	2
2	4
3	8
4	16
....	....
8	256
10	1024 (1K)
16	65536 (64K)
20	1048576 (1M)
n	2ⁿ

in order to encode a collection of data objects, the encoding scheme must have at least as many patterns available as there are objects to be encoded
for example, if we wished to encode the integer values from 0 to 9, a minimum of 4 circuits (providing 16 patterns) would be required

The Decimal Odometer Analogy

most cars have an odometer which records the total distance traveled (in either kilometres or miles)
a typical odometer might have 6 digit "wheels" with the right most wheel rotating most rapidly from 0 up to 9 and back to 0 again every 10 kilometers (or miles); the next wheel to the left would only make this change every 100 kilometers; etc.
a 6 digit odometer only has 1,000,000 different values (0 to 999999 inclusive); a car driven 6,372,945 kilometers and one driven 7,372,945 kilometers would have the same odometer reading
notice that the 6 digit wheels are built-into the car, and do not automatically expand to 7 digit wheels once the car passes 999,999 kilometers
because the decimal positional notation is so familiar to use, we recognize without much thought that an odometer reading of 372945 means

3 x 100000
+7 x 10000
+2 x 1000
+9 x 100
+4 x 10
+5 x 1

each digit wheel of an odometer is analogous to a single circuit
where each digit has 10 different values (0 to 9), a single circuit only has 2 ( 0 and 1)
the odometer within a car is analogous to a "word" in a computer system (i.e. a word in a computer system is the basic unit for representation of a simple numeric value)
different makes of cars may have a different number of wheels in their odometers; different makes of computers may have a different number of circuits (bits) in their words
the number of circuits (bits) in a specific computer's word unit is "fixed" and can not be modified just because all the patterns have been used up
a 6-bit word with a pattern of 100101, if viewed as a positional system analogous to the 6-digit odometer, would mean

1 x 32 (2 x 2 x 2 x 2 x 2)
+0 x 16(2 x 2 x 2 x 2)
+0 x 8(2 x 2 x 2)
+1 x 4(2 x 2)
+0 x 2
+1 x 1

Unsigned Binary Encoding

notice that to this point we have not been concerned with representing negative values; we have been dealing with "unsigned" (i.e. assumed to be 0 or positive) numbers
the "bits" or circuits of a computer "word" are imagined to be lined up in a horizontal row regardless of their actual physical positioning
each bit has its own "weight" with the right-most bit having a weight of 1 and every other bit having a weight which is double that of the bit to its immediate right
notice that the sum of the weights of all bits to the right of any specific bit is always one less that the weight of that bit
in the (unsigned) binary encoding scheme, the numeric value being encoded is the sum of the weights of the bits which are turned on
for example using an 8-bit "word"

pattern in word:	off (0)	on (1)	off (0)	off (0)	on (1)	on (1)	off (0)	off (0)
weight	128	64	32	16	8	4	2	1

the value of this encoded word (01001100) would be 64 + 8 + 4 = 76

conversely to encode a particular value, for example 137, in an 8-bit word using the (unsigned) binary encoding scheme
the bit with weight 128 must be on (since the sum of all the remaining bits only adds up to 127)
if the bit with weight 128 is on, then the remaining bits must contain a pattern that adds up to 137 - 128 = 9
the bits with weights 64, 32, and 16 must be off, since if any of them were on the total would add up to too much
the bit with weight 8 must be on, leaving 9 - 8 = 1 to be represented by the remaining bits
the bits with weights 4 and 2 must be off
the bit with weight 1 must be on
therefore, the 8-bit (unsigned) binary encoded pattern for 137 is 10001001

weight	128	64	32	16	8	4	2	1
pattern	1	0	0	0	1	0	0	1

Multi-Column Addition

multi-column addition is done one column at a time, starting with the right-most column
the addition of a column of digits results in two values: the "column result" and a "carry" value which must be included when adding the next column to the left.
when adding two numbers, each column except for the right-most, requires the addition of three digits, two from the numbers and a (possibly zero) carry from the column to its right
therefore, the addition of two (unsigned) binary values requires the ability to add three single bits at a time

3-Bit Addition: The 8 Possible Input Combinations and Their Outputs
bit values being added (carry in from previous column)	0 0 0	0 0 1	0 1 0	0 1 1	1 0 0	1 0 1	1 1 0	1 1 1
column result	0	1	1	0	1	0	0	1
carry to next column	0	0	0	1	0	1	1	1

Examples:
(4-bit "words")

Multi-Column Subtraction

although not always taught in primary school in this fashion, subtraction can be done in a similar manner, one column at a time (primary school subtraction often teaches children to skip over several (zero valued) columns when "borrowing" enough to perform a "proper subtraction

3-Bit Subtraction: The 8 Possible Input Combinations and Their Outputs
"Subtrahend" minus "minuend" minus borrow from previous	0 0 0	0 0 1	0 1 0	0 1 1	1 0 0	1 0 1	1 1 0	1 1 1
column result	0	1	1	0	1	0	0	1
borrow from next column	0	1	1	1	0	0	0	1

Examples:
(4-bit "words")

The "Carry" Flag

Addition

as we have already seen, every column in a (binary) addition produces a "carry" signal for the next column
for the left-most column, there is no subsequent column for this signal to go to
if there is a carry (i.e. the carry signal is 1 / the Carry flag is on) out of the left-most column for an addition of two (unsigned) binary encoded values, it means that the actual result is two large to fit into the number of bits/circuits available (for this computer)
the Carry flag should be checked following any addition of (unsigned) binary values, to ensure that the results are correct; the "checking" requires execution of a separate instruction following the addition. For some mythical processor this sequence might look like:

LOAD A FROM @3054 'copy value from memory at address 3054 to ALU working "register" A
LOAD A FROM @4190 'copy value from memory at address 4190 to ALU working "register" B
ADD_TO A FROM B 'replace value in "register" A with sum of original values
IF_CARRY_GOTO ERROR_ROUTINE 'go somewhere else to handle error if it occurred
...value in "register" A is OK

Subtraction

Subtraction works the same way as Addition except that we use a "borrow from next column" signal instead of a "carry to next column"
rather than implement a separate "Borrow" flag, most systems re-use the "Carry" flag to record the final column "need to borrow" indicator
following an (unsigned) binary subtraction, if the Carry flag is on, then

the result is wrong (as an unsigned binary value)
an attempt was made to subtract a larger number from a smaller number

Subtracting and then checking the Carry flag can therefore be used as a method for determining the relative size of two numbers

The "Zero" Flag

in addition to a "Carry" flag, all computer processors have a "Zero" flag (or some functional equivalent).
the "Zero" flag is turned on, when all "result" output bits are turned "off" i.e. when the result is zero; the "Zero" flag will be turned off if any of the result bits are "on"
this flag is set/reset by the bit manipulation operations (OR, AND, XOR, NOT) and by the basic ADD and SUBTRACT operations; other instructions may set/reset the Zero flag, but these vary among different processors.
to test to determine if two values are equal, subtract one from the other and then check the zero flag; if it is on, the values are equal

Multiplication - Double Word Result

binary multiplication is performed as a series of left shifts and additions
notice that when multiplying two 3-digit (decimal) numbers, the result may require as many a 6 digits
similarly when multiplying two 16-bit (unsigned binary encoded) words, the computer's ALU must allow for as many as 32 bits in the result
a simple single-bit flag is not sufficient to handle this problem

Example:
(4-bit "words"
8-bit "double-word" result)

Division - 2 Results

unlike addition, subtraction, and multiplication, Division produces two results: a Quotient and a Remainder when dealing with integers values (such as unsigned binary encoded values)
a computer's execution unit must make some provision for handling this double result; however, the specific method for handling this varies from computer to computer, and otten within a single computer, different instructions may handle this problem in different ways.