Java 8 Unsigned Integer Addition and Potential Overflow

Question

I'm working exercises from the book "Java SE 8 for the Really Impatient" by Cay S. Horstmann. One of the exercises based on the improvements in the Number classes asks:

Write a program that adds, subtracts, divides, and compares numbers between 0 and 2³² - 1, using int values and unsigned operations. Show why divideUnsigned and remainderUnsigned are necessary.

The problem is, if you add 2 unsigned ints, the sum may overflow the integer limit. I don't see a way to prevent that without using a long to store the sum and checking if it's greater than Integer.MAX_VALUE. Is it possible to do this using ints only?

Holger · Accepted Answer · 2015-01-13 17:23:33Z

6

The Two's complement used for integer values has the neat property that for adding and subtracting it is irrelevant whether you interpret the values as signed or unsigned.

Therefore, even at CPU level, there are no distinct instructions for adding/subtracting signed or unsigned numbers. It’s all about interpretation.

So when you add or subtract two unsigned numbers using the signed int type, the result may overflow in the signed int range. But when printing the now-negative number using Integer.toUnsignedString the result will be the correct unsigned value, assuming that the operation didn’t even overflow in the unsigned integer value range.

That’s why the class java.lang.Integer provides special unsigned operations only where necessary, i.e. for comparing two unsigned values, for division and remainder and for conversions from and to String (and to long, while a type-cast from long to int is already sufficient for the other direction).

edited Jan 13, 2015 at 17:23

answered Jan 13, 2015 at 17:17

Holger

301k43 gold badges481 silver badges827 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Abhijit Sarkar Over a year ago

Thanks for your response. I'm not sure if the question is with printing only. If the overflow value is returned and to be used in some other operation, it's going to be incorrect. The "exact" operations that have been introduced in Java 8, intValueExact throw exceptions in such cases.

Holger Over a year ago

Since the exercise mandates the use of int for calculations, there is no way around it. Of course, you may define the API of your calculation in a safe way, i.e. you can use Integer.toUnsignedLong to return the value (which you calculated using int) in a form which can’t be misinterpreted. Of course, the same would hold if you returned the result as String using toUnsignedString “calculation” != “return type”

Abhijit Sarkar Over a year ago

I was hoping that there's more to it than that. If you read the question, it says "using int values and unsigned operations". If seems beyond trivial to create a method that uses the + operator to add 2 ints. The exercise doesn't add any value unless we're missing something.

Holger Over a year ago

Maybe you should focus on the last sentence of your exercise: “Show why divideUnsigned and remainderUnsigned are necessary”. This implies that you should dig deep enough into the 2’s Complement to understand why it works for +, -, and * but not for / and % so you will understand the API design decision made for Java 8 to add these two support methods but no addUnsigned, etc.

Steve K · Accepted Answer · 2015-01-14 03:07:22Z

In order to obtain an unsigned int, you need to use the Integer.parseUnsignedInt() functions or do a manual calculation. Remember, Java doesn't actually HAVE unsigned integers, Java8 just provides the ability to treat an int as unsigned in order to allow for a greater range of positive-number values.

According to the Java 8 Doc for the Integer class,

An unsigned integer maps the values usually associated with negative numbers to positive numbers larger than MAX_VALUE

So the conversion between an unsigned int and a signed one is that if the number is greater than or equal to zero AND less than or equal to Integer.MAX_VALUE, it remains the same. If it's greater than Integer.MAX_VALUE but still within the unsigned range, then to store it in an int, you need to add 2^31 to it, which will convert it to the correct value due to the way that addition overflow is defined as an operation. Overflow and underflow in addition of binary primitives like int just causes the counter to reset and continue counting.

int min = Integer.MIN_VALUE;            // -2147483648
int max = Integer.MAX_VALUE;            // 2147483647
int overByOne = Integer.MAX_VALUE + 1;  // -2147483648 : same as Integer.MIN_VALUE
int underByOne = Integer.MIN_VALUE - 1; // 2147483647 : same as Integer.MAX_VALUE

They exercise is just asking you to look at the Integer class and test out the various (new in Java8) methods for unsigned operations. Java does not have unsigned integer primitives, but an int value can be treated as unsigned for the purposes of certain new methods in the Integer class.

Collectives™ on Stack Overflow

Java 8 Unsigned Integer Addition and Potential Overflow

2 Answers 2

4 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related