Simple operations in binary

Question

How would you perform the mathematical operations +, -, *, / and % in binary using only AND, OR, NAND, NOR, XOR and so on?

I'm not knowledgeable on binary at all, I only really know what the operations do in the most basic sense and how to count up to n.

Answer 1

This is a broad subject. I give you the answer for binary addition (the easiest part)

The addition is divided in cells. Each cell performs the addition of a single bit. It is connected with other cells in order to process the carry in and out. As such, each cell has three inputs and two outputs:

Input

• A, the first input bit
• B, the next input bit
• Ci, the carry in from the calculation to the right, or 0 if it is the least significant bit.

Output

• X, the output bit
• Co, the carry out to the calculation to the left (connected to the carry in)

You can put a truth table for the cell:

  A  B  Ci   X  Co
  0  0  0    0  0
  0  0  1    1  0
  0  1  0    1  0
  0  1  1    0  1
  1  0  0    1  0
  1  0  1    0  1
  1  1  0    0  1
  1  1  1    1  1

And this gives you the following formula's:

• X = (A and not B and not Ci) or (not A and B and not Ci) or (not A and not B and Ci) or (A and B and Ci)
• Co = (not A and B and Ci) or (A and not B and Ci) or (A and B and not Ci) or (A and B and Ci)

Note that you can optimize these boolean expressions.

You can do the subtraction using the same scheme (with borrow instead of carry). Multiplication and division, are harder. As far as I know, a lookup table is often used.

Three connected cells

           A2 B2       A1 B1       A0 B0
            |  |        |  |        |  |
            |  |        |  |        |  |
           ------      ------      ------
       --Co|    |Ci--Co|    |Ci--Co|    |Ci-- 0 (fixed)
       |   ------      ------      ------
       |      |           |           |
      X3     X2          X1          X0