Number Representations

00:00 In the previous lesson, you learned about bitwise operations. In this lesson, you’ll learn all about the different ways binary is used to represent numbers and why that makes bitwise operations have weird results.

00:13 Binary, outside of the computing world, is a series of powers of 2, which on its own can only represent numbers 0 or greater. Computers use binary to represent numbers, but they store those values in a finite space in memory. A group of eight bits is called a byte.

00:30 A single unsigned byte can hold from 0 to 255 decimal or 0 to 1111 1111 in binary. To store numbers larger than 255, you need multiple bytes.

00:48 The C programming language has four different ways of storing integers: char, short, int, and long. Each of these is comprised of a different number of bytes. “And what,” you might say, “about negative numbers?” Such an intelligent question.

01:03 You have to store those differently. C has two variations on those four types I just mentioned: signed and unsigned. An unsigned char is a single byte ranging from 0 to 255.

01:16 A signed char is also a single byte, but in decimal ranges from -128 to 127. The same 256 spots are used, but they’re mapped to different numbers.

01:30 One of the complications of limited storage space is what to do when an operation causes a value to exceed the maximum for that storage space. This is referred to as an overflow.

01:41 Consider a one-byte binary number containing decimal 10. Adding 1 just flips the rightmost bit. Well, what about a one-byte binary number with all the bits set to 1?

01:55 What happens when you add to it? Overflow. The number resets to 0. There’s usually a signal to the programmer that such an overflow happened, but not always.

02:08 Let’s talk about negative numbers. A lot! The next seven slides are all about negative numbers. What might seem simple on the surface, decidedly is not. Signed-magnitude is one strategy for representing a negative number.

02:22 It uses the leftmost, or most significant, bit to indicate whether a number is positive or negative. If the leftmost bit is 1, the number is negative. Positive numbers for a single-byte signed-magnitude integer range from 0 to 0111 1111 in binary.

02:44 The leftmost bit has to be 0 for the number to be positive. That gives you 0 to 127 in decimal. Negative numbers are the same but with the leftmost bit set to 1.

02:59 Well, that’s a little odd. 1 and all 0s is 0, but with the sign bit set. This is called ambiguous zero. There are two different ways of representing zero in signed-magnitude representation. Two zeros isn’t the only problem. Addition is also problematic.

03:20 You can’t just add the bits together. Consider the following example. 0 plus 0 is 0. 1 plus 1 is 10, carrying the 1. Passing through the carry gives you 1.

03:38 Then 1 plus 1, carrying again, 1 plus 1, carrying again, and finally, 1. The end result of adding 42 and -42 this way is -84. Let me just get a calculator quickly. Yeah, nope. That’s not right.

04:00 You can’t just add two signed-magnitude numbers and get the right answer.

04:07 An early solution to the problems with signed-magnitude representation was ones’ complement. The leftmost bit still indicates the sign, but the negative value is stored as its complement—i.e. all its bits are flipped.

04:22 This weird little trick actually solves the addition problem. Positive values are the same as signed-magnitude, only the negative values are different. Ones’ complement, like signed-magnitude, still has an ambiguous zero.

04:36 You can’t have everything.

04:39 Let’s look at some examples to make this a little more clear. The single byte, ones’ complement value for zero, is eight 0s. The complement of that is an ambiguous zero.

04:51 It flips the sign bit and complements, or inverts, all the other bits. These are the two representations for zero in ones’ complement. Here’s positive one. Negative one is the invert of positive one. Here’s two.

05:12 Negative two is the invert of positive two.

05:17 And the same goes for all the way up to plus or minus 127.

05:25 What’s better than one compliment? Well, two compliments, of course! This is the most common mechanism for storing negative numbers in modern machines. It removes the ambiguous zero problem and makes a couple of the corner cases in addition easier. The leftmost bit is still used for the sign.

05:43 Negative numbers are still a complement, but this time, they’re the complement plus 1. This is called an asymmetrical representation. There are more negative values than positive ones. For an eight-bit byte the range is -128 to 127.

06:04 You can think of the most significant bit indicating both the sign and a magnitude. You can see it here in the chart. Bit 7 is a negative magnitude.

06:16 Let’s try some two’s complement numbers. Zero is not ambiguous. There’s only one representation. No negative zero in this case. Positive 1, let’s complement it, and then add 1.

06:32 That gives you the all 1s to represent the negative equivalent. Positive 2, complement it and add 1, and that’s plus or minus 2. At the upper end, the biggest positive number is 127,

06:49 which, when you look at the complement, shows you’ve still got one more bit that you can turn off. So -128 is 1 and all 0s.

07:01 Consider these three different representations and what it would mean to perform bitwise operations on them. Most of the time you’re doing bitwise operations, you really don’t care about the negative representation. You’re tracking bits, turning them on and off. Being explicit about this and using an unsigned integer is your best bet.

07:20 Performing a bitwise operation on a signed value may result in the signed bit changing, and depending on the kind of number representation, the same operation will impact the value differently.

07:33 In the following table, I’m going to show you the three types of a negative number representation. For each case, I’ll show a value, the value NOT-ed, and the resulting decimal numbers in the three representations. 0110 NOT-ed is 1111 1001.

07:55 The decimal value in signed-magnitude is 6, and the NOT-ed value is -121. The same two values in ones’ complement give 6 and -6. And 6 and -7 in two’s complement. The same two binary values give four different variations on what they mean. Let’s try it again, this time with 1001 1101.

08:28 Here’s the NOT-ed value, -29 signed-magnitude. 98 for the NOT-ed value. -98 for ones’ complement, -99 for two’s complement, and 98 pops up again for the NOT-ed value.

08:47 How about one of the edge cases? Here’s all 0s. Here’s the invert. 0 in signed-magnitude, and then NOT-ed value is -127. Zero, ambiguous zero, zero, and negative one.

09:06 And because I’m having so much fun, one more. Literally, one more. Here’s the NOT-ed value. That’s a one, -127, one, minus one, one, and finally minus two.

09:23 Have I convinced you that you should be using unsigned integers yet?

09:29 Everything so far has mapped to powers of two somewhat directly. That doesn’t have to be the case. Floating-point and fixed-point representations are different altogether.

09:39 You don’t typically do bitwise math on these types of numbers, so if the details of how these are stored doesn’t interest you, I’ll see you at the next lesson. Floating-point numbers are based on the IEEE standard 754.

09:54 These are a lossy representation of non-integer numbers. They’re lossy because they aren’t precise. As you saw in the second lesson, you can store sixteen digits of pi, but that’s it. Good enough for most cases, but it’s still not technically pi.

10:11 A floating-point number is composed of three parts: a sign bit, an exponent, and a mantissa. This is similar to scientific notation. The name floating point comes from the fact that the number of digits to the right of the decimal isn’t fixed. The decimal point floats around.

10:32 The standard defines several variations. The two most common precisions are single float, which is stored as thirty-two bits or four bytes, with a sign bit, eight bits for the exponent, and twenty-three bits for the mantissa.

10:48 And a double float, which is stored as sixty-four bits, or eight bytes, still with a single sign bit, eleven bits for the exponent, and a whopping fifty-two for the mantissa.

11:01 Let’s look a little deeper at the single precision floating-point number. The sign bit is zero for positive and one for negative. That should seem a little familiar. The exponent is eight bits.

11:14 The number is treated as an unsigned value. To get small fractional numbers, you need a negative power. That’s done by biasing the exponent. That means the raw number actually represents 127 more than the actual number. Subtract the bias, and you get the right value.

11:32 The mantissa is twenty-three bits. This part represents a fraction where each bit is a negative power of two. For all exponent values except zero, the fractional portion assumes a twenty-fourth bit to the left that has a value of one.

11:50 That gives you twenty-four bits of precision packed into twenty-three bits of space. And it means you have to add one to the raw mantissa to get the number it actually represents. Let’s look at an example to clear up this messiness.

12:06 All that stuff on the previous slide breaks down into this formula. The value the binary digits represent is minus one to the power of the sign bit times two to the power of the biased exponent times the mantissa plus one.

12:23 Consider this long mess. Zero for the sign, 128 for the raw exponent, and a whole bunch of digits for the raw mantissa. The mantissa breaks down into the following powers of two.

12:38 With the position of each on bit corresponding to a fractional power of two, turning those into actual fractions, and you get about 0.57. Plugging all that into the original formula,

12:55 and look at that! Pi. If you remember the pi from lesson two, this one has less precision. The pi in lesson two was a double float. This one being a single means there are fewer significant digits to the right of the decimal point.

13:11 Floating-point numbers are only approximations. Some of them cannot be precisely described. You can see this easily in practice with the handy REPL. I might have to dig out my calculator again, but I’m pretty sure that’s not right.

13:26 These sorts of errors are very bad for money. Fractions of a cent can add up over time. Don’t believe me? Go watch Superman III. Richard Pryor wouldn’t lie to you, would he?

13:38 The answer to this problem is fixed-point math. A simple version of this is all numbers are made up of two parts: the part to the left of the decimal and the part to the right.

13:47 As long as you don’t overflow either of those two parts, you’re good. Although fixed point doesn’t have the approximation problem that floating point does, it also doesn’t have a dedicated part of the CPU that specializes in doing math with them.

14:01 This tends to make fixed point more expensive computationally. The short version of that is: Fixed point is good for money calcs, but slower. Python has a fixed-point library called Decimal.

14:14 It allows you to set an arbitrary precision to the right of the decimal point.

14:20 Want even more precision for your numbers? Python has the fractions module that represents the numerator and denominator of a fraction separately. It supports doing operations on these objects, finding the lowest common denominator of the result.

14:35 You can get the floating point equivalent if you like, delaying the creation of the imprecise thing to the last step in your calculation.

14:44 Want some actual Python in your Python course? You’ve been patient. Next up, I’ll talk about how Python stores integers to prepare you for the effects of bitwise operations in the lesson after.