C++ for beginners, part 4 (a binary digression)

I know I said there’d only be one more post before problem 2, but I realised this is a good opportunity to talk about binary, which is both useful, and really interesting (no, seriously). Right now, we have 10 options. Either I gloss over the details and let you get confused further down the line, or we communicate like adults and take some time to discuss representing numbers in binary. So, you know the drill: go make a cup of tea, I’ll wait.

Context

Here’s the more elegant approach to problem 1 (section 2 of this post), in R, this time with comments to refresh your memory:

Pic1

Now here’s an interesting thing about representing numbers in C++. Say we declare two positive integers, and divide one by the other. The result is not always a whole number (e.g. 999/5 = 199.8). But C++ will still give an integer output. How? By dropping the fractional part. Why? Because of how numbers are represented in binary.

Computer logic

Everyone knows that computers work on 1s and 0s. But aren’t quite sure how. There may or may not be teeny-tiny pixies involved. Also, it’s green?

Oh, and there’s some electronics involved. These are in the form of teeny-tiny (maybe even pixie-sized) switches, called logic gates. They take an input representing 0 (low input, no voltage), or 1 (higher input, higher voltage), and give the appropriate output. There is a short and excellent explanation here, and there’s a simple guide to truth tables (what different combinations of 1/0 inputs  produce for different operations), here, but I’ll give a very brief example anyway.

You have logical operators such as AND, OR, and NOT, and a few basic variations like NAND (negated-AND. i.e. ‘as long as it’s not both’). For example, take AND. It outputs a 1, if and only if, both inputs are 1. This logic gate is physically constructed in a way that given a high enough input voltage, the output voltage represents the correct value (1) for the AND operator. And by combining different logic gates, you can have more complex operations! Cool, huh?

From binary to numbers

So, why we use binary numbers makes sense. But how do these 1s and 0s represent actual numbers? Let’s compare a decimal counter with a binary one:

On the decimal counter, once you hit the maximum bit (9), it ticks over to 0, and the one to the left ticks up by 1. On a binary system, the maximum bit is 1, but the process is exactly the same. I only ended up using 5 bits, but I drew 8,  because 8 bits is what is known as a ‘byte’, and computer CPUs are based on multiples of 8-bits. Thus, in terms my readership (read: geeks, and I say that with utmost affection) will understand:

  • Nintendo Entertainment System (NES) was 8-bit
  • Sega Mega Drive / Genesis, and Super Nintendo were 16-bit
  • Playstation was 32-bit
  • N64 and PS2 were 64-bit

Anyway, you can kind of see a pattern in the numbers. Look at when the leading (leftmost) non-zero bit 1, and there are no 1s in the trailing (right of this bit) digits:

  • For the decimal one, the only times this happens are 1, and 10.
  • For binary, it happens at 1, 2, 4, 8, and 16.
  • Aha! These are all powers of 10 or 2, respectively. Cool. But what does squaring or multiplying a number by itself have to do with anything?
  • [Quick note: it makes sense that 10¹ and 10² are 10 and 100. But why is 10º equal to 1? Well, keep multiplying 10 by itself: 10, 100, 1000, 10000 etc. Going back the other way, you divide by 10, so: 10000, 1000, 100, 10, 1! And by that logic, 10¯¹ or 10¯² are 0.1, and 0.01 etc.]

Anyway, let’s take a look at why exactly we’re getting all those powers of 2. We’ll take four bits, and look at every combination possible. At the top of the image is the leading digit (it can either be 1 or 0. duh). Each level below is the trailing digit that could possibly follow it. We can see where this is going:

  • Two options, each of which can be followed by two options, each of which etc. So after the initial ‘1’, we have 2 times 2 times 2 etc… and that’s why we get powers.
  • 0 and 1 give you 0 and 1.
  • 1? can have a 0 or 1 in the ‘?’ position. So 2 possibilities.
  • 1?? can be followed by 00, 01, 10, 11, so 4 possibilities.
  • etc.

Even better is that you can think of each ‘1’ as an indicator of whether or not a binary number contains a certain power:

Pic2

Neato. It is super-simple once you know the reasoning behind it. You can also translate in the other direction:

From numbers to binary

This works because of an interesting property of the integers: every positive integer can be expressed as the sum of distinct powers of two. For example:

  • 17 = 16 + 1
  • 39 = 32 + 4 + 2 + 1
  • 372 = 256 + 64 + 32 + 16 + 4
  • But why does that work? Can we take it on faith that it always works, or can we prove it? Rhetorical. Of course we can prove it. Let’s take a top-down approach:
  1. Since getting the next power of 2 means multiplying by 2, then the only odd power of 2 is 1.
  2. This means that if we can generate an even number by adding distinct, even powers of 2, we can always generate the odd number above it by adding 1, the only odd power. So, now we can focus on trying to prove that all even numbers are the sum of distinct, even powers of 2.
  3. For any integer, it obviously is a power of 2, or lies between powers of 2:
  4. Pic3
  5. This means you can always find a nearest power of 2 below the number. So, that is the first term in your sum. For example, we’ll do 38. Nearest power below is 32. This leaves us with 6 left to sum up.
  6. Again, there exists a closest power below 6, which is 4. Leaving us with 2, which is itself a power. So 38 = 32 + 4 + 2.
  7. We kinda proved that by brute force, it doesn’t really prove it for every number, but you’ve gotten the flavour of it.

How about a bottom-up approach?

  1. Each power is twice that of the one before it. Which means that to get to the midpoint between two powers, you just add the power below both, to the smaller of the two powers. The midpoint between 16 & 32 is 24. Which is 16 + 8. Simples.
  2. So, obviously 1 and 2 are powers, and trivial cases. 3 is 2 + 1. 4 is a power. 5 is 4 + 1. These are all trivial. 6 though, is where we find out there’s a trick to it. 6 is halfway between 4 and 8. Now we realize:
  3. Since we can get to the midpoint of any two powers by adding a lower power, there is always a way to half the remaining part of the sum, so we can get progressively closer to our total without using any power more than once. Then, to top that off, we just add 1 if we want an odd number. I realize that sounds like a mouthful, so here it is visually, finding the powers that make up 119:

So, in 8-bit binary, 119 would be: (0)1110111. This also solves an important, age-old question we’ve asked ourselves since we first played Final Fantasy or other such RPGs. Why do most of my stats max out at 255?

  • Because of the memory constraints of an 8 bit CPU. 11111111 = 128+64+32+16+8+4+2+1 =255! Tada!
  • This is going to make all future discussions of the types of numbers in C++ a lot easier to make sense of. I’ll put it all in context and get back to what I was saying about integer division, in the next post.

Advertisements
This entry was posted in C++, Problem 1 and tagged , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s