7.4: Binary (base 2)

The other base we commonly use in computer science is base 2, or binary. This is because the basic unit of information in a computer is called a bit, which has only two values, conventionally called either “true" and “false" or “1" and “0". Numbers (as well as everything else) are ultimately represented as colossal sequences of 1’s and 0’s, which are of course binary numbers.

The rules for interpreting place value are the same: \[\begin{aligned} \text{110101}_{2} &= 1 \times 2^5 + 1 \times 2^4 + 0 \times 2^3 + 1 \times 2^2 + 0 \times 2^1 + 1 \times 2^0 \\ &= 1 \times 32 + 1 \times 16 + 0 \times 8 + 1 \times 4 + 0 \times 2 + 1 \times 1 \\ &= \text{53}_{10}.\end{aligned}\] So in binary we have a one’s-place, a two’s-place, a four’s-place, an eight’s-place, and so on. We call the right-most place the least significant bit (LSB) and the left-most the most significant bit (MSB).

Counting up from zero is really just the same as any other base, although it feels a little strange in binary because you “roll over" so often:

\(\texttt{0}_2\)	zero
\(\texttt{1}_2\)	one
\(\texttt{10}_2\)	two
\(\texttt{11}_2\)	three
\(\texttt{100}_2\)	four
\(\texttt{101}_2\)	five
\(\texttt{110}_2\)	six
\(\texttt{111}_2\)	seven
\(\texttt{1000}_2\)	eight
\(\texttt{1001}_2\)	nine
⋮	⋮

Converting to and from decimal

Converting from binary to decimal was demonstrated above (with \(110101_2=53_{10}\).) To go the other way, we follow the algorithm from page . Let’s try it for the decimal number 49:

1. (Step 1) We first compute 49 mod 2. Doing “mod 2" is easy: you just see whether the number is even or odd. In this case, it’s odd, so the remainder is a 1:

   1

2. (Step 2) Now divide 49 by 2 and take the floor, which gives \(\lfloor \text{49} \div 2 \rfloor = 24\). It’s not zero, so we perform step 2.2: make 24 our new value, move our pencil to the left of the 1, and go back to step 1.

3. (Step 1) Compute 24 mod 2. Since 24 is even, this is zero, which we write down to the left of the 1:

   01

4. (Step 2) Divide 24 by 2 and take the floor, which gives \(\lfloor \text{24} \div 2 \rfloor = 12\). Make 12 our new value, move our pencil to the left of the 0, and go back to step 1.

5. (Step 1) Compute 12 mod 2. Since 12 is even, this is zero, which we write down:

   001

6. (Step 2) Divide 12 by 2 and take the floor, which gives \(\lfloor \text{12} \div 2 \rfloor = 6\). Make 6 our new value, move our pencil to the left of the 0, and go back to step 1.

7. (Step 1) Compute 6 mod 2. Since 6 is even, this is zero, which we write down:

   0001

8. (Step 2) Divide 6 by 2 and take the floor, which gives \(\lfloor \text{6} \div 2 \rfloor = 3\). Make 3 our new value, move our pencil to the left of the 0, and go back to step 1.

9. (Step 1) Compute 3 mod 2. Since 3 is odd, this is one, which we write down:

   10001

10. (Step 2) Divide 3 by 2 and take the floor, which gives \(\lfloor \text{3} \div 2 \rfloor = 1\). This still isn’t zero, so make 1 our new value, move our pencil to the left of the 0, and go back to step 1.

11. (Step 1) Compute 1 mod 2. Since 1 is odd, this is one, which we write down:

    110001

12. (Step 2) Divide 1 by 2 and take the floor, which gives \(\lfloor \text{1} \div 2 \rfloor = 0\). We’re done. The final answer is \(110001_2\). Double-checking our work, we verify that indeed one 32 plus one 16 plus one 1 gives 49, which is what we started with.

Converting to and from hex

That was pretty tedious. But converting back and forth from binary to hex is a snap. That’s because 16 is exactly \(2^4\), and so one hex digit is exactly equal to four binary digits. This isn’t the case with base 10, where one decimal digit is equal to three binary digits… plus a little extra. This “not quite a whole number of digits" thing is what makes converting from decimal to binary (or decimal to hex, for that matter) so awkward.

We most commonly deal with sets of eight bits at a time, which is called a byte. (This is the fundamental unit of storage on pretty much every computer on earth.) Suppose I had the following byte:

\(\texttt{10000110}_2\)

Because one hex digit is exactly equal to four bits, this byte is exactly equal to:

\(\texttt{86}_{16}\)

This is because the byte can be neatly split into two parts: 1000, which corresponds to the hex digit 8, and 0110, which corresponds to the hex digit 6. These two halves are called nibbles — one byte has two nibbles, and each nibble is one hex digit. At a glance, therefore, with no multiplying or adding, we can convert from binary to hex.

Going the other direction is just as easy. If we have:

\(\texttt{3E}_{16}\)

we just convert each hex digit into the corresponding nibble:

\(\texttt{00111110}_2\)

After you do this a while, you get to the point where you can instantly recognize which hex digit goes with which nibble value. Until then, though, here’s a handy table:

nibble	hex digit
0000	0
0001	1
0010	2
0011	3
0100	4
0101	5
0110	6
0111	7
1000	8
1001	9
1010	A
1011	B
1100	C
1101	D
1110	E
1111	F

In case you’re wondering, yes this is worth memorizing.  

Adding binary numbers

Adding two binary numbers is the same as adding in decimal, hexadecimal, or any other base: you just have to know when to “roll over the odometer," which in this case is almost instantly, since the highest value a bit can hold is 1! Let’s give it a shot: \[\begin{array}{*{7}{c@{\hspace{0pt}}}} & 1 & 1& 1&0 &0&1_2\\ +& 0 & 1 & 1 & 0 & 1 & 0_2 \\  \hline &  & & &  &  & ?_2 \\ \end{array}\] A child could follow the rules: when we add two zeroes, we get zero. Adding a one to a zero gives one. Adding two ones gives zero, and a carry to the next significant digit. And adding two ones plus a carry gives a one and a carry. See if you can follow the flow: \[\begin{array}{*{7}{c@{\hspace{0pt}}}} & 1&1 & & &&\\ & 1 & 1 & 1 & 0 & 0 & 1_2 \\ + & 0 & 1 & 1 & 0 & 1 & 0_2 \\ \hline 1 & 0 & 1 & 0 & 0 & 1 & 1_2 \\ \end{array}\]

Capacity

How large a value can a byte store? There are 8 bits, and each one can independently have either of two values (0 or 1), so by the Fundamental Theorem of Counting, there are \(2^8\) different combinations. This works out to 256, but we can’t actually store the number 256 in a byte if we’re using the bit pattern \(\texttt{00000000}_2\) (or \(\texttt{00}_{16}\)) to represent zero. The highest value would be\(\texttt{11111111}_2\) (or \(\texttt{FF}_{16}\)), which is \(256_{10}\).

How do we store a number larger than that? Simply use more than one byte, of course. If we used two bytes of memory, and treated them as concatenated one after the other, that would give us 16 bits, allowing us to store up to the number \(\texttt{0000000000000000}_2\) = \(\texttt{FFFF}_{16}\) = \(\text{65,535}_{10}\). We’d call one of these bytes — the one representing the \(2^0\)’s place up to the \(2^7\)’s place — the least significant byte, and the other one — containing places \(2^8\) through \(2^{15}\) — the most significant byte. Extending to more than two bytes to accommodate even larger numbers is done in the obvious way.

Binary representation schemes

That’s mostly all there is to it. But there’s one thing we haven’t discussed yet, and that’s negative numbers. We know how to represent any positive number (or zero) with an ordinary place value scheme. But how do we store a number like \(-5\)?

There are three different schemes for treating negative numbers, each with its strengths and weaknesses.

Unsigned

The simplest scheme is called unsigned, and it simply means that we don’t allow negative numbers. For one byte, we have 256 different bit patterns at our disposal, and we might just choose to allocate them all to represent positive numbers, so as to get the widest range. This makes sense for, say, a C++ program variable called heightInInches which we know can never meaningfully be negative (no one has a negative height).

The advantage of this scheme is simply that we can represent the greatest possible range of positive numbers, which is sometimes the goal. Each of the alternative schemes carves off a chunk of these available bit patterns and devotes them to representing negative numbers, leaving fewer left over for positive numbers. There’s no free lunch: you have to decide how you want to “spend" your available bit patterns depending on what values you need to represent.

Sign-magnitude

The sign-magnitude scheme is probably the first thing you’d think of to solve the negative number representation problem. We need to store the sign of the number somehow, and a sign is inherently a two-valued thing (either positive or negative), so why not peel off one of the bits and use it to represent the sign? The remaining bits can then be used in the ordinary way to represent the magnitude of the number.

The way this is most often done is to take the left-most bit and use it as the sign bit. This bit now has no other meaning. It can’t “double" as the 128’s place, because then there’d be no way to distinguish between, say, 129 and \(-129\) (each would be represented with 10000001.) No, the sign bit must be considered “spent money," and its expressive power cannot be reclaimed to also represent part of the magnitude. By convention, if the sign bit is 0 this represents a positive number, and a sign bit of 1 represents a negative number. (That might seem counterintuitive, but hey, that’s the way it is.)

So this number in sign-magnitude:

00100110

represents the decimal number 38. That’s because the sign bit (bolded, on the far left) is 0, which means the number is positive. The magnitude of the number is contained in the other 7 bits, which gives 32 + 4 + 2 = 38. This number, on the other hand:

10100110

represents \(-38\). The magnitude is the same, but the sign bit is 1 so this pattern now “means" a negative number.

Clearly we have reduced our range of positive numbers in exchange for the ability to also store negatives. We have 7 bits of range instead of 8, so instead of 255, our highest possible value is merely 127. On the other end, the lowest possible value is \(-127\).

If you have sharp eyes, you may have noticed a discrepancy in the counting. With the sign-magnitude approach, we can hold numbers in the range \(-127\) to 127. But wait: that’s only 255 different values, not 256! Why did we lose one value of expressive power? The answer is that the sign-magnitude scheme has two ways of representing zero. The bit pattern 00000000 is obviously zero, but so is 10000000 (which you might call “negative zero.") Using two different patterns to represent the same value is a little wasteful, but the situation is actually worse than that. Having to account for both patterns means that computer hardware using the sign-magnitude scheme is inevitably more complicated. To compare two bytes to see if they’re equal, you’d think we’d just compare each bit position, and if they were all the same, the bytes would be declared equal, otherwise no. Alas, this is no longer quite that simple. The two zero patterns must be considered numerically equal, so our digital logic now has to contain a special case. “To be equal, all the bits have to be the same…oh, but actually not if the right-most seven are all zeroes in both bytes. In that case, it doesn’t matter what the left-most bit contains." Maddening.

Two’s-complement

This shortcoming in the sign-magnitude scheme is remedied with the two’s-complement scheme, which is the one actually used most often in practice. It’ll seem weird at first — certainly not as intuitive as the first two — but it leads to a critically important feature that we’ll look at shortly.

First, the rules. To interpret a two’s-complement number, you:

1. Look at the left-most bit (just like in sign-magnitude). If it’s a 0, you have a positive number. If it’s a 1, you have a negative number.

2. If it’s a positive number, the other 7 bits give you the magnitude (just like in sign-magnitude).

3. If, however, it’s a negative number, then to discover the magnitude of that negative number you must flip all the bits and add one. This will give you a positive number which is the absolute value of your negative number.

Easy example: take the byte 00100110. The left-most bit is a 0, which means it’s a positive number, and as we discovered above, the remaining 7 bits give a magnitude of 38. So this is the number 38.

Harder example: take the byte 10100110. The left-most bit is a 1, which means it’s negative. Okay: negative what? How do we find the magnitude? Well, we “flip" all the bits (i.e., invert each one from 0 to 1 or vice versa) to get:

01011001

and then add one to the result: \[\begin{array}{*{9}{c@{\hspace{0pt}}}} & & & & & & & 1 & \\ & 0 & 1& 0 & 1 & 1 & 0 & 0 & 1 \\ + & &  & &  & & && 1\\ \hline & 0 & 1 & 0& 1 &1 &0 &1 & 0\\ \end{array}\] This black magic produces the value \(\texttt{01011010}_2\), which converts to \(90_{10}\). This means that the original number, 10100110, corresponds to the value –90.

“Flipping all the bits and adding one" is the cookbook procedure for taking the complement (negative) of a number in the two’s-complement scheme. It works in reverse, too. Let’s start with 90 this time and crank through the process again, making sure we get –90.

Start with the binary representation of \(90_{10}\): \[\begin{array}{*{8}{c@{\hspace{0pt}}}} \texttt{0} & \texttt{1} & \texttt{0} & \texttt{1} & \texttt{1} & \texttt{0} & \texttt{1} & \texttt{0} \\ \end{array}\] Flip all the bits to get: \[\begin{array}{*{8}{c@{\hspace{0pt}}}} \texttt{1} & \texttt{0} & \texttt{1} & \texttt{0} & \texttt{0} & \texttt{1} & \texttt{0} & \texttt{1} \\ \end{array}\] and finally add one to the result: \[\begin{array}{*{9}{c@{\hspace{0pt}}}} & & & & & & & \texttt{1} & \\ & \texttt{1} & \texttt{0} & \texttt{1} & \texttt{0} & \texttt{0} & \texttt{1} & \texttt{0} & \texttt{1} \\ + & & \texttt{ } & \texttt{ } & \texttt{ } & \texttt{ } & \texttt{ } & \texttt{ } & \texttt{1} \\ \hline & \texttt{1} & \texttt{0} & \texttt{1} & \texttt{0} & \texttt{0} & \texttt{1} & \texttt{1} & \texttt{0} \\ \end{array}\] We get 10100110, which was precisely the number we originally began with, and which we have already determined represents –90.

Now you may ask what we gain from all this. Surely this scheme is considerably more convoluted than the simple idea of reserving one bit as a sign bit, and treating the rest as a magnitude. But it turns out there is indeed a method to the madness. Strange as it sounds, a two’s-complement representation scheme allows us to perform addition and subtraction with a single operation.

In first grade (or so), you learned the procedure for adding multi-digit numbers, which we’ve followed several times in this chapter. It involves adding the digits right-to-left and possibly “carrying." Then in second grade (or so), you learned the procedure for subtracting multi-digit numbers. It involves subtracting the digits right-to-left and possibly “borrowing." If you’re like me, you found adding easier than subtracting. It’s easy to just carry the one, but to borrow requires looking at the digit to the left, making sure that you can borrow from it (i.e., that it’s not already 0), borrowing from further left until you actually find an available non-zero value, hoping the number on the bottom is actually less than the one on the top (because otherwise you have to switch the order and then add a negative sign to the result), and keeping all of that straight as you march down the line.

Even if you didn’t find subtracting more difficult than adding, though, you can’t argue that it’s still a completely different algorithm, with different rules to follow. In computer hardware, we have to implement different circuitry to perform each operation, which is more difficult, costly, error-prone, and power-draining.

The wonderful thing about two’s-complement, however, is that with this scheme we actually never need to use the subtraction algorithm. If we want to subtract two numbers — say, \(24 - 37\) — we can instead take the complement of the second number and then add them. Instead of \(24-37\) we compute \(24 + (-37)\).

Let’s see it in action. Using conversion procedures, we can figure out that \(24_{10}\) is: \[\begin{array}{*{8}{c@{\hspace{0pt}}}} \texttt{0} & \texttt{0} & \texttt{0} & \texttt{1} & \texttt{1} & \texttt{0} & \texttt{0} & \texttt{0} \\ \end{array}\] and that positive \(37_{10}\) is: \[\begin{array}{*{8}{c@{\hspace{0pt}}}} \texttt{0} & \texttt{0} & \texttt{1} & \texttt{0} & \texttt{0} & \texttt{1} & \texttt{0} & \texttt{1} \\ \end{array}\] If we wanted to compute \(24+37\), we’d just add these. But instead we’re looking for \(24-37\), so we’ll take the complement of 37 to find \(-37\). Flip all the bits of 37: \[\begin{array}{*{8}{c@{\hspace{0pt}}}} \texttt{1} & \texttt{1} & \texttt{0} & \texttt{1} & \texttt{1} & \texttt{0} & \texttt{1} & \texttt{0} \\ \end{array}\] and add one: \[\begin{array}{*{9}{c@{\hspace{0pt}}}} \texttt{1} & \texttt{1} & \texttt{0} & \texttt{1} & \texttt{1} & \texttt{0} & \texttt{1} & \texttt{0} \\ + & \texttt{ } & \texttt{ } & \texttt{ } & \texttt{ } & \texttt{ } & \texttt{ } & \texttt{1} \\ \hline \texttt{1} & \texttt{1} & \texttt{0} & \texttt{1} & \texttt{1} & \texttt{0} & \texttt{1} & \texttt{1} \\ \end{array}\] and so now we’ve determined that in the two’s-complement scheme, \(-37\) is represented by \(\texttt{11011011}_2\).

We’re now ready to compute \(24 + (-37)\): \[\begin{array}{*{9}{c@{\hspace{0pt}}}{l}} & & & \texttt{1} & \texttt{1} & & & & \\ & \texttt{0} & \texttt{0} & \texttt{0} & \texttt{1} & \texttt{1} & \texttt{0} & \texttt{0} & \texttt{0} & \quad {\leftarrow this\space is\space 24_{10}}\\ + & \texttt{1} & \texttt{1} & \texttt{0} & \texttt{1} & \texttt{1} & \texttt{0} & \texttt{1} & \texttt{1} & \quad {\leftarrow this\space is\space -37_{10}}\\ \hline & \texttt{1} & \texttt{1} & \texttt{1} & \texttt{1} & \texttt{0} & \texttt{0} & \texttt{1} & \texttt{1} & \\ \end{array}\]

So we have our two’s-complement answer, 11110011. What value does that correspond to? Well, the left-most bit is a 1, so it’s a negative number. To find out what it’s the negative of, flip all the bits and add one: \[\begin{array}{*{8}{c@{\hspace{0pt}}}{l}} \texttt{0} & \texttt{0} & \texttt{0} & \texttt{0} & \texttt{1} & \texttt{1} & \texttt{0} & \texttt{0} & \quad {\leftarrow flip\space the\space bits\space to\space get}\\ + & \texttt{ } & \texttt{ } & \texttt{ } & \texttt{ } & \texttt{ } & \texttt{ } & \texttt{1} & \quad {\leftarrow add\space one}\\ \hline \texttt{0} & \texttt{0} & \texttt{0} & \texttt{0} & \texttt{1} & \texttt{1} & \texttt{0} & \texttt{1} \\ \end{array}\] This is positive 13, which means the number we inverted to get it — 11110011 — must represent \(-13\). And that is indeed the correct answer, for \(24-37=-13\).

One last word on two’s-complement: what is the range of numbers we can represent? It turns out to be -128 to 127. The highest value is 01111111, which is 127. You might think the lowest value would be represented as 11111111, but if you work it out, you’ll find that this is actually the number \(-1\). The lowest number is actually the bit pattern 10000000, which is \(-128\).

Overflow

One last sticky detail we need to cover has to do with overflow. When we add two numbers, there is the possibility that the result will contain one more digit than the original numbers did. You’ve probably seen this on a hand calculator when you press “=" and get an “E" (for “error") in the display. If there are only ten digits on your display, adding two ten-digit numbers will (sometimes) result in an eleven-digit number that your calculator can’t display, and it’s alerting you to that fact so you don’t misinterpret the result. Here, we might add two 8-bit quantities and end up with a 9-bit quantity that can’t fit in one byte. This situation is called overflow, and we need to detect when it occurs.

The rules for detecting overflow are different depending on the scheme. For unsigned numbers, the rule is simple: if a 1 is carried out from the MSB (far left-side), then we have overflow. So if I were to try to add \(155_{10}\) and \(108_{10}\): \[\begin{array}{*{9}{c@{\hspace{0pt}}}{l}} & \texttt{1} & \texttt{1} & \texttt{1} & \texttt{1} & & & & \\ & \texttt{1} & \texttt{0} & \texttt{0} & \texttt{1} & \texttt{1} & \texttt{0} & \texttt{1} & \texttt{1} & \quad {\leftarrow 155_{10}}\\ + & \texttt{0} & \texttt{1} & \texttt{1} & \texttt{0} & \texttt{1} & \texttt{1} & \texttt{0} & \texttt{0} & \quad {\leftarrow 108_{10}}\\ \hline \texttt{1} & \texttt{0} & \texttt{0} & \texttt{0} & \texttt{0} & \texttt{1} & \texttt{1} & \texttt{1} & \texttt{1} \\ \end{array}\] then I get a carry out left into the 9th digit. Since we can only hold eight digits in our result, we would get a nonsensical answer (\(15_{10}\)), which we can detect as bogus because the carry out indicated overflow.

Sign-magnitude works the same way, except that I have one fewer bit when I’m adding and storing results. (Instead of a byte’s worth of bits representing magnitude, the left-end bit has been reserved for a special purpose: indicating the number’s sign. Therefore, if I add the remaining 7-bit quantities and get a carry out left into the eighth digit, that would indicate overflow.)

Now with two’s-complement, things are (predictably) not that easy. But it turns out they’re almost as easy. There’s still a simple rule to detect overflow, it’s just a different rule. The rule is: if the carry in to the last (left-most) bit is different than the carry out from the last bit, then we have overflow.

Let’s try adding \(103_{10}\) and \(95_{10}\) in two’s-complement, two numbers which fit in our -128 to 127 range, but whose sum will not: \[\begin{array}{*{9}{c@{\hspace{0pt}}}{l}} {\text{carry-in}} \rightarrow & \texttt{1} & \texttt{1} & \texttt{1} & \texttt{1} & \texttt{1} & \texttt{1} & \texttt{1} & \\ & \texttt{0} & \texttt{1} & \texttt{1} & \texttt{0} & \texttt{0} & \texttt{1} & \texttt{1} & \texttt{1} & \quad {\leftarrow 103_{10}}\\ \quad + & \texttt{0} & \texttt{1} & \texttt{0} & \texttt{1} & \texttt{1} & \texttt{1} & \texttt{1} & \texttt{1} & \quad {\leftarrow 95_{10}}\\ \hline {\text{carry-out}} \rightarrow \texttt{0} & \texttt{1} & \texttt{1} & \texttt{0} & \texttt{0} & \texttt{0} & \texttt{1} & \texttt{1} & \texttt{0} \\ \end{array}\] The carry-in to the last bit was 1, but the carry-out was 0, so for two’s-complement this means we detected overflow. It’s a good thing, too, since 11000110 in two’s-complement represents \(-57_{10}\), which is certainly not 103 + 95.

Essentially, if the carry-in is not equal to the carry-out, that means we added two positive numbers and came up with a negative number, or that we added two negatives and got a positive. Clearly this is an erroneous result, and the simple comparison tells us that. Just be careful to realize that the rule for detecting overflow depends totally on the particular representation scheme we’re using. A carry-out of 1 always means overflow…in the unsigned scheme. For two’s-complement, we can easily get a carry-out of 1 with no error at all, provided the carry-in is also 1.

“It’s all relative"

Finally, if we come up for air out of all this mass of details, it’s worth emphasizing that there is no intrinsically “right" way to interpret a binary number. If I show you a bit pattern — say, 11000100 — and ask you what value it represents, you can’t tell me without knowing how to interpret it.

If I say, “oh, that’s an unsigned number," then you’d treat each bit as a digit in a simple base 2 numbering scheme. You’d add \(2^7 + 2^6 + 2^2\) to get 196, then respond, “ah, then that’s the number \(196_{10}\)." And you’d be right.

But if I say, “oh, that’s a sign-magnitude number," you’d first look at the leftmost bit, see that it’s a 1, and realize you have a negative number. Then you’d take the remaining seven bits and treat them as digits in a simple base 2 numbering scheme. You’d add \(2^6 + 2^2\) to get 68, and then respond, “ah, then that’s the number \(-68_{10}\)." And you’d be right.

But then again, if I say, “oh, that’s a two’s-complement number," you’d first look at the leftmost bit, see that it’s a 1, and realize you’re dealing with a negative number. What is it the negative of? You’d flip all the bits and add one to find out. This would give you \(\texttt{00111100}\), which you’d interpret as a base 2 number and get \(60_{10}\). You’d then respond, “ah, then that’s the number \(-60_{10}\)." And you’d be right.

So what does 11000100 represent then?? Is it 196, \(-68\), or \(-60\)? The answer is any of the three, depending on what representation scheme you’re using. None of the data in computers or information systems has intrinsic meaning: it all has to be interpreted according to the syntactic and semantic rules that we invent. In math and computer science, anything can be made to mean anything: after all, we invent the rules.