javaencodingbinaryhuffman-codedataoutputstream

Implementing a writeBit method in Java


So I know that in Java you cannot write out individual bits to a file and that you have to use writeByte. I have some understanding that there is a way to implement a writeBit method that makes use of writeByte by calling writeByte once 8 'bits' are concatenated together. I was hoping to implement this like:

public void writeBit(char bit) {
    try {
    //functionality here
    } catch (IOException e) {
        System.out.println(e);
    }
}

But I just cannot seem to get started. I understand that I should probably have some attribute that keeps track of how many bits I have concatenated, but other than that I'm lost as to how to implement this.

I guess my big question here is how can I continuously call writeBit without losing my concatenated String of bits, and what would an implementation of writeBit look like, if it were to make use of writeByte?

As a side note, I am using a DataOutputStream here if this was not clear.


Solution

  • I've noticed a couple people have talked about using two instance variables, one to store the byte as you add bits to it and another to keep track of how many bits have been added so far. While this is a perfectly good way to do it, I'd like to show why you don't need a second instance variable.

    Theory

    There's no need to keep track of how many bits have been added so far. The only piece of information we need is "has the byte been filled yet?". Instead of initializing your byte to 0, try initializing it to a value of 1. Then each time you add a bit, shift the bits of the byte to the left one place (using the bitshift operator <<), and then add the new bit in the rightmost place.

    In practice, it would look something like this, where X is the newly added bit:

    Initialize the byte to a value of 1: 00000001

    To insert a new bit, shift the bits to the left: 00000010

    And add the new bit X in the rightmost place: 0000001X

    Shift left: 000001X0

    Add the new bit: 000001XX

    Eventually, you'd have 7 bits written from your method and the leftmost bit would be 1: 1XXXXXXX

    So in your method, you can check to see if the leftmost bit is set every time it's called. If it is, then you know you're ready to write the byte to the file on this iteration. You would start by doing the same thing, shifting left and then adding the new bit, so now you have XXXXXXXX. Then you would write the now-full byte to the file, and then reset the byte to a value of 1 so the cycle can start over again.

    Writing the code

    First you'll need an instance variable to keep track of these bits. It will need to be type byte, and I'll just call it buffer.

    To shift the bits to the left one place, we can use the bitshift operator, <<. And, to make our lives even easier, there's even a bitshift assignment operator, <<=, so we can perform the bitshift and assign the new value back to the variable all in one operation. This leaves us with:

    buffer <<= 1;
    

    The next thing we'll need to do is add the new bit. If you OR a value with 1, the rightmost bit will be set, and the rest of the bits will be unaffected. If you OR a value with 0, none of the bits are affected. We can use this trick to only set the rightmost bit if the new bit is a 1 (The |= is the OR assignment operator):

    buffer |= bit ? 1 : 0;
    

    Then, the last piece of this code is writing the if statement to check if the leftmost bit is set. If it is, then when we AND it with 10000000, we will get 10000000. If not, we will get 00000000. 10000000 is 128 in decimal (or -128, or 256, all will work), so our expression is:

    (buffer & 128) == 128
    

    Result

    Putting all these pieces together, we get:

    // Notice bit is type boolean
    public void writeBit(boolean bit) {
        // If the leftmost bit in buffer is set:
        if ((buffer & 128) == 128) {
    
            // Shift all the bits in buffer to the left 1 place
            buffer <<= 1;
    
            // Add the new bit in the rightmost place
            buffer |= bit ? 1 : 0;
    
            // Write the now-full byte to the file
            // I'm just calling your DataOutputStream "dos" here
            try {
                dos.writeByte(buffer);
            } catch (IOException e) {
                throw new RuntimeException();
            }
    
            // Reset buffer to a value of 1
            buffer = 1;
        } else {
            // Shift all the bits in buffer to the left 1 place
            buffer <<= 1;
    
            // Add the new bit in the rightmost place
            buffer |= bit ? 1 : 0;
        }
    }