CS 12 -- Lab 8

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.

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:

  0000 0000 0000 0000 0000 0000 0000 0101
  1111 1111 1111 1111 1111 1111 1111 1010

• 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:

  0000 0000 0000 0000 0000 0000 0000 0101
  0000 0000 0000 0000 0000 0000 0000 1100
  0000 0000 0000 0000 0000 0000 0000 1101

• 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:

  0000 0000 0000 0000 0000 0000 0000 0101
  0000 0000 0000 0000 0000 0000 0000 1100
  0000 0000 0000 0000 0000 0000 0000 0100

• 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:

  0000 0000 0000 0000 0000 0000 0000 0101
  0000 0000 0000 0000 0000 0000 0101 0000

• SHIFT RIGHT (insert 0): 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:

  0000 0000 0000 0000 0000 0000 0101 0000
  0000 0000 0000 0000 0000 0000 0000 0101

• SHIFT RIGHT (maintain sign): Given a value, shift the bits right by a specified number of positions, inserting bits that match the existing most significant positions. Since the uppermost bit indicates the sign of the value (0 is positive, 1 is negative), the sign of the value is maintained. The following code...

  int x = 0xf0000050;
  int y = x >> 3;
  System.out.println(Integer.toBinaryString(x));
  System.out.println(Integer.toBinaryString(y));

  ...will produce the following output:

  1111 0000 0000 0000 0000 0000 0101 0000
  1111 1110 0000 0000 0000 0000 0000 1010

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, based on a brutally simple model. 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.

In order to facilitate the organization of the bits into a stream, you should use the BitStream class. It will store a arbitrarily long sequence of bits into an array of int, making your job here much easier. You can grab this class at:

~sfkaplan/public/cs12/BitStream.java

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-8 when you use the cs12-submit command.