At first glance, this may sound like a silly question—isn’t it just like how we know 2 + 3 = 5? We somehow learned how to count (1, 2, 3, 4, 5…) and we understand addition through counting (and the natural number series). We know that 2 + 3 = 5 because we know that if we start counting at 2, after we count 3 times, we would get to 5. Doesn’t a computer just count in binary numbers?
Well, no.
While a computer can represent numbers in their binary form—combinations of 0s (off/false) and 1s (on/true), how does a computer know the relations between, say, 10 (2), 11 (3), and 101 (5)? How does it know that 10 is followed by 11, 11 is followed by 100, and 100 is followed by 101? A computer knows the logical relations between combinations of 0 and 1 in virtue of how we construct its logic circuits, but how can it go from this sort of relations—which are essentially relations between Booleans—to the relations between numbers? If it doesn’t know the relations between numbers, how does it add?
To put the question differently, how does a computer know that adding 10 and 11 should result in 101? We can arbitrarily decide that a certain combination of 0s and 1s represents addition, but what is the computer supposed to do upon seeing its version of the “+” sign? In other words, how should the computer manipulate the 0s and 1s in the two input numbers to yield a new number, a new combination of 0s and 1s?
Before answering these questions, let’s consider how we, humans, add two binary numbers together.
Binary Addition by Human
The addition of binary numbers is very much like the addition of “normal” (decimal) numbers. Suppose we add 10 and 11. The first digit of 10 is 0 and the first digit of 11 is 1. 1 + 0 = 1, so we know that the first digit of the result should also be 1:
10 10
+ 11 -> + 11
= ??? = __1The second digits of 10 and 11 are both 1. 1 + 1 = 10 (remember, we are adding in binary—there is no 2 in the binary system). So we know that in the result, there is a 1 that gets carry over to the third digit, and there is nothing left for the second digit:
10 10 `10
+ 11 -> + 11 -> + 11
= ??? = __1 = _01The third digits of 10 and 11 are both 0. So the third digit of the result will be 0 + 1 (the carry) = 1
10 10 `10 10
+ 11 -> + 11 -> + 11 -> + 11
= ??? = __1 = _01 = 101Notice that while we do know the relations between binary numbers 10, 11 and 101 (e.g., 10 is followed by 11, 101 is greater than 11…), such knowledge is not necessary for performing the operation above.
How may a computer mimic this operation? We can think of this operation as embodying two kinds of “sub-operation”—adding 0 and 1 (no carry) and adding 1 and 1 (carry). Adding 0 and 1 at the nth digit of the input numbers yields a 1 at the nth digit of the resulting output. Adding 1 and 1 at the nth digit of the input adds 1 to the (n+1)th digit of the output. A computer can mimic these sub-operations by logic and shift operations. Before we dive into exactly how that works, let’s review what logic and shift operations are.
Logic and Shift Operations
Logic operators: AND and XOR
A logic operation takes input(s) that is/are either true or false (represented as 0 and 1 in a computer) and produces an output that is either true or false. For the purpose of this article, we will only look at two logic operators: AND and XOR.
To understand AND, let’s consider its analogue in English—“and.” We often use “and” to connect two declarative sentences together to form a new declarative sentence (e.g., “Cody is a pug and a pug is a dog”). A declarative sentence can be true or false (e.g., if Cody is not a pug, then the sentence “Cody is a pug” is false).
Now, “Cody is a pug and a pug is a dog” is true if, and only if, both “Cody is a pug” and “A pug is a dog” are true. In other words, whether “Cody is a pug and a pug is a dog” is true depends on whether the parts that form the sentence are true.
Abstract away the content of these English sentences, we have something like the following:
- If A is true and B is true (where A and B represent certain declarative sentences), A and B is true.
- If A is true and B is false, A and B is false.
- If A is false and B is true, A and B is false.
- If A is false and B is false, A and B is false.
And we can describe English sentential connective “and” in a table—a truth table—like this:
A | B | A and B
---------------
T | T | T
T | F | F
F | T | F
F | F | FNow, we can understand logic operator AND in a similar fashion. The input has two bits and the output has one bit. Whether the output is 0 or 1 depends on the “truth” of the input bits. So AND can be described by the following truth table (A and B represent the input bits):
A | B | A AND B
---------------
1 | 1 | 1
1 | 0 | 0
0 | 1 | 0
0 | 0 | 0
Similarly, XOR has an English analogue—the exclusive “or,” as in “either A is true or B is true, but not both.” XOR can be described by the following truth table:
A | B | A XOR B
---------------
1 | 1 | 0
1 | 0 | 1
0 | 1 | 1
0 | 0 | 0
Bit Shifting
Metaphorically speaking, a shift operation “moves” a combination of bits to the “left” or to the “right.” For example, if we shift 10101 to the left by one bit, we get 101010. If we shift 10101 to the right by one bit, we get 1010.
When a computer represents a binary number with a combination of bits, shifting the bits to the left by one bit would in effect multiplies the binary number by 2, and shifting the bits to the right by one bit would in effect divides the binary number by 2.
Now that we understand what logic and shift operations are, let’s talk about how a computer actually adds.
Binary Addition by Computer
Suppose a computer is to add 10 and 11 together (for the sake of readability, let’s assume that the computer represents each number in four bits). What should happen next? Remember, the computer is going to mimic the following “sub-operations”: 0 + 1 = 1 (no carry) and 1 + 1 = 10 (carry).
To begin, let’s stack the two numbers up and compare them digit by digit:
0010
0011There are two things to notice. First, there is a 0 + 1 = 1 operation at the first digit of the input numbers. The computer can see that using the XOR operator:
XOR 0010
0011
= 0001Second, there is a 1 + 1 = 10 operation at the second digit of the input numbers. The computer can see that using the AND operator:
XOR 0010 | AND 0010
0011 | 0011
= 0001 | = 0010After that, the computer can carry the 1 over from the second digit to the third digit by shifting the result of the AND operation (i.e. 0010) to the left by one bit:
XOR 0010 | AND 0010 | << 0010
0011 | 0011 |
= 0001 | = 0010 | = 0100Then the computer can add the result of the shift operation (the carry, 0100) to the result of the XOR operation (i.e. 0001) by another XOR operation:
XOR 0010 | AND 0010 | << 0010
0011 | 0011 |
= 0001 | = 0010 | = 0100XOR 0001
0100
= 0101
Now, to check and see whether there is any more carry to handle after handling the carry it found above, the computer can perform another AND operation on the result of the shift operation and the result of the first XOR operation:
XOR 0010 | AND 0010 | << 0010
0011 | 0011 |
= 0001 | = 0010 | = 0100XOR 0001 | AND 0001
0100 | 0100
= 0101 | = 0000 <- No carry
Then, boom! The computer gets the result of adding 10 and 11 together, 101, using logic and shift operations only.
To summarize, from a computer’s perspective, adding two numbers together is a sequence of logic and shift operations. Unlike us, a computer need not know that 5 is 3 numbers after 2 before it can figure out 2 + 3 = 5. In other words, a computer need not know the relations between numbers before it can add. It just needs to know Boolean logic (and how to move bits left and right).
An Illustration in JavaScript
Bitwise operators operate on binary numerals at the level of their individual bits. JavaScript has bitwise operators for both logic and shift operations. These operators treat a numerical value as a 32-bit binary integer. Here is an illustration in JavaScript of what we have talked about so far.
A philosophical note: I am not taking a side in the debate about whether a computer can actually know, see or figure out anything. I just think that putting quotation marks everywhere would be obnoxious.
