20061113

Bits of Java

Note: Today's coding gem is one that probably most Java programmers have experienced at least once.

A student of mine came to me with a problem from a different class she was taking. She had to write a program to generate truth tables for certain electrical gates. Because she's in my Java class, Java was her choice to complete the assignment. While I teach Java, I'm very unfamiliar with many of its low level aspects. This was a unique challenge for me.

These particular electrical gates required 4 binary inputs. How could I quickly generate all 16 possible binary combinations of 1's and 0's without resorting to spaghetti code? My first thought was to write a simple 'for' loop to generate the binary bits.

Solution #1:

    for (int i = 0; i < 16; i++) { // Combination Number
        for (int j = 0; j < 4; j++) { // Nth bit in combination
            int bit = (int) Math.pow(2,j);
            System.out.print( (i&bit)/bit );
        } // End For
        System.out.println("");
    } // End For

It just looks ugly, but it's mathematically correct (or at least plausible). We call "Math.pow", convert double to integer, there seems to be division taking place (but it's anyone's guess as to why), and we still have to perform the logical "and" (&). Bleh! How is anyone suppose to understand what's going on?

Solution #2:

    for (int i = 0; i < 16; i++) { // Combination Number
        for (int j = 0; j < 4; j++) { // Nth bit in combination
            System.out.print( (i>>>j)&1 );
        } // End For
        System.out.println("");
    } // End For

It's a little cleaner. There's a unsigned shift which is then compared and-wise to the number 1. It's only two operations, both of which happen at the binary level. Works for me. Too bad I figured this out after she came up with her own solution using large, ugly 2D-arrays.

No comments: