Understanding two’s complement

In this article, we dive into the topic of two’s complement number representation and try to explain how it works. We’ll work through it together, as I also need to check and validate my own understanding.

In a computer, numbers are represented in binary notation, as a sequence of bits. Since we need to work with negative numbers as well as positive ones, we need a system to represent the sign.

Two’s complement is a method to encode the sign information. Two’s complement is used by Java to represent integer numbers. For example, a Java language int is a 32-bit signed integer in the range of [-231, 231 – 1].

Why this range? We’ll get to that in a moment. But first, let’s look at numbers whose representation uses only the largest digit in a base.

In decimal, 9 is the largest digit. 9 = 10 – 1, 99 = 102 – 1, 999 = 103 – 1 and so forth.

In binary, 11 = 22 – 1, 1111 = 24 – 1.

In hexadecimal, F = 161 – 1 and FF = 162 – 1.

To conclude, in a base b, a number written by repeating the largest digit n times is equal to bn – 1.

To get the next largest number, we write 1 and turn all the other digits into zeros, effectively obtaining bn.

For example, FF16 + 1 = 10016 = 162

In two’s complement notation, the leftmost bit is reserved for the sign. By convention, it has a negative value.

Take the 32-bit number:

1_111111111111111111111111111111111111111

Can you guess what number it is?

The 31 bits to the right of the sign bit encode the number 231 – 1, as explained. The sign bit is equal to -231. Adding them up we obtain -1.

-231 + 231 – 1 = -1

We can verify this easily, using binary to hex conversion.

System.out.println(0xffffffff == -1); // true

If…

11111111111111111111111111111111

is -1, then…

10000000000000000000000000000000

is the minimum value of int, right?

System.out.println(0x80000000 == Integer.MIN_VALUE); // true

Also, zero followed by 31 set bits should be the maximum value of int.

System.out.println(0x7fffffff == Integer.MAX_VALUE); // true

Well, that explains why  [-231, 231-1] is the range of a 32-bit signed two’s complement integer.

Another thing we can do is to revert the sign, in order to find a number’s complement. To find the complement of a number x, we take 231x.

For ex., to find the representation of the number -15, we take 231 – 15.

10000000000000000000000000000000 -
00000000000000000000000000001111 =
11111111111111111111111111110001

Indeed, in Java, 0xfffffff1 maps to -15.

Using a checked list in Java

Java offers checked versions of the collection classes List,  Set and Map. Both normal and checked collections provide type checking, but checked collections just make it easier to spot a type-error when it occurs. Let’s see the difference.

A checked list can be obtained from a factory method exposed by the Collections class.

public static <E> List<E> checkedList(List<E> list,
                                      Class<E> type)

The method expects a list object and a type token and returns the checked list. The type token should be the same class as the parameter type declared by the list.

According to the documentation, a checked list is a “dynamically typeset view over the specified list”.  We also learn that:

To illustrate the point, let’s define a method that can add “pears” to “apples”. We can pretend the method is from a third-party library written before the introduction of generics (in JDK5).

@SuppressWarnings("unchecked")
void unsafeAdd(Collection c, Object e) {
    c.add(e);
}

The author used a raw type java.util.Collection and annotated the method with @SuppressWarning to silence the compiler.

For the sake of the argument, let’s also examine a type-safe version of the same method.

// add element to collection in a generic fashion
<T> void add(Collection<T> c, T e) {
    c.add(e);
}

If we try to call the add() method in a way that violates type guarantees, our code doesn’t even compile. On the other hand, with the unsafe method we get no such warning.

Now let’s see what happens when we attempt to pass an normal/unchecked list to the unsafeAdd method.

List<Integer> list = Arrays.asList(1, 2, 3);
unsafeAdd(list, "4");

Here’s the stack trace:

 Exception java.lang.UnsupportedOperationException
        at AbstractList.add (AbstractList.java:153)

The UnsupportedOperationException is a generic error thrown by the parent class which that doesn’t really point to the actual problem. Had we performed many different operations on the list (i.e. in the same method scope), it would have been unclear which one caused the error.

Now let’s pass a checked list to the unsafeAdd method.

List<Integer> ckList =  Collections.checkedList(list, Integer.class);
unsafeAdd(ckList, "5");

Now we get another error – a better one. Here’s the stack trace:

Exception java.lang.ClassCastException: Attempt to insert class java.lang.String element into collection with element type class java.lang.Integer
|        at Collections$CheckedCollection.typeCheck (Collections.java:3047)

The ClassCastException correctly identifies the problem and has a nice, helpful message.

Conclusion

While both checked and unchecked lists prevent type violations, checked list operations fail immediately, with a clear, appropriate exception that is useful for debugging.

How to deploy a Spring Boot app to WildFly

According to the spring.io docs, stand-alone Spring Boot applications can be packaged as a WAR or JAR, which can be deployed to any Servlet 3.1+ compatible container.

You might think this is possible out of the box, but in reality we’ll need a couple of tweaks. Nothing too complicated.

Let’s use the example REST service application provided by the Spring guides.  As a quick reminder, all this app does is respond to HTTP Get requests with a greeting in JSON format.

To deploy the app to an external server, first we extend SpringBootServletInitializer; this is the only change in the application code we are going to need.

package hello;

import org.springframework.boot.SpringApplication;
import org.springframework.boot.autoconfigure.SpringBootApplication;
import org.springframework.boot.web.servlet.support.SpringBootServletInitializer;

@SpringBootApplication
public class Application extends SpringBootServletInitializer {

    public static void main(String[] args) {
        SpringApplication.run(Application.class, args);
    }
}

Next we edit the gradle.build file.

Remember that Spring Boot apps run in the embedded Tomcat Server. Since our target HTTP runtime (WildFly) uses the Undertow servlet, we don’t want any Tomcat stuff on the classpath.

Let’s exclude the spring-boot-starter-tomcat module from the parent project.

gradle.build

configurations {
    all.collect { configuration ->
        configuration.exclude   group: 'org.springframework.boot', module: 'spring-boot-starter-tomcat'
    }
}

Next we declare a dependency to javax.servlet module.

dependencies {
    compile("org.springframework.boot:spring-boot-starter-web")
    compile("javax.servlet:javax.servlet-api:3.1.0")
    testCompile('org.springframework.boot:spring-boot-starter-test')
}

Finally let’s add the WAR plugin.

plugins {
    id 'war'
}

Now try to package the app using ./gradlew bootWar. If this succeeds, you should be able to deploy the file to WildFly without errors.

Note that WildFly will use the application name as the context root. Visit http://localhost:8080/gs-rest-service/greeting to test the result.

{"id":1,"content":"Hello, World!"}

Hope it helps.