Unsigned Challenge

Overview

Its easy to assume that because Java doesn't support unsigned primitives that you need a complex wrapper to using unsigned numbers.

The challenge

Modify the following class which has been written to use signed int as unsigned value. The starting code works for signed values. You need to change the methods so it treats them as unsigned 32-bit int values. The aim is to add/change a minimum of lines. (You can't change the tests or turn them off)

public enum Unsigned {;
    public static int add(int i, int j) {
        return i + j;
    }

    public static int subtract(int i, int j) {
        return i - j;
    }

    public static int multiply(int i, int j) {
        return i * j;
    }

    public static int shiftLeft(int i, int n) {
        return i << n;
    }

    public static int shiftRight(int i, int n) {
        return i >> n;
    }

    public static int parseUnsignedInt(String text) {
        return Integer.parseInt(text);
    }

    public static String toString(int n) {
        return Integer.toString(n);
    }

    public static void main(String... args) {
        assert "2500000000".equals(toString(subtract(add(2000 * 1000 * 1000, 1750 * 1000 * 1000), 1250 * 1000 * 1000)));
        assert "4000000000".equals(toString(multiply(1000 * 1000, 4000)));
        assert "3200000000".equals(toString(shiftLeft(100 * 1000 * 1000, 5)));
        assert "1000000000".equals(toString(shiftRight(parseUnsignedInt("4000000000"), 2)));

        ByteArrayOutputStream baos = new ByteArrayOutputStream();
        DataOutputStream dos = new DataOutputStream(baos);
        writeUnsignedInt(dos, multiply(1000 * 1000, 4000));
        writeUnsignedInt(dos, parseUnsignedInt("3210000000"));
        dos.close();
        DataInputStream dis = new DataInputStream(new ByteArrayInputStream(baos.toByteArray()));
        assert "4000000000".equals(toString(readUnsignedInt(dis)));
        assert "3210000000".equals(toString(readUnsignedInt(dis)));
        dis.close();
    }
}

Hint: The solutions are surprisingly simple (which is the point of this article) If you are adding many lines of code, you are heading down the wrong path.

Comments

  1. The critical fact is that all your arithmetic operators are insensitive to whether our representation is two's complement (signed) or unsigned.

    A few small fixes are required (in addition to implementing a couple of trivial missing methods):

    * shiftRight needs to use the unsigned operator, >>>, which puts a 0 in the most-significant position (while >> will leave a 1 there if the bits correspond to a negative number in two's complement).

    * to implement toString, we do an unsigned right-shift, to dump the sign bit, then cast to long and shift back to the left. We've then lost our LSB, so we need to add it back in.

    * Finally, we sort of do the opposite with parseInt: parse the thing as a long, shift right (signed or unsigned) so we can safely cast to int, then shift left and, at last, recover our LSB.

    Is there a slicker way (i.e., one with fewer bitwise operators) to implement toString and parseUnsigned? I kind of feel like there should be, but I'm not really a bit-twiddling pro.

    Fun puzzle! Fixed sources here: https://gist.github.com/1638122

    ReplyDelete
  2. The following worked for me. I wonder if it's always correct, and if there is a simpler way:

    public static int parseUnsignedInt(String text) {
    return (int) Long.parseLong(text);
    }

    public static String toString(int n) {
    return Long.toString(n & (-1L >>> 32));
    }

    ReplyDelete
  3. @Chris, Good attempt, thank you for the feedback.

    @Thomas, I tend to use 0xFFFFFFFFL but perhaps -1L >>> 32 is clearer.

    ReplyDelete

Post a Comment

Popular posts from this blog

Java is Very Fast, If You Don’t Create Many Objects

System wide unique nanosecond timestamps

Unusual Java: StackTrace Extends Throwable