CS 12 -- Lab 6

We seek to write code that does a bit of the grunt work for data compression. Given a specific encoding where symbols are represented by a variable number of bits, we want to take a string, encode it, decode it, and compare it to the original. Any compressor/decompressor must perform these steps, and we particularly want to focus on how to manipulate data at a bit level to perform this encoding/decoding.

See the solution.

Bit manipulation operators

In order to manipulate individual bits, Java provides a number of useful operators that you can use on integer values. Each of these operators manipulates the bits of an integer on a bit-by-bit basis. Here is a listing of the basic operators and how to use them:

• NOT: Invert the bits of an integer. Consider the following code:

  int x = 5;
  int y = ~x;
  System.out.println(Integer.toBinaryString(x));
  System.out.println(Integer.toBinaryString(y));

  This code will emit the following output:

  00000000000000000000000000000101
  11111111111111111111111111111010

• OR: Given two values, takes the logical OR of each pair of bits taken from each position in the values. The following code...

  int x = 5;
  int y = 12;
  int z = x | y;
  System.out.println(Integer.toBinaryString(x));
  System.out.println(Integer.toBinaryString(y));
  System.out.println(Integer.toBinaryString(z));

  ...will produce the following output:

  00000000000000000000000000000101
  00000000000000000000000000001100
  00000000000000000000000000001101

• AND: Given two values, takes the logical AND of each pair of bits taken from each position in the values. The following code...

  int x = 5;
  int y = 12;
  int z = x & y;
  System.out.println(Integer.toBinaryString(x));
  System.out.println(Integer.toBinaryString(y));
  System.out.println(Integer.toBinaryString(z));

  ...will produce the following output:

  00000000000000000000000000000101
  00000000000000000000000000001100
  00000000000000000000000000000100

• SHIFT LEFT: Given a value, shift the bits left by a specified number of positions, inserting 0-valued bits at the least significant positions. The following code...

  int x = 5;
  int y = x << 4;
  System.out.println(Integer.toBinaryString(x));
  System.out.println(Integer.toBinaryString(y));

  ...will produce the following output:

  00000000000000000000000000000101
  00000000000000000000000001010000

• SHIFT RIGHT: Given a value, shift the bits right by a specified number of positions, inserting 0-valued bits at the most significant positions. The following code...

  int x = 80;
  int y = x >> 4;
  System.out.println(Integer.toBinaryString(x));
  System.out.println(Integer.toBinaryString(y));

  ...will produce the following output:

  00000000000000000000000001010000
  00000000000000000000000000000101

These operations can be used to set or test any single bit or group of bits. You will need to set bits to encode a given output, and test bits to decode them.

Your assignment

Assume a very simple encoding. Specifically:

1. The character e is encoded as the bit 0.
2. Any other character is encoded as the bit 1 followed by the least significant 8 bits of the char value.

You must write a SimpleCode class. It must contain two public methods:

1. public static int[] encode (String original);

   Given a String, encode each of its char elements using the encoding given above. Store the result in an array of int, where each integer contains the next 32 bits of the encoded representation.

2. public static String decode (int[] encoded);

   Given an array of int that contains an encoded representation, decode the sequence of symbols and return it as a String.

The main method of this class should pass a string into the encode method, and then pass the result of that call to the decode method, and finally compare the two.

What you must submit

Once you have written and tested the various classes, you must use the cs12-submit command to submit them. Submit this assignment as lab-6 when you use the cs12-submit command.