Binary Addition

Section 4.4 Binary Addition

With slight modifications can use our normal algorithms for doing binary math. Take addition for example. We are familiar with adding base ten numbers column by column, carrying to the next column any time we get a value of 10 or more in the present column. In base two, each column can only store a 0 or a 1. So any value over 1 means we have to carry. 2 (

10_{2}

) means “zero in this column, carry a 1”, 3 (

11_{2}

) means “one in this column, carry 1 to the next column.”

🔗

Below is shown the process of adding 15 (

1111_{2}

) to 6 (

0110_{2}

🔗

Animation used by permission of Virginia Tech

🔗

Table 4.4.1. Adding in base 2

Carries	1	1	1	0
First number		1	1	1	1
Second number		0	1	1	0
Sum	1	0	1	0	1

🔗

Subsection 4.4.1 Overflow

One thing we do have to watch out for any time we have a fixed number of bits to represent numbers is overflow. That is when a value becomes too large to store in the bits we have. When we are doing math on paper, we can add as many digits as we need. But when an electric circuit is doing math, there is a fixed number of digits that can be represented. For example, say we are using 4-bit numbers and we try to add 9 + 9 (

1001_{2}

1001_{2}

) - any bits past 4 need to be discarded.

🔗

1  1    (Carries)
 1001   (9)
+1001   (9)
10010   (18)
Keep only the last 4 bits:
 0010   (2 !?!)

9 + 9 gave us just 2 because we can not store the bit that should represent 16. This is an overflow error. Circuits in computers have to detect when there is a carry-out of the last digit so it can signal an error and software developers have to be careful to watch for these errors. Computers use many more than 4 bits to store each number, but any fixed representation will have limits to how big a value can be stored.

🔗

Real software can have bugs when the developers do not use enough bits to represent numbers. Youtube engineers had to add more bits to the storage

https://www.wired.com/2014/12/gangnam-style-youtube-math/

for view counts of the video Gangnam Style when the view counter for the video was threatening to overflow the 32 bits they had originally used.

🔗

You can also see an overflow bug at work in the game Hearthstone.

http://www.codeproject.com/Articles/802368/Integer-Overflow-in-Hearthstone

🔗