Itsy Bitty Teeny Weeny

This lesson is all about binary numbers - how computers count, and (as usual) it's really important stuff. Most of it doesn't directly have anything to do with Java, although we might get on to how to manipulate binary numbers in Java later. The most important thing about binary numbers is that they're really not that different from normal (decimal) numbers. The usual rules apply, just in a slightly different way as you'll see.

In decimal we can write 0, 1, 2, 3, 4, 5, 6, 7, 8 or 9 with one digit. To do bigger numbers (like ten, ooh, soo big) we need two digits. In binary we can only write 0 or 1 with one digit. To count two we have to write 10. Here's your first test - please say out loud the following binary number:

10

I bet you all said "ten", didn't you! In decimal this number is ten, but in binary it is two. Let's try that again, but this time you should say "one zero".

10

Excellent, now everyone is looking at you and wondering why you are talking to your computer. The reason for all this isn't just me being picky - by saying "one zero" (even just in your head) it helps you to remember that the number you are looking at is not a decimal number but a binary one (no pun intended). Let's stop here and learn an important word: bit which is short for binary digit. A bit is either a single 0 or a single 1. The number above has two bits (ie two digits).

Now what is all this binary stuff about exactly? Well it's just a simpler way of counting which computers find easier. In fact it is the simplest way to count except for tallying. The value 0 or 1 for each bit in a computer corresponds to a transistor being off or on. To represent all the digits 0, 1, 2, ..., 9 would require ten different states for the transistor. Now you don't need a degree in Electronic Engineering to see that just off or on is much simpler than ten different states. It just takes a bit of getting used to for us humans.

So how do we count in binary? In decimal we count from 0 up to 9, then we carry over to two digits (10) where the first digit is more significant than the second. By more significant I mean that the first digit is the "tens" and the second is the "units". If we have three digits then the leftmost is the "hundreds", the second is the "tens" and so on. Notice that 100 is 10 squared, and if we go to four digits then 1000 is 10 cubed.

The same happens in binary, except we can only count from 0 up to 1 before we have to carry over to 10 (two). Next comes 11 (three) and then we have to carry over again to 100 (four). In a three digit binary number the leftmost digit is the "fours", the next is the "twos" and the last is the "ones". With four digits, the leftmost is the "eights", then "fours" and so on. Notice that 4 is 2 squared, and 8 is 2 cubed.

Enough waffling, here's a table of the binary numbers from 0 to 15:

Decimal	8s (=23)	4s (=22)	2s (=21)	1s (=20)		Decimal	8s (=23)	4s (=22)	2s (=21)	1s (=20)
0	0	0	0	0		8	1	0	0	0
1	0	0	0	1		9	1	0	0	1
2	0	0	1	0		10	1	0	1	0
3	0	0	1	1		11	1	0	1	1
4	0	1	0	0		12	1	1	0	0
5	0	1	0	1		13	1	1	0	1
6	0	1	1	0		14	1	1	1	0
7	0	1	1	1		15	1	1	1	1

Have a good look at this table so you can see how the numbers carry. Notice that powers of two (2, 4, 8, 16) are a one and then all zeros, the same as the powers of ten (10, 100, 1000) are a one and then all zeros.

How do you convert between binary and decimal numbers? One way is to use a table like the one above, but that can get very hard work for more than four digits of binary! The best thing is to take all the digits which are 1 and add together the corresponding powers of two. For example:

8s (=23)	4s (=22)	2s (=21)	1s (=20)
1	1	0	1
8 +	4 +		1 =	13

OK, now you can cheat and check in the table above - you can see that 1101 is in fact 13. Wasn't hard, was it? Let's now convert eleven to binary. To do this, first think of the biggest power of two which is less than eleven (it's 8). So we write a 1 in the 8s column:

8s (=23)	4s (=22)	2s (=21)	1s (=20)
1
8 +

Taking 8 from 11 leaves 3. Now look at the next-smallest power of two. As 3 is less than 4, we write a 0 in the 4s column (we don't need any 4s to make 3).

8s (=23)	4s (=22)	2s (=21)	1s (=20)
1	0
8 +

But 2 is less than 3, so write a 1 in the 2s column.

8s (=23)	4s (=22)	2s (=21)	1s (=20)
1	0	1
8 +		2 +

We have 8 + 2 so to make eleven we just need to add one - so put 1 in the 1s column. That's a lot of 1s in 1 sentence!

8s (=23)	4s (=22)	2s (=21)	1s (=20)
1	0	1	1
8 +		2 +	1 =	11

Go back and check, yes 1011 is in fact eleven. You can try some of these of your own, for numbers with more than four bits (remember bits are binary digits). Just write in 16, 32, 64 etc. along the top row. Try converting 43 to binary and back to decimal. Or tell me what number 1011 0100 is (you can write your answers in the comments box at the bottom if you like!)

Now, onwards to adding. We add binary numbers the same as we add decimal numbers. The only difference is that there are a lot more carrys! So 1 + 0 = 1, but 1 + 1 = 0 (carry 1). Also 1 + 1 + 1 = 1 (carry 1). That's about it. I'll do a simple example, 3 + 2 = 5, for you:

8s (=23)	4s (=22)	2s (=21)	1s (=20)
0	0	1	1	3
0	0	1	0	2

We can do 1 + 0 easily, that's 1 with no carry.

8s (=23)	4s (=22)	2s (=21)	1s (=20)
0	0	1	1	3
0	0	1	0	2
			1

And 1 + 1 is 0, carry 1:

8s (=23)	4s (=22)	2s (=21)	1s (=20)
0	0	1	1	3
0	0	1	0	2
		0	1
	1

0 + 0 is, logically enough, 0. But don't forget the carry 1! So the next bit is in fact 1.

8s (=23)	4s (=22)	2s (=21)	1s (=20)
0	0	1	1	3
0	0	1	0	2
	1	0	1	5
	1

That's us done! We have the answer 101, which is 5. Brilliant! I'll do one more, but without all the explanations:

16s (=24)	8s (=23)	4s (=22)	2s (=21)	1s (=20)
	0	1	1	1	7
	1	0	1	1	11
1	0	0	1	0	18
	1	1	1

Sit down and try to follow that one through yourself (it's not as easy as it looks). Then forget all about it, because in practice you won't have to do this sort of thing very often. I'm not going to attempt subtraction either, because it's not very nice.

Our final topic for this lesson is called two's complement. Look back to the table showing the binary values of 0 to 15. These are all the possible values we can represent with 4 bits. It's no coincidence that 15 is 2⁴ - 1. We can apply this to any number of bits. For instance, using 32 bits we can represent values from 0 to 4294967295. That's a pretty big number, but isn't something missing? Well yes, there are no negative numbers.

In order to represent both positive AND negative numbers, we use a special system called two's complement. Don't ask me why they called it that. It can be used for binary numbers of any number of bits. In Java all whole number types (byte, short, int and long) are stored using this system - in other words all these types can hold either positive or negative numbers. To make it easy to understand, we will only use 4 bits for our two's complement numbers, but be aware that in real life they can be 8, 16, 32, 64 or any other number of bits long.

So, for the values 0 to 7, the two's complement (or signed) values are the same as the unsigned values. By unsigned I mean the values at the beginning of this lesson. Let's take a look at them.

Decimal	8s (=23)	4s (=22)	2s (=21)	1s (=20)		Decimal	8s (=23)	4s (=22)	2s (=21)	1s (=20)
0	0	0	0	0			1	0	0	0
1	0	0	0	1			1	0	0	1
2	0	0	1	0			1	0	1	0
3	0	0	1	1			1	0	1	1
4	0	1	0	0			1	1	0	0
5	0	1	0	1			1	1	0	1
6	0	1	1	0			1	1	1	0
7	0	1	1	1			1	1	1	1

Notice that all the values 0 to 7 have a zero as their first (leftmost) bit. This is also called the most significant bit, since its value can make the difference between 2 and 10 (for example). The rightmost bit is surprisingly called the least significant bit, since it only makes the difference between 2 and 3. Think of your bank balance, the digits to the left (ie number of hundreds) are more significant than the digits to the right (number of pence).

Now we have to fill in the rest of the table. Let's start with -1, which is always represented by all 1s:

Decimal	8s (=23)	4s (=22)	2s (=21)	1s (=20)		Decimal	8s (=23)	4s (=22)	2s (=21)	1s (=20)
0	0	0	0	0			1	0	0	0
1	0	0	0	1			1	0	0	1
2	0	0	1	0			1	0	1	0
3	0	0	1	1			1	0	1	1
4	0	1	0	0			1	1	0	0
5	0	1	0	1			1	1	0	1
6	0	1	1	0			1	1	1	0
7	0	1	1	1		-1	1	1	1	1

However many bits a two's complement number may have, -1 is always a string of all 1s. Zero is always a string of all 0s (although that may be obvious). Also the most significant bit will always indicate the sign of the number (0 for positive or zero, 1 for negative).

The original (unsigned) values on the right were increasing down the column, so maybe we should do the same. To increase up to -1, the others must all be negative too:

Decimal	8s (=23)	4s (=22)	2s (=21)	1s (=20)		Decimal	8s (=23)	4s (=22)	2s (=21)	1s (=20)
0	0	0	0	0		-8	1	0	0	0
1	0	0	0	1		-7	1	0	0	1
2	0	0	1	0		-6	1	0	1	0
3	0	0	1	1		-5	1	0	1	1
4	0	1	0	0		-4	1	1	0	0
5	0	1	0	1		-3	1	1	0	1
6	0	1	1	0		-2	1	1	1	0
7	0	1	1	1		-1	1	1	1	1

That's interesting, now we have a set of negative and positive values which we can represent. Notice that the smallest negative value is -8, but the largest positive value is only +7. The reason for this is that zero occupies one of the positive spaces. Obviously now we cannot go all the way up to +15 with four bits, as half the binary values are now used for negative numbers.

So we have a system for signed values. The forward-thinking amongst you might be wondering how easy it is to add these values together. What if we add a negative number to a positive one? Or two negative numbers together? Wait, because this is the coolest thing about two's complement numbers: you don't have to do anything special. You just add the two values together as we did before when they were unsigned values. If there is an extra carry bit (beyond our allowed 4 bits) we just have to throw it away. To demonstrate this, I will add 6 to -3:

16s (=24)	8s (=23)	4s (=22)	2s (=21)	1s (=20)
	0	1	1	0	6
	1	1	0	1	-3
1	0	0	1	1	3
	1

Wow! It's the right answer (make sure you ignore the 1 which is crossed out and just take the answer 0011, or 3). There's another trick which is handy to know, which is how to go from 5 to -5 (for example). This is probably the easiest way to work out the binary value for a negative number in two's complement form.

8s (=23)	4s (=22)	2s (=21)	1s (=20)
0	1	0	1	5

To change a positive number to its negative equivalent (or vice versa) there are just two steps. First, change all the 0s to 1s, and all the 1s to 0s. This is known as "taking the complement" and probably where the silly name comes from.

8s (=23)	4s (=22)	2s (=21)	1s (=20)
0	1	0	1	5
1	0	1	0

The second step is to add one. In this case it's pretty easy because there's no carrying.

8s (=23)	4s (=22)	2s (=21)	1s (=20)
0	1	0	1	5
1	0	1	0
1	0	1	1	-5

Hurrah, right again. Well you might have noticed by now that two's complement numbers with 4 bits are, well, limited in their usefulness and incredibly dull. Although working with 32 or 64 bits isn't at all any more interesting, we can represent a large range of numbers, and all the same principles hold. There's one more thing I have to teach you, which is how to convert from a small two's complement number to a larger one.

Suppose you like to use 4 bits for your numbers (in two's complement form), but you have a friend who likes to use 5 bits. You would very much like to share some numbers (both positive and negative) with him, but you just don't know how. Let's look at the 5-bit system your friend uses:

Decimal	16s (=24)	8s (=23)	4s (=22)	2s (=21)	1s (=20)		Decimal	16s (=24)	8s (=23)	4s (=22)	2s (=21)	1s (=20)
0	0	0	0	0	0		-16	1	0	0	0	0
1	0	0	0	0	1		-15	1	0	0	0	1
2	0	0	0	1	0		-14	1	0	0	1	0
3	0	0	0	1	1		-13	1	0	0	1	1
4	0	0	1	0	0		-12	1	0	1	0	0
5	0	0	1	0	1		-11	1	0	1	0	1
6	0	0	1	1	0		-10	1	0	1	1	0
7	0	0	1	1	1		-9	1	0	1	1	1
8	0	1	0	0	0		-8	1	1	0	0	0
9	0	1	0	0	1		-7	1	1	0	0	1
10	0	1	0	1	0		-6	1	1	0	1	0
11	0	1	0	1	1		-5	1	1	0	1	1
12	0	1	1	0	0		-4	1	1	1	0	0
13	0	1	1	0	1		-3	1	1	1	0	1
14	0	1	1	1	0		-2	1	1	1	1	0
15	0	1	1	1	1		-1	1	1	1	1	1

The top left and bottom right sections contain those numbers that we can also represent with our 4-bit system. But notice that the binary values our friend uses for the values 0 to 7 are the same as the ones we use, except with an extra 0 on the left. Now look at the values -1 to -8. These are the same as the ones we use, but with an extra 1 on the left. So for any number in our 4-bit system, we can just take the leftmost bit and add the same value to the left (so 0xxx becomes 00xxx, and 1xxx becomes 11xxx). This will then represent the same value in our friend's system.

In fact this technique works in general for converting to any two's complement system with more bits than our own. For instance, in an 8-bit system, our value 0xxx becomes 00000xxx and 1xxx becomes 11111xxx. This is known as sign extension, because the sign bit (the leftmost, or most significant bit) of the original number is extended to fill all the spaces on the left. Remember that, for any two's complement number, the most significant bit is 0 for positive numbers (and zero), and 1 for negative numbers.

We'll look at manipulating two's complement and other binary values in our next lesson. Please fill out the questionnaire before going on.

But what do you think?	This lesson was...		What don't you understand? Other comments?
	Excellent OK Poor
	Your email (optional)

Next lesson: The Second Bit