Prerequisite

Knowledge of the concepts from the tutorial Base n Numbers are a prerequisite for this tutorial

Section 1 Addition of Base-n Numbers

The trick to doing base-n addition is to "fake" it by doing decimal arithmetic in your head or on a piece of scratch paper -but writing down answers in base-n.


        Review of Decimal Addition
        Procedure to Add Two Base-n Numbers
        Example Adding Base-n Numbers

 

Review of Decimal Addition (1.1)

Here are the principles of adding two decimal numbers:
  1. Line up the numbers from right to left. If one number is shorter, extend it by adding leading zeros to the front of the shorter number.

  2. Work from right to left - doing the same addition and carry operation in each column.

  3. Add the two digits in the same column and also add the carry at the top of the column (if any).

  4. A one digit answer is simply recorded at the bottom of the same column.

  5. A two digit answer requires you to subtract 10 from the sum and record the remainder at the
    bottom of the same column.

  6. A two digit answer also requires you to record a carry of 1 in the next column over to the left.

  7. Any extra carry is recorded in a new column on the left.

Of course no one actually does every step for subtracting 10. Instead they split the answer into two digits, record the right hand digit in the same column and carry the left hand digit into the column over one place left.

HOWEVER, you need to get used to thinking of the step as "subtracting ten". So for example:

Procedure to Add Two Base-n Numbers (1.2)

Here is how to add together two (unsigned) base-n numbers:
  1. Line up the numbers from right to left. If one number is shorter extend it by adding leading zeros to the front of the number.

  2. Work from right to left - doing the same addition and carry operation in each column.

  3. Add the two digits in the same column and also add the carry at the top of the column (if any).

  4. Compare the sum (in your head) with the radix n.

  5. A sum less than n is just recorded at the bottom of the same column.

  6. A sum greater or equal to n requires several steps:

  7. Any extra carry past the leftmost column is not recorded in the answer. It is called the carry out and is usually stored somewhere else on the computer.

    The answer must have the same number of digits as the two operands.

Example Adding Base-n Numbers (1.3)

Here is an example of adding B2C59 and 346A2 in base 13 : 
         carry row:  1 0 1 1 0
      first number:    B 2 C 5 9
     second number:    3 4 6 A 2
     --------------    ---------
               sum:    1 7 6 2 B
With a detailed explanation:

Section 2 Subtraction of Base-n Numbers

The trick to doing base-n subtraction is to "fake" it by doing decimal arithmetic in your head or on a piece of scratch paper -but writing down answers in base-n.


        Revision of Decimal Subtraction
        Procedure to Subtract Two Base-n Numbers
        Example Subtracting Base-n Numbers

 

Revision of Decimal Subtraction (2.1)

Here is a new way to subtract decimal integers:
  1. Line up the numbers from right to left. If one number is shorter extend it by adding leading zeros to the front of the number.

  2. Work from right to left - doing the same subtraction and borrow operation in each column.

  3. Subtract the two digits in the same column and also subtract the borrow at the top of the column (if any). You may get a negative answer. This is OK, do not borrow a ten to avoid the negative answer - just do the signed arithmetic.

  4. If the difference is positive or zero - then just record it at the bottom of the column and record a borrow 0 in the next column left.

  5. If the difference is negative - then add 10 to it and record the result (which will no longer be negative) at the bottom of the column. Also record a borrow 1 in the next column left.
Try this out for a problem like 3100-2957 and then also do it the way you learned in grade school. You should get the same answer if you are doing it right.

Procedure to Subtract Two Base-n Numbers (2.2)

Here is how to subtract two (unsigned) base-n numbers:
  1. Line up the numbers from right to left. If one number is shorter extend it by adding leading zeros to the front of the number.

  2. Work from right to left - doing the same subtraction and borrow operation in each column.

  3. Subtract the two digits in the same column and also subtract the borrow at the top of the column (if any).

  4. A zero or positive difference is just recorded at the bottom of the same column.

  5. A negative difference requires several steps:

  6. Any extra borrow past the leftmost column is not recorded in the answer. It is called the borrow out and is usually stored somewhere else on the computer. The answer must have the same number of digits as the two operands.

Example Subtracting Base-n Numbers (2.3)

Here is an example of computing B2C59 less 346A2 in base 13 : 
        borrow row:  0 1 0 1 0
      first number:    B 2 C 5 9
     second number:    3 4 6 A 2
     --------------    ---------
        difference:    7 B 5 8 7
With a detailed explanation:

Section 3 Digit Min and Max Operations

Except for binary numbers, these operations are fairly useless. However, they are very simple to do:

        Digit Minimum Operation
        Digit Maximum Operation

Digit Minimum Operation

This operation takes the smallest of corresponding pairs of digits.
  1. Line up the numbers from right to left. Both numbers MUST have the same number of digits. The operation is not defined otherwise.

  2. Work in any direction you want - doing the same operation in each column.

  3. Find the smallest of the two digits in the same column and place that in the answer at the bottom of the same column.

  4. There is no carry or borrow or any kind of connection between different columns. This is called a digit-wise operation.
Here is an example of the digit min of B0C59 and 34A52 in base 13 : 
      first number:    B 0 C 5 9
     second number:    3 4 A 5 2
     --------------    ---------
         digit min:    3 0 A 5 2
This is simple enough not to need a detailed explanation.

Digit Maximum Operation

This operation takes the largest of corresponding pairs of digits:
  1. Line up the numbers from right to left. Both numbers MUST have the same number of digits. The operation is not defined otherwise.

  2. Work in any direction you want - doing the same operation in each column.

  3. Find the largest of the two digits in the same column and place that in the answer at the bottom of the same column.

  4. There is no carry or borrow or any kind of connection between different columns. This is called a digit-wise operation.
Here is an example of the digit min of B0C59 and 34A52 in base 13 : 
      first number:    B 0 C 5 9
     second number:    3 4 A 5 2
     --------------    ---------
         digit max:    B 4 C 5 9
This is simple enough not to need a detailed explanation.

Section 4 Binary Logic

When performed with binary numbers, the digit min and digit max operations have special names. The three common bit-wise operations are:

The three operations can be formed on numbers written in any base by first converting them to binary, then performing the desired operation, and finally converting the asnwer back to the original base.

 

THUS NOTE:

Except for Binary ITSELF,
The binary operations CANNOT be done
in the original number base.

Here are some examples in binary: 
        11001010        11001010         11001010
        01101100        01101100         01101100          11010110
   -------------    ------------    -------------    ---------------
   and: 01001000    or: 11101110    xor: 10100110    cmpl: 00101001
Here are some examples in hexidecimal: 
         B6 = 1011 0110        B6 = 1011 0110
         5C = 0101 1100        5C = 0101 1100
    -------------------    ------------------
    and: 14 = 0001 0100    or: FE = 1111 1110


         B6 = 1011 0110
         5C = 0101 1100          C7 = 1100 0111
    -------------------    -------------------
    xor: EA = 1110 1010    cmpl: 38 = 0011 1000

Copyright © 1998 Dr. James F. Wirth

Section 5 Multiply

To multiply numbers in some other base, it is strongly suggested that you convert the numbers to decimal, do the operation in decimal and then convert back to the original base.

The discussion here assumes that signed binary numbers are being used so you may need to review the Signed Binary tutorial.

It is possible to do multiplication directly in base-n, but it would require you to memorize the n2 elements of the multiplication tables base-n. For example, in hexidecimal, you would have to memorize 256 values.

When converting to decimal be careful to convert either signed or unsigned as specified. The answers can depend on the signs. Also notice that you can get an answer with twice as many digits as the original two numbers.

On some computers (in particular the ECTC98) the answer is trimmed back to the original size by dropping the left most digits. This can easily lead to the wrong answer - a condition known as multiplicative overflow. Most computers do not automatically detect this error - so be careful!

Here are two examples of eight bit signed multiply on eight bits quantities represented in hexidecimal: 

  Hex   Dec   Hex    Dec
   FA =  -6    9C = -100
   05 =   5    F1 =  -15
 ----------   ----------
   E2 = -30    DC = 1500

where the second problem gives the wrong answer. The correct answer should have been 05DC, but only the right hand eight bits (DC) are kept in the result.

Section 6 Divide and Mod

Both division and modulus in base n should actually be done by converting to decimal, performing the desired arithmetic and then converting the answer back to base n.

The discussion here assumes that signed binary numbers are being used so you may need to review the Signed Binary tutorial.

Some details differ:

Division
Modulus

Division (6.1)

Division in base n should actually be done by converting to decimal, performing the division and then converting the answer back to base n.

Notice that the result of division of base n numbers is another base n integer - and thus integer division must be used.

Here is an example in signed base 16 (hexidecimal). Let us divide the numerator(dividend) FD3B by the denominator(divider) C4.

First we convert to decimal so that:

FD3B gives: -709
C4 gives: -60

Then we use the calculator to divide -709 by -60:

-709 / -60 = 11.8166666666

Next we truncate, because we must use integer division.

truncating gives: 11

Final we convert back to hexidecimal

converting gives: 0B

Thus the answer in hex is:

FD3B / C4 = 0B

 

Modulus (6.2)

Modulus in base n should actually be done by converting to decimal, performing the modulus and then converting the answer back to base n.

However if any of the operands are negative number, then calculating the modulus should be done using the formula:

		X mod Y = X - (X/Y) * Y

where the quotient (X/Y) must be the integer division and where the asterisk * stands for "multiply".

An example

Consider computing the value of:

-103 mod 17

Thus X (see the above formula) is -103 and Y is 17. Thus the formula becomes:

-103 mod 17 = -103 - (-103/17) * 17

BUT, the division must be integer division so that

-103/17 = -6

instead of -6.058823.

Thus the formula becomes:

-103 mod 17 = -103 - -6 * 17

and because you do the multiply first (before the subtract)


-103 mod 17 = -103 - -102
= -1

Thus the value of   -103 mod 17   is -1.

USE a calculator if you have trouble doing negative arithmetic. BUT make sure you use the calculator CORRECTLY.

Leading Zeros

A leading zero is a zero written at the left end of a base-n number which does not contribute to the value of the number (i.e. its translation into decimal).

All zeroes at the left end of an unsigned number are leading zeroes.

The zeroes at the left end of a signed binary/hex number are NOT leading zeros because their presence or absence changes the decimal value of the number.

As an example where left end zeros are not leading zeros consider a signed (twos complement) number written in hexidecimal:

Integer Division

Most computers (and computer languages such as C and C++) get an integer result after they divide one integer by another.

This is called integer division

To do an integer division on a calculator:

  1. First do the indicated division
  2. You may get a fractional part (after the decimal point)
  3. Throw the fractional part away (called truncation)

Thus the division 17/5 does not give 3.4 but rather gives just 3.

On some computers, a negative number is "rounded down" to the next more negative number. This is called "truncating to negative infinity".

However, on Intel based computers, ordinary truncation is used (just throw away the fraction).

Thus the problem -17/5 gives these answers:

It is the negative answer that provides different behavior. Thus the problem 17/5 gives these answers:

with no difference between the Intel based or "negative infinity" computer.