Fail to Understand Java Two's Complement

Question

I have this code:

package com.company;

import java.net.InetAddress;
import java.net.UnknownHostException;

public class Main {

    private final static int broadcast = 0xffffffff;    //4294967295, or 255.255.255.255
    private final static int firstClassE = 0xf0000000;  //4026531840, or 240.0.0.0

    public static int GetIntInetAddress(InetAddress toConvert)
    {
        final byte[] addr = toConvert.getAddress();

        final int ipAddr =
                ((addr[0] & 0xFF) << (3 * 8)) +
                        ((addr[1] & 0xFF) << (2 * 8)) +
                        ((addr[2] & 0xFF) << (1 * 8)) +
                        (addr[3] & 0xFF);

        return ipAddr;
    }

    public static Boolean IsClassEAddress(InetAddress address)
    {
        int curAddr = GetIntInetAddress(address);
        Boolean test1 = curAddr >= firstClassE;
        Boolean test2 = curAddr < broadcast;
        System.out.println(String.format("\ncurAddr: %s, firstClassE: 240.0.0.0, broadcast: 255.255.255.255", address.getHostAddress()));
        System.out.println(String.format("curAddr: %d, firstClassE: %d, broadcast: %d, curAddr >= firstClassE: %s, curAddr < broadcast: %s",
                                         curAddr, firstClassE, broadcast, test1 ? "true" : "false", test2 ? "true" : "false"));
        return (test1 && test2) ? true : false;
    }

    public static void main(String[] args) throws UnknownHostException
    {
        if (IsClassEAddress(InetAddress.getByName("1.0.0.0")))
        {
            // Raise a flag
            System.out.println("Class E IP address detected.");
        }
        if (IsClassEAddress(InetAddress.getByName("250.0.0.0")))
        {
            // Raise a flag
            System.out.println("Class E IP address detected.");
        }
        if (IsClassEAddress(InetAddress.getByName("239.255.255.255")))
        {
            // Raise a flag
            System.out.println("Class E IP address detected.");
        }
        if (IsClassEAddress(InetAddress.getByName("240.0.0.0")))
        {
            // Raise a flag
            System.out.println("Class E IP address detected.");
        }
        if (IsClassEAddress(InetAddress.getByName("240.0.0.1")))
        {
            // Raise a flag
            System.out.println("Class E IP address detected.");
        }
        if (IsClassEAddress(InetAddress.getByName("255.255.255.255")))
        {
            // Raise a flag
            System.out.println("Class E IP address detected.");
        }
    }
}

Which produces the following output:

curAddr: 1.0.0.0, firstClassE: 240.0.0.0, broadcast: 255.255.255.255
curAddr: 16777216, firstClassE: -268435456, broadcast: -1, curAddr >= firstClassE: true, curAddr < broadcast: false

curAddr: 250.0.0.0, firstClassE: 240.0.0.0, broadcast: 255.255.255.255
curAddr: -100663296, firstClassE: -268435456, broadcast: -1, curAddr >= firstClassE: true, curAddr < broadcast: true
Class E IP address detected.

curAddr: 239.255.255.255, firstClassE: 240.0.0.0, broadcast: 255.255.255.255
curAddr: -268435457, firstClassE: -268435456, broadcast: -1, curAddr >= firstClassE: false, curAddr < broadcast: true

curAddr: 240.0.0.0, firstClassE: 240.0.0.0, broadcast: 255.255.255.255
curAddr: -268435456, firstClassE: -268435456, broadcast: -1, curAddr >= firstClassE: true, curAddr < broadcast: true
Class E IP address detected.

curAddr: 240.0.0.1, firstClassE: 240.0.0.0, broadcast: 255.255.255.255
curAddr: -268435455, firstClassE: -268435456, broadcast: -1, curAddr >= firstClassE: true, curAddr < broadcast: true
Class E IP address detected.

curAddr: 255.255.255.255, firstClassE: 240.0.0.0, broadcast: 255.255.255.255
curAddr: -1, firstClassE: -268435456, broadcast: -1, curAddr >= firstClassE: true, curAddr < broadcast: false

What I am not understanding is why the numbers and comparisons are not what I expect them to be, yet the code produces the results I want. I gather it's the whole two's complement thing, which I just don't "get" for some reason. Mechanically, I know it (two's complement) is flipping bits and adding 1 but what I don't get is, why are my comparisons working properly if some of the numbers are inverted?

For example, in the first check for IP 1.0.0.0, the int value 16777216 is checked to see if it's smaller than the int value for 255.255.255.255, which is -1. The result is false, but the broadcast IP, when converted to an int, is obviously larger, not smaller, than the IP for 1.0.0.0. Likewise, the check for 1.0.0.0 being at least, or higher than, 240.0.0.0 returns true, when we know that clearly isn't the case.

I've checked the boundary cases and everything is working... I just don't understand why it is (and I wrote the code, so go figure!). If there is a more clear method of determining if an IP fals within a range, I would like to explore that as my way must not be making sense, despite working (or does it?)

In IntelliJ, there's another strange example of this behaviour. When I examine an address, the inspector is showing both the proper value and the negative value, as I've highlighted with red arrows in the pic below. Using Windows calc, I put in -84 and converted to hex and received FFF...FAC. When I put in 172, I received just AC... why do I get the same hex number, just preceeded by a 1 in the most sig position?

UPDATE:

Thanks for all the patient discussion and great answers! I think I get the mechanics of the thing, but still grappling with the subtleties of usage. :) Cheers!

Answer 1

In a 32-bit two's complement number, the non-negative integers are 0x00000000 - 0x7fffffff and these convert from hex to deciminal in the ordinary way.

The lowest (ie most negative) number is represented in the machine as 0x80000000 (ie the highest-order bit and no other bit is set). What this bit being set really means is add the positive integer indicated by the 31 lower-order bits to the number -(0x80000000).

Exercise: What is the number -84 in 32-bit two's complement? Since it is negative, we have to set the high-order bit. So we start with -(0x80000000) = -2147483648. Now you can solve algebraically what the other 31 bits need to be:

-2147483648 + x = -84
=> x = 2147483648 - 84
=> x = 2147483564
=> x = 0x7fffffac

And it should be obvious that if you take 0x80000000 | 0x7fffffac, you get 0xffffffac.

It should also be obvious that 0x7fffffac = (0x7f000000 + 0xff0000 + 0xff00 + 0xac) and the expression in parentheses is equivalent to (2130706432 + 16711680 + 65280 + 172). The fact that the lower-order byte is equivalent to decimal 172 is meaningless without considering the other 3 bytes.

Your Comparisons

Now you mention that your comparisons are "not what you expect them to be". I don't know what you expect them to be since you haven't explained, but my guess is you want a true return value for IP addresses in the range [240.0.0.0 .. 255.255.255.255) non-inclusive of the right-hand side of the range. This means IP addresses in the range [0xf0000000 .. 0xffffffff) non-inclusive.

If those are 32-bit two's complement integers, this is the range [-268435456, -1), so any expression of the form (0xf0000000 <= ip_addr && ip_addr < 0xffffffff) will give you the correct result.

Since your function returns a more convoluted version of the above expression, it gives the correct result.

By the way, are you familiar with the boolean type? Is there some reason your method needs to return a boxed primitive (ie Boolean)?

Answer 2

There are several ways you can make sure unsigned 32-bit integers are compared correctly:

1) Use Integer.compareUnsigned, which was added in Java 8.

2) Use a long instead of an int. If the value is constructed properly, the results will be positive integers in the range 0 to 2³²-1, which can then be compared with no problem. You have to be careful about the order in which casting and bitwise operations take place, so that things don't sign extend. This works:

    final long ipAddr =
            (((long)addr[0] & 0xFF) << (3 * 8)) +
            (((long)addr[1] & 0xFF) << (2 * 8)) +
            (((long)addr[2] & 0xFF) << (1 * 8)) +
            ((long)addr[3] & 0xFF);

When each byte is cast to a long, it will sign extend, but the & 0xFF zeroes any 1 bits that were added with sign extension.

3) Write a compare method, or lessThan or lessThanOrEqual or whatever you need, that accounts for the signs. A method like this would have to have special cases for when the arguments have different signs. E.g.:

static int compareUnsigned(int x, int y) {
    if (x >= 0 && y < 0) {
        return -1;        // y is actually greater than x if unsigned
    }
    else if (x < 0 && y >= 0) {
        return 1;         // x is greater than y if unsigned
    } else {
        return Integer.compare(x, y);
    }
}

or, more compactly,

static int compareUnsigned(int x, int y) {
    if (((x ^ y) & 0x80000000) != 0) {  // see if x and y have different signs
        return (x < 0) ? 1 : -1;     
    } else {
        return Integer.compare(x, y);
    }
}

Actually, this is how it's done in the Java 8 source:

static int compareUnsigned(int x, int y) {
    return Integer.compare(x + Integer.MIN_VALUE, y + Integer.MIN_VALUE);
}

which I didn't think of at all.

Answer 3

You are right, this is an issue with two's complement, I can only advise you to read up on it and finally get it - it will bite you again and again in various integer overflow problems (It's even used in some of the core Java libraries).

The issue itself is that in Java Integer holds numbers from -(2^31) to (2^31)-1. The value of 255*255*255*255 is 2^32 - 1. It's not representable as a signed int. Hence when you convert the IP to a signed int you don't get a sensible (to you) value. If you want to compare IPs with the built in 'less than' use a primitive where an IP will actually fit - like a long.

Same thing happening in the second part. A signed byte holds values from -128 to 127. You are putting 255 there. Why are you expecting a sane result? Now if you use unsigned arithmetic where byte holds 0..255, it all works fine.

Answer 4

To summarize, you want IsClassEAddress(InetAddress address) to return true if the address is between 240.0.0.0 and 255.255.255.254 inclusive. This takes 2 lines of code:

public static Boolean IsClassEAddress(InetAddress address)
{
    int curAddr = GetIntInetAddress(address);
    return ((curAddr & 0xF0000000) == 0xF0000000) && (curAddr != 0xFFFFFFFF);
}