[COMP1110] [Course] [Schedule] [Laboratories] [Handouts] [Assessment] [Resources] [Search] [Site map]

Laboratory class 2

Help from your lab demonstrator

This week, your lab demonstrator will only be present in the lab during the middle hour. (In other words, he will arrive thirty minutes into the lab, and leave thirty minutes before the end.)

Discussion

There are two aims of this laboratory class: first, to develop skills in working with arrays and Strings; second, to develop skills working at the bit level, in preparation for Assignment 2.

Resources for this lab

(The links given here are also available on the Resources page.) You'll need to make use of the ANU Java Package Javadoc description for reading input and writing output, and the Java API Specification.

Exercise 1: array warm-up

Start by making a fresh directory for this lab. I suggest ~/comp1110/labs/lab2/. (The tilde ~ is the Unix way to refer to your home directory.)

Write a method that, given an array of integers, returns the largest difference between any two consecutive array elements. Then write a program that tests this method.

Exercise 2: arrays with user-selectable indexing

Arrays in Java are always indexed starting from 0. For example, the declaration/statement:

int[] x = new int[10];

creates a new array indexed from 0 to 9. In many other languages (Pascal, Ada, Eiffel . . .) you are allowed to choose the first and last indexes. Write a new class, say MyArray, that is a new type of array that allows an index range from p to q, where p and q are arbitrary int values, provided that the value of p is less than or equal to q. Include methods to access p and q, and each stored value, and also to set a new value into a location.

Remarks and hints:

The constructor will take p and q as its two parameters.

Exercise 3: string representation of binary values

You might like to refresh your memory about the binary representation of values from the COMP1100 material (see the link above) before attempting this exercise.

Values of type int are represented in the computer's memory using 32 bits. For example, the value 123456789 is represented as the bit sequence 00000111010110111100110100010101. Java provides a (static) method, toBinaryString (in the class java.lang.Integer), which takes an int parameter and returns a String representation of the parameter as a sequence of bits.

Write a short Java program to read in a value in decimal, then print out the result of evaluating toBinaryString on it.

Try your program on negative values, e.g. -1. Make sure that you understand the results. (Remember two's complement?)

If you run your program on the value 123456789, you'll find that the result is 111010110111100110100010101; in other words, leading zeros (which, of course, don't change the value) are not included. Modify your program so that exactly 32 bits are printed, so that the output for 123456789 is 00000111010110111100110100010101.

Remarks and hints:

You know from the description of toBinaryString that the String return value has length at least 1. So prepend a sequence of 31 zeros to the result of toBinaryString, then use one of the substring methods of class String to extract the last 32 characters.
To prepend the 31 zeros, it doesn't make sense to use a loop. This is done using nothing more high-tech than writing "0000000000000000000000000000000" +.

Exercise 4: bit manipulation - bitwise and, or, xor, ~

Java provides a number of operators that perform bit manipulation; we mentioned some of them already in Lecture 4.

Write a new program that reads in two integer values, storing them in int variables a and b, prints out their binary representation (using your method from the final part of Exercise 3), then prints out the decimal and binary representations of the values of a & b, a | b, a ^ b, and ~a and ~b.

Run your program on a variety of inputs and make sure that you understand the results.

Exercise 5: bit manipulation - bit shifting

Make a copy of your program from Exercise 4. This time, print out the binary representation of a, then the decimal and binary representations of the values of a << b, a >> b, and a >>> b.

Run your program on a variety of inputs and make sure that you understand the results. In particular, note the difference between a >> b, and a >>> b when a is a negative value. Read up about and make sure you understand the distinction between sign extension (as done by a >> b) and zero padding (as done by a >>> b).

Exercise 6: bit manipulation - putting it all together

For some applications, it is necessary to pack two values into one. For example, you might wish to pack two 16-bit values into one 32-bit value. In this exercise, we examine how to do that in Java, using a combination of bitwise operations and bit shifting.

For example, suppose we wish to store the two values 1234 and 5678 in the one 32-bit value. We can store 1234 using the high-order 16 bits, and 5678 using the low-order 16 bits:

(1234 << 16) | 5678

If x is one of these 32-bit values containg two 16-bit values, we can extract the two 16-bit values in Java thus:

x>>> 16
x & 0xffff

Note that 0xffff is the hexadecimal value equal to the binary value 00000000000000001111111111111111. Make sure you understand how all of this works.

By combining bitwise operators and shifting, work out expressions for altering just the high-order 16 bits, or just the low-order 16 bits, of one of these packed values.

Now write a new Java program that allows you to explore bit packing in this way. It should read a series of commands from the keyboard, and write the answers on the screen.

You might do this as follows: read a one-letter command, then read the appropriate operands. For example, you might implement these commands:

command	operands	prints out

p	2 ints, a and b	packed value with a in high-order 16 bits, b in low-order bits; print the result in decimal and binary
u	1 int, a packed value	unpacked values of the high- and low-order 16 bits; print the result in decimal
h	2 ints, a and b	treat a as a packed value; reset the high-order 16 bits to be b
l	2 ints, a and b	treat a as a packed value; reset the low-order 16 bits to be b

Then sample input (in blue italics) and output might look like this:

p 1234 5678 80877102/00000100110100100001011000101110 u 80877102 1234/5678 h 80877102 4321 283186734/0010000111000010001011000101110 u 283186734 4321/5678 l 283186734 8765 283189821/0010000111000010010001000111101 u 283189821 4321/8765