Bit Addition Manual

Quick start

Click on switches to turn their respective bits on (1) and off (0)

Each row of 8 switches represents an 8-bit number (Addend1 and Addend2)

Whenever any bit is turned on or off, the lights show the new calculated binary addition of Addend1 and Addend2

Each light at the top (Carry) indicates whether a 1 was carried from the column immediately to the right

The Partial sum lights show the result of adding Carry to Addend1 in each column

The lights at the bottom (Sum) represent the binary addition of Partial sum and Addend2

Things to try

Starting with all bits off (0), click the right-most bit of Addend1 to turn it on (1)

You are now adding 00000001 and 00000000

The Carry light for the right-most column will be off (0)

The Partial sum light in the same column will be on (1; the result of Carry + Addend1)

The Sum light in the same column will be on (1; Partial sum + Addend2)

Therefore, the result of adding 00000001 and 00000000 is 00000001

Now, click the right-most bit of the other addend so that you are adding 00000001 and 00000001

The Carry light for the right-most column is still off (0)

The Partial sum light in the right-most column is on (1; the result of Carry + Addend1)

But the Sum light in the right-most column is now off (0; the result of Partial sum + Addend2)

The Carry light in the next column to the left is now on (1)

The Partial sum light in that column is now on (1; Carry + Addend1)

The Sum light in that column is now on (1; the result of Partial sum + Addend2)

Try other combinations of switches and keep reading to understand what's happening

How does this all work? Understanding numbers, digits, and bases

What are binary numbers?

A binary number is composed of binary digits

A binary digit has 2 possible values: 0 or 1

A binary number can contain an infinite number of binary digits

We can interpret the values of binary digits in many ways, but in this app we will interpret them exclusively as numerical and logical values

Why are binary numbers used in computing?

In an electronic circuit, it is more reliable to measure whether a circuit is 'turned on' or 'turned off' than it is to measure its potential (voltage) or current (amperage)

Although many transistors and other electronic devices can allow a range of voltage or current in different parts of a circuit, it is very difficult to consistently measure those values and interpret them as numbers

So,

Computer engineers use specialized transistor circuits that behave more like on/off switches than valves,

And, since binary digits (bits) are great for representing on/off states as 1 or 0,

We can group binary digits together to represent numbers, characters, pixels, etc.

How do binary numbers (and numbers from other bases) work numerically?

We can count and perform arithmetic operations in binary (radix or base 2) just as we can in decimal (base 10) or any other base greater than 1

Base refers to the number of different values that a single digit can represent

In base 10, a digit can represent 10 possible values using the numeric symbols (numerals) 0, 1, 2, 3, 4, 5, 6, 7, 8, 9

In base 2, a digit can represent only 2 possible values: 0, 1

Numbers written in any base use 'places' with values increasing incrementally by powers of the base, moving right to left.

In a base 10 number, the powers increase toward the left like this (negative powers also follow this pattern but we're disregarding them here):

...	5	4	3	2	1	0	Power of 10
...	100000	10000	1000	100	10	1	Base 10 value

In base 2, they work like this:

...	5	4	3	2	1	0	Power of 2
...	32	16	8	4	2	1	Base 10 value

When a digit occupies a place, it represents the product of the digit by the place value.

The value of the entire number is the sum of all the place products

For example, the number 47,302 in base 10 works like this:

...	5	4	3	2	1	0	Power of 10
...	100000	10000	1000	100	10	1	Base 10 Value
		4	7	3	0	2	Our number
		40000	7000	300	0	2	Place products

where the decimal sum of the place products 40000 + 7000 + 300 + 0 + 2 returns our base 10 number: 47,302

The same value in base 2 is represented by 1011100011000110:

15	14	13	12	11	10	9	8	7	6	5	4	3	2	1	0	Power of 2
32768	16384	8192	4096	2048	1024	512	256	128	64	32	16	8	4	2	1	Base 10 Value
1	0	1	1	1	0	0	0	1	1	0	0	0	1	1	0	Our number
32768	0	8192	4096	2048	0	0	0	128	64	0	0	0	4	2	0	Place products

where the decimal sum of the place products returns the decimal value 47,302

Adding numbers that share a common base

Let's take a look at how you might explain how base 10 addition works

Here's a very explicit, very generalized base 10 addition algrorithm for values set up like those in Steps 1 through 4 below:

Call the right most column the 'current column'

Loop:

Add the Carry and Addend1 values in the current column

If the sum cannot be expressed in a single base 10 digit,

Add 1 to the value in the Carry row for the next column to the left

Write the remainder of the addition in the Partial Sum row of the current column

Add Partial Sum to Addend2 in the current column

If the sum cannot be expressed in a single base 10 digit,

Add 1 to the value in the Carry row for the next column to the left

Write the remainder in the Sum row of the current column

If the next column to the left contains non-zero values,

Set the current column to the next row to the left and repeat Loop

Otherwise, read the sum of Addend1 and Addend2 from left to right in the Sum row

Here is how the algorithm applies to the addition of 6 and 7:

Step 1. Initializing our table to add 6 and 7.

Carry	0	0
Addend1	0	6
Partial Sum	0	0
Addend2	0	7
Sum	0	0

 

Step 2. Call the right-most column the current column. Add Carry (0) and Addend 1 (6) in the current column. The result 6 fits in 1 base 10 digit so no need to add to Carry in the next column. Write 6 to Partial Sum in the current column

Carry	0	0
Addend1	0	6
Partial Sum	0	6
Addend2	0	7
Sum	0	0

 

Step 3. Add Partial Sum and Addend2 of the current column. The result cannot be expressed in a single base 10 digit so add 1 to Carry in the next column to the left and write the remainder 3 to Sum in the current column

Carry	1	0
Addend1	0	6
Partial Sum	0	6
Addend2	0	7
Sum	0	3

Step 4. Call the next column to the left the current column and repeat the loop (add Carry to Addend1 and place the result in Partial Sum (no need to carry here). Add Partial Sum to Addend 2 and write the result in Sum (again, no carry needed here). Read the result as decimal 13 in the result row

Carry	1	0
Addend1	0	6
Partial Sum	1	6
Addend2	0	7
Sum	1	3

But what does addition mean??

So far we've just explained how base 10 addition works. Unfortunately, a computer can't directly add 2 base 10 numbers together. We have to convert them to base 2 and compute a result using logic operators.

Bitwise logic operators

There are quite a few logic operators out there and an almost endless list of applications for them

Bitwise logic operators take 2 bits as input values and produce 1 bit as an output value (or result)

Here is a good place to start for more information on the history of logic 'gates' in digital electronics

In digital computing, logic operators define the results of combining 2 bit values

Instead of 'adding' bits together, we typically combine them using one or more logic operators to achieve some desired effect

These kinds of operations are used extensively in remote sensing and GIS

The OR operator

The following table is a 'truth table' for a logic operation (in this case the OR operation)

It shows all the possible results for all the possible input patterns

Input 1	Operator	Input 2	Result
1	OR	1	1
1	OR	0	1
0	OR	1	1
0	OR	0	0

Suppose you want to find all land parcels adjacent to either Main St. or 1st Ave

If one or both of those conditions is true for a given house, then the query is satisfied and the house is highlighted on the map layer

If neither is true, the house is not highlighted

If you think of 1 as being 'true' and 0 as 'false', then you can see the correspondence of this query with the OR truth table

Bitwise comparisons are much more straightforward

In the following bitwise OR operation on 2, 8-bit binary numbers, the result is 1 for any place where one or both digits are 1

We only get a 0 if both input values are 0:

Input 1	1	0	0	1	0	0	1	1
Input 2	1	1	1	0	1	0	0	1
OR Result	1	1	1	1	1	0	1	1

The AND operator

Input 1	Operator	Input 2	Result
1	AND	1	1
1	AND	0	0
0	AND	1	0
0	AND	0	0

Suppose your GIS query is 'Show me all houses with paid off mortgages on Main St.'

Houses should show up only if both 1) a house is paid off and 2) it's located on Main St.

A bitwise AND of our 2 inputs gives the following results:

Input 1	1	0	0	1	0	0	1	1
Input 2	1	1	1	0	1	0	0	1
AND Result	1	0	0	0	0	0	0	1

The XOR operator

XOR, or 'exclusive or' is very handy for binary addition

Its truth table looks just like the one for OR except that if both input values are 1, the result is 0:

Input 1	Operator	Input 2	Result
1	XOR	1	0
1	XOR	0	1
0	XOR	1	1
0	XOR	0	0

Basically it says that if either, but not both of the 2 inputs are 1 (or true), the result is 1

Otherwise, the output is 0 (or false)

Input 1	1	0	0	1	0	0	1	1
Input 2	1	1	1	0	1	0	0	1
XOR Result	0	1	1	1	1	0	1	0

This is key to understanding how my bit 'addition' algorithm works

The binary addition algorithm

Let's start with base 10 addition:

1 + 1 = 2

This is perfectly acceptable since base 10 has a numeral, 2, that represents a value equivalent to 1 + 1

But what about base 2?

Binary (base 2) arithmetic can only use 2 values, 1 and 0

These are the only 2 values that digital circuits can represent in modern computers

In binary addition:

1 + 1 = 10

Let's lay out the input values and the result in a table showing binary place values:

Binary place values	32	16	8	4	2	1
Addend1	0	0	0	0	0	1
Addend2	0	0	0	0	0	1
Sum	0	0	0	0	1	0

And now, let's follow the order of operations that can produce the result, using the same pattern as our base 10 example above

Step 1. Initializing our table to add binary 1 and 1.

Step 2. Call the right-most column the current column. Add Carry (0) and Addend 1 (6) in the current column. The result 1 fits in a single base 2 (binary) digit so no need to add to Carry in the next column. Write 1 to Partial Sum in the current column

Step 3. Add Partial Sum and Addend2 of the current column. The result cannot be expressed in a single base 10 digit so add 1 to Carry in the next column to the left and write the remainder 0 to Sum in the current column

Step 4. Call the next column to the left the current column and repeat the loop (add Carry to Addend1 and place the result in Partial Sum (no need to carry here). Add Partial Sum to Addend 2 and write the result in Sum (again, no carry needed here). Read the result as decimal 10 in the result row

Ok, but how do you actually get the adding and carrying to work in each step?

Let XOR produce the result for the Partial sum and Sum rows and let AND produce the result for the Carry row

Starting with Step 2, we replace the text with the actual bitwise operations:

Step 2. In the right-most column, combine Carry and Addend1 with XOR to provide the value for the Partial Sum row:

0 XOR 1 = 1

Then combine Carry and Addend1 with AND to provide the value for Carry in the next column to the left:

0 AND 1 = 0

Step 3. Still in the right-most column, combine Partial Sum and Addend2 with XOR to provide the value for Sum:

1 XOR 1 = 0

Then combine Partial Sum and Addend2 with AND to provide the value for Carry in the next column to the left:

1 AND 1 = 1

Step 4. Move to the next column to the left and repeat Steps 2 and 3:

1 XOR 0 = 1 (Carry XOR Addend1, result stored in Partial Sum)

1 AND 0 = 0 (no carry to the column to the left)

1 XOR 0 = 1 (Partial Sum XOR Addend2, result stored in Sum)

We would repeat these steps for the remaining columns but since they're all set to 0 for both addends, we can stop here

Reading the result column we see the answer is 10.

What happens if the last column on the left requires a carry?

That's called overflow, where the result is too big to store in the number of bits we provide for representing numbers--too bad!!

Overflow will always be a problem whenever you work with numbers that have an infinite range (integers, real numbers, transcendental numbers, etc.)

It's your job as a programmer to make sure that any math operations you perform don't cause an overflow condition

It doesn't matter what base you're working with; a finite memory space can't hold an infinite range of numbers!

Egad! Do I have to do this every time I want to add 2 numbers together?

No! Modern high-level computing languages like Python take care of all these details for you

The Python interpreter (a program, usually a version of CPython written for your particular computer and operating system) translates your code into Python bytecode and then runs it on your system

CPython itself is a machine language program (written originally as a C program that has been compiled (or translated) to machine language

In the end, your Python code actually runs within the CPython 'virtual machine'

So, the Python statement

result = 3 + 4

computes the addition and stores the sum in result without your needing to do anything else

EXCEPT to remember that you're still working with finite memory spaces!!!

We can go a long way in Python without working at the bit level