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. Chris Fesler19 January 2012 at 05:24

    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. Thomas Mueller19 January 2012 at 06:45

    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. Peter Lawrey19 January 2012 at 08:41

    @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

Image
  You still have to watch how many objects you create. This article looks at a benchmark passing events over TCP/IP at 4 billion events per minute using the net.openhft.chronicle.wire.channel package in Chronicle Wire and why we still avoid object allocations..  One of the key optimisations is creating almost no garbage. Allocation is a very cheap operation and collection of very short-lived objects is also very cheap. Does this really make a difference? What difference does one small object per event (44 bytes) make to the performance in a throughput test where GC pauses are amortised? While allocation is as efficient as possible, it doesn’t avoid the memory pressure on the L1/L2 caches of your CPUs and when many cores are busy, they are contending for memory in the shared L3 cache.  Results Benchmark on a Ryzen 5950X with Ubuntu 22.10. JVM Vendor, Version No objects Throughput, Average Latency* One object per event Throughput, Average Latency* Azul Zulu 1.8.0_322 60.6 ...
Read more

System wide unique nanosecond timestamps

A Unique Identifier can be very useful for tracing. Those ids are even more useful when they contain a high-resolution timestamp.  Not only do they record the time of an event, but if unique can help trace events as they pass through the system. Such unique timestamps however can be expensive depending on how they are implemented.   This post explores a lightweight means of producing a unique, monotonically increasing system-wide nano-second resolution timestamp available in our open-source library. Uses for Unique Identifiers Unique identifiers can be useful to associate with a piece of information so that information can be referred to later unambiguously. This could be an event, a request, an order id, or a customer id. They can naturally be used as a primary key in a database or key/value store to retrieve that information later. One of the challenges of generating these identifiers is avoiding creating duplicates while not having an increasing cost.  You could ...
Read more

What does Chronicle Software do?

Image
Overview Chronicle Software is about simplifying fast data.  It is a suite of libraries to make it easier to write, monitor and tune data processing systems where performance and scalability are concerned. But its free, how do you make money, through support? We offer premium support . However, we often hear from users for the first time about a year after they have it in production.  Most users find they can support the software themselves.  It is only after a year or so, they have questions or concerns about where to take the product next.  In many cases, it is to a problem we have already solved and they just need to upgrade their software or use a new module we have added. As we don't know who is using most of our software, we can't advise them on how best to use our software and what updates or enhancements they would benefit from. We need users to contact us and ask questions.  We have a free forum , and we respond to 50% of questions in 2 hours...
Read more