Java - Need help with binary/code string manipulation

Question

For a project, I have to convert a binary string into (an array of) bytes and write it out to a file in binary.

Say that I have a sentence converted into a code string using a huffman encoding. For example, if the sentence was: "hello" h = 00 e = 01, l = 10, o = 11

Then the string representation would be 0001101011.

How would I convert that into a byte? <-- If that question doesn't make sense it's because I know little about bits/byte bitwise shifting and all that has to do with manipulating 1's and 0's.

Answer 1

Here is a simple, but probably inefficient implementation:

import java.io.FilterOutputStream;
import java.io.IOException;
import java.io.OutputStream;

public class BitOutputStream extends FilterOutputStream {

  private int bits = 0;
  private int n = 0;
  private long totalBits = 0;

  public BitOutputStream(OutputStream out) {
    super(out);
  }

  private void writeSingleBit(int bit) throws IOException {
    bits = (bits << 1) | (bit & 1);
    n++;
    totalBits++;
    if (n == 8) {
      super.write(bits);
      bits = 0;
      n = 0;
    }
  }

  /**
   * Writes the <i>numberOfBits</i> lower bits of <i>bitsToWrite</i> to the
   * output stream, starting with the most significant bit.
   */
  public void writeBits(int bitsToWrite, int numberOfBits) throws IOException {
    for (int i = numberOfBits - 1; i >= 0; i--) {
      int bit = bitsToWrite >> i;
      writeSingleBit(bit);
    }
  }

  @Override
  public void write(byte[] b, int off, int len) throws IOException {
    for (int i = 0; i < len; i++)
      writeBits(b[off + i], 8);
  }

  @Override
  public final void write(int b) throws IOException {
    writeBits(b, 8);
  }

  @Override
  public final void flush() throws IOException {
    writeBits(0, (8 - n) & 0x07);
  }

  /**
   * Returns the number of bits that have been written to this bitstream.
   */
  public long getTotalBits() {
    return totalBits;
  }
}

And the corresponding unit test:

import static org.junit.Assert.*;

import java.io.ByteArrayOutputStream;
import java.io.IOException;

import org.junit.Test;

public class BitOutputStreamTest {

  @Test
  public void hello() throws IOException {
    ByteArrayOutputStream baos = new ByteArrayOutputStream();
    BitOutputStream bos = new BitOutputStream(baos);
    bos.writeBits(0x00, 2);
    bos.writeBits(0x01, 2);
    bos.writeBits(0x02, 2);
    bos.writeBits(0x02, 2);
    bos.writeBits(0x03, 2);
    assertEquals(10, bos.getTotalBits());
    bos.close();
    assertEquals(16, bos.getTotalBits());
    assertArrayEquals(new byte[] { 0x1A, (byte) 0xC0 }, baos.toByteArray());
  }
}

This code doesn't output the bits in the string representation you want, but when you want to write them to a byte-based stream later, this is the way to go.

Update (2010-09-25): Fixed a bug in the write(byte[], int, int) method. I forgot to add off to the array index.