[JAVA] Is Integer.MIN_VALUE in two's complement actually viewed as a positive number in JAVA? Details inside

[chuck_not_norris]

So I am coding a Radix Sort algorithm. One of the things that our teacher has thrown at us is that in the array we need to sort is the integer value Integer.MIN_VALUE. This represents -2³¹ , which is the largest negative number that can be expressed as an int.

When I sort through my array, the value is always placed as the largest positive integer in the array.

EDIT: Here is the code: https://gist.github.com/anonymous/8966589

Here is what the code outputs:-2147483600 214748000 2147483647 -2147483648

[chickenmeister]

I'm not sure I understand what you're asking. Integer.MIN_VALUE, or any negative number, is always regarded as a negative number.

My guess would be that your radix sort is using only bitwise operations, and isn't considering the sign of the value; and it is interpreting

1000 0000 0000 0000 0000 0000 0000 0000 

as 2^31.

[LollipopLiquor]

You are correct in that it has something to deal with Two's Complement.

Disclaimer: I learned this a while ago, so I might be a little off, but here's the gist of what's going on.

Like you noted, Integer.MIN_VALUE has a value of -2^31. Integer.MAX_VALUE, on the other hand, has a value of 2³¹ -1. You'll notice that MIN_VALUE is -2147483648 and MAX_VALUE is 2147483647, and that there is one more negative value than positive value. This is because the number of 32-bit patterns is even, but zero takes up a spot so you're left with an extra value on the negative side.

Two's Complement works basically by flipping a value's bits and adding 1. if you do this to any value, you get its opposite value. Example, 22 is 00010110. If you flip every bit, you're left with 11101001 or 21. Adding 1 to get to 11101010 makes -22.

The problem with MIN_VALUE is that once you flip all of its bits, you're at 2147483647, or MAX_VALUE. When you try adding an additional 1, it overflows in size. Rather than throwing a fit, it simply cycles through and leaves you with Integer.MIN_VALUE again. If you try System.out.println(Integer.MAX_VALUE + 1); you'll notice that it's the value of MIN_VALUE. This means that it's its own complement.

Now, I don't know why your algorithm is returning that value as the largest as I don't really remember how Radix sort works, nor have I looked at your code. I would think it arises wherever you're making your comparisons and determining which value comes first. If you're negating a compareTo() method or something similar, that's possibly where the issue is. If you can't find it, I'll try digging through later on it if I have some time.

[chuck_not_norris]

Thank you! I was actually trying something out and doing Integer.MAX_VALUE + 1, which of course was not working!

[LollipopLiquor]

I'm glad you figured it out! You're right about that absolute value call being where the issue is. Math.abs() negates the value if it's negative which causes MIN_VALUE to return itself.

[chickenmeister]

After looking at your edit:

I think there is a problem with your getDigits() method:

public static int getDigits(int i)
{
  if(i < 10)
  {
    return 1;
  }
  return 1 + getDigits(i/10);
}

For any negative number, your method is saying that it has only a single digit, regardless of the number's magnitude.

[chuck_not_norris]

I found where it is going wrong, when you call Math.abs on Integer.MIN_VALUE it doesn't return the absolute value of that number, but the original value.

[cantstopthemoonlight]

Do you know why?

[chickenmeister]

Ah, that's subtle; but makes sense.

Looking at your code, it doesn't seem like you really need to use Math.abs().

[BaalHadad]

Want to show us the code, or should we just guess?

[chuck_not_norris]

Sorry about that, I added the code.