The Second Bit

Hi. Welcome back. You must be loving this binary stuff so much, you just can't get enough of it. That's good, because we're doing some more, but you definitely need to read the previous lesson (Itsy Bitty Teeny Weeny) first, if you haven't already. Don't worry if you're not 100% on how two's complement works yet, because I also have a cool diagram which explains it pretty well:

Unlike the last lesson, this one shows you how to do all this bitty stuff in Java too. Let's get going.

At the end of the last lesson we talked about sign extending a two's complement number. Do you remember? This is when we want to store the same number, but using more bits, so that our friends can understand it too. We take the leftmost (or most significant) bit from the old number and extend it to fill up all the space available. So 0xxx becomes 00000xxx, and 1xxx becomes 11111xxx.

There is another way to do this called zero extension. This means we just fill the extra space with 0s. So 0xxx becomes 00000xxx, but 1xxx becomes 00001xxx. This means that, for negative numbers, the value is no longer the same in the new longer binary representation. So we normally only do this when we are talking about unsigned numbers (rather than two's complement numbers - see previous lesson).

Before we do our first piece of Java, some revision: all the integer types in Java are stored in two's complement form. A byte is 8 bits, a short is 16 bits, an int is 32 bits and finally, a long is 64 bits.

For this program I've provided you with two methods (both called printBinary) to print out a byte or an int in binary form. The Java compiler will figure out the correct one to use for you, depending on whether the argument you give (the part between the brackets) is a byte or an int.

class Hello { public static void main(String[] args) { } private static void printBinary(byte b) { for (int sh = 7; sh >= 0; sh--) { System.out.print((b >> sh) & 1); } System.out.println(); } private static void printBinary(int i) { for (int sh = 31; sh >= 0; sh--) { System.out.print((i >> sh) & 1); } System.out.println(); } }

Let's test this by printing the value of some numbers we are familiar with. I've not bothered to write out the two printBinary methods again, but they are just the same as above.

class Hello { public static void main(String[] args) { byte x = 0; byte y = -1; printBinary(x); printBinary(y); } ...

Now try it:

[nurmes]btg: javac Hello.java [nurmes]btg: java Hello 00000000 11111111 [nurmes]btg:

Ooh, look at all those digits! Let's make a small change to the program to show the same values as an int (32 bits).

class Hello { public static void main(String[] args) { int x = 0; int y = -1; printBinary(x); printBinary(y); } ...

You might now appreciate why binary is not the most compact form for representing numbers (for humans, anyway!)

[nurmes]btg: javac Hello.java [nurmes]btg: java Hello 00000000000000000000000000000000 11111111111111111111111111111111 [nurmes]btg:

Luckily for you, there is a neater way to write all those numbers. We've learned about binary, which only has 0 and 1, and hopefully you already know about decimal, which has 0 up to 9. There is another system often used by programmers, called hexadecimal (or hex for short).

Hexadecimal can represent 0 up to 15 with a single digit. As we don't have numbers for ten onwards, in hex we use the letters A, B, C, D, E and F. The A stands for ten, B for eleven and so on (which means F stands for fifteen).

So in hex, 10 isn't ten! But it isn't two (like in binary) either. Like in the last lesson, you should say it "one zero". Binary has 1s, 2s, 4s, 8s and so on, decimal has 1s, tens, hundreds, thousands. Hexadecimal has 1s, sixteens, 256s and so on (256 is 16²). So what 10 actually means in hex is "one sixteen and no units", in other words sixteen.

Before you have a nervous breakdown every time you see 10, let me tell you how hex numbers are written in Java. We start them with 0x (that's a zero and an X), so for example sixteen is written 0x10. I'll write hex numbers in this lesson the same way.

I'll put a little table in here, like in the last lesson, so you can check up on what each digit means in hex as you go along.

Decimal	Hex	Binary		Decimal	Hex	Binary
0	0x0	0000		8	0x8	1000
1	0x1	0001		9	0x9	1001
2	0x2	0010		10	0xA	1010
3	0x3	0011		11	0xB	1011
4	0x4	0100		12	0xC	1100
5	0x5	0101		13	0xD	1101
6	0x6	0110		14	0xE	1110
7	0x7	0111		15	0xF	1111

You might now have noticed another really neat thing about hex numbers. One digit of hex can represent the values zero to fifteen. Four digits of binary also represent the values zero to fifteen. You guessed it - you can convert any four digits of binary to one digit of hex, using the table above. This means that a byte takes exactly two digits of hex, and an int (32 bits) takes eight digits of hex. Let's try a big scary example:

Take the binary number below and convert it to hexadecimal:

10000011111110000101110111100101

Try not to scream! Let's break this up into 4 bit chunks:

1000 0011 1111 1000 0101 1101 1110 0101

Now treat each chunk individually, and turn it into a single digit of hexadecimal. Start on the left - we have 1000 which is 0x8 in hex. Then 0011 becomes 0x3 and so on.

8 3 F 8 5 D E 5

So we've converted that HUGE number in binary to hexadecimal with relative ease. If you really wanted to turn this into decimal it would be easier now too.

Let's shift on with the lesson then. Literally - we are going to look at shifts in Java. The easiest type is called a left shift. It's really very easy. You shift along the bits of a binary number by a specified amount. Throw away the spare bits on the left, and add zeros on the right. Let me show you:

class Hello { public static void main(String[] args) { int x = 20; int y = -20; printBinary(x); printBinary(y); } ...

First let's just run it to see what 20 and -20 look like in binary (if you like, you can try to figure it out...)

[nurmes]btg: javac Hello.java [nurmes]btg: java Hello 00000000000000000000000000010100 11111111111111111111111111101100 [nurmes]btg:

Now we're going to shift each value to the left and to the right by two bits and print them out in binary.

class Hello { public static void main(String[] args) { int x = 20; int y = -20; printBinary(x); printBinary(x << 2); printBinary(x >> 2); System.out.println(); printBinary(y); printBinary(y << 2); printBinary(y >> 2); } ...

 

[nurmes]btg: javac Hello.java [nurmes]btg: java Hello 00000000000000000000000000010100 00000000000000000000000001010000 00000000000000000000000000000101 11111111111111111111111111101100 11111111111111111111111110110000 11111111111111111111111111111011 [nurmes]btg:

Rock and roll! Can you see what's happened? Look at the first three to start with. You can see that the "101" in the binary value of 20 has moved. In the second line down it has moved to the left by two bits. In the third line it has moved to the right by two bits (compared to the original value).

This means that, whether we shift to the left or to the right, two bits are thrown away and two new bits are added. The new bits are zeros.

Now look at the next three lines. Can you see the 011 pattern has also been moved to the left by two bits, and then to the right by two bits? When shifting to the left, the new bits added (on the right) are zeros. But when shifting to the right, two new ones are added. This is because the number is negative. Remember that a negative number always starts with a one in two's complement.

To explain why a negative number gets ones added on the left, and why anyone would want to shift their bits anyway, I'm going to print out the decimal values to the left of the binary values.

class Hello { public static void main(String[] args) { System.out.println("Hello, world!"); int x = 20; int y = -20; System.out.print(x + " "); printBinary(x); System.out.print((x << 2) + " "); printBinary(x << 2); System.out.print((x >> 2) + " "); printBinary(x >> 2); System.out.println(); System.out.print(y + " "); printBinary(y); System.out.print((y << 2) + " "); printBinary(y << 2); System.out.print((y >> 2) + " "); printBinary(y >> 2); } ...

Let's see what happens:

[nurmes]btg: javac Hello.java [nurmes]btg: java Hello 20 00000000000000000000000000010100 80 00000000000000000000000001010000 5 00000000000000000000000000000101 -20 11111111111111111111111111101100 -80 11111111111111111111111110110000 -5 11111111111111111111111111111011 [nurmes]btg:

Hmm, interesting... shifting two places to the left multiplies the value by 4, and shifting to the right divides by 4. It seems to work for negative numbers too. Maybe that's why it fills up with ones on the left.

This is no coincidence - we can in fact divide or multiply by any power of two (2, 4, 8, 16, etc.) by shifting by the appropriate number of bits to the left or right. In this case we multiply by 4, which is 2², so we shift by two bits.

Once again, we can do the same for decimal numbers: take 200, add two extra zeros on the right (ie shift left by two digits) and you get 20000, which is 100 times bigger. If you remove the rightmost two digits (ie shift right by two digits) then you get 2, which is 100 times smaller. Do you see?

With a negative value (a value that has a 1 as the leftmost digit), when we shift to the right, extra ones are added on the left. But with a positive value (a value that has a 0 as the leftmost digit), when we shift to the right, extra 0s are added on the left. We call this sign extending the number, because the sign bit (leftmost bit) is extended to fill up the left. Remember when we learned in the last lesson about converting an 8-bit number to a 16-bit number? It's just the same.

class Hello { public static void main(String[] args) { System.out.println("Hello, world!"); int x = 20; int y = -20; System.out.print(x + " "); printBinary(x); System.out.print((x << 2) + " "); printBinary(x << 2); System.out.print((x >>> 2) + " "); printBinary(x >>> 2); System.out.println(); System.out.print(y + " "); printBinary(y); System.out.print((y << 2) + " "); printBinary(y << 2); System.out.print((y >>> 2) + " "); printBinary(y >>> 2); } ...

Notice there is only one change in the program: replacing >> by >>>. Why don't we try it:

[nurmes]btg: javac Hello.java [nurmes]btg: java Hello 20 00000000000000000000000000010100 80 00000000000000000000000001010000 5 00000000000000000000000000000101 -20 11111111111111111111111111101100 -80 11111111111111111111111110110000 1073741819 00111111111111111111111111111011 [nurmes]btg:

Only the last value has changed - rather than filling up with ones on the left when we shift -20 to the right, we fill up with zeros. This means the number is kind of meaningless in decimal. This is called zero extending and fills up with zeros on the left whether the number is positive or negative. There is no equivalent for left shifting - we always fill up with zeros.

As an exercise to try, can you convert 20 and -20 to hex numbers? Before you try it, do you know how many hex digits an int needs?

Here's the answers, anyone who gets them all right gets a gold star. Firstly, an int is 32 bits. One digit of hex is worth exactly four bits, so we need eight digits of hex for an int (two for a byte, four for an short and a whopping sixteen hex digits for a long).

So, remember how to do it yet? Since one digit of hex is worth four bits, break the binary value into four-bit chunks and replace each chunk by its hex equivalent. You're allowed to peek at the conversion chart above if you like.

So 20 becomes 0000 0000 0000 0000 0000 0000 0001 0100 which becomes 0x00000014. -20 becomes 1111 1111 1111 1111 1111 1111 1110 1100 which becomes 0xFFFFFFEC. Try it yourself. We can shorten 0x00000014 to just 0x14 by removing all the zeros.

You might remember, back in the mists of time (at the start of this lesson), I mentioned that hex numbers are written with an 0x in Java (that's why I keep writing them that way). So let's use our new and exciting hex values to change the program without actually changing it:

class Hello { public static void main(String[] args) { System.out.println("Hello, world!"); int x = 0x14; int y = 0xFFFFFFEC; System.out.print(x + " "); printBinary(x); System.out.print((x << 2) + " "); printBinary(x << 2); System.out.print((x >>> 2) + " "); printBinary(x >>> 2); System.out.println(); System.out.print(y + " "); printBinary(y); System.out.print((y << 2) + " "); printBinary(y << 2); System.out.print((y >>> 2) + " "); printBinary(y >>> 2); } ...

In fact the program will compile to exactly the same thing, because we've replaced the decimal values by their hex equivalents. Try it for yourself. Why not have a play about with some binary values of your own, using the printBinary methods?

That's it for this lesson. We've done some pretty hard core binary stuff recently - well done, you made it! There's one or two more things I want to say about binary yet, but I'll save those for another day. Fill out the questionnaire and give yourself a BIG pat on the back.

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

All these bits, I'm Going Loopy