5

I'm adding/subtrating to numbers of type long. Is there a way to figure out if a theoretical carry would be set by this operation?

kaetzacoatl
  • 1,419
  • 1
  • 19
  • 27
  • What is a theoretical carry? – Thomas Uhrig Jun 20 '14 at 16:22
  • @ThomasUhrig "theoretical" here probably is meant to mean: "theoretically, IF i were to add these numbers, would there be a carry". As in: Without doing the actual math, what would the carry be? – Markus A. Jun 20 '14 at 16:24

2 Answers2

4

This should do:

/**
 * Add two long's with overflow detection (r = s + d)
 */
public static long add(final long s, final long d){
    final long r = s + d;
    if (((s & d & ~r) | (~s & ~d & r)) < 0)
        throw new RuntimeException("long overflow add(" + s + ", " + d + ")");
    return r;
}

This has been asked before here: How does Java handle integer underflows and overflows and how would you check for it? (Subtraction is also described there)

Edit: Since its not clear if the OP meant unsigned addition, thats also not too hard to detect. If one rethinks the problem as "if we had two (unsigned) 64 bit values and would add them, would bit 64 be set in the result (assuming bits are numbered from 0=LSB to 63=MSB in the original operands)"

A little logical thinking leads to the conclusion that bit 64 would be set if more than one of the following conditions is true:

  • bit 63 of operand1 is set
  • bit 63 of operand2 is set
  • the sum of the lower bits (0-62) of both operands produces a carry to bit 63

Thats reasonably easy to check:

long operand1 = ...
long operand2 = ...
long bitMask = Long.MAX_VALUE; // bits 0-62 set, bit 63 clear
int conditions = 0;
if (operand1 < 0)
    ++conditions; 
if (operand2 < 0)
    ++conditions;
if (((operand1 & bitMask) + (operand2 & bitMask)) < 0)
    ++conditions;
if (conditions > 1)
    System.out.println("carry would be set!");

I havent spent any time on thinking how that could be optimized, I'm sure there is a more concise solution.

For unsigned subtraction its pretty simple: A borrow occurs in (a - b) if b is greater than a. That can be checked with unsigned comparison, which could be expressed in java as:

long flipSignBit = Long.MIN_VALUE; // only bit 63 set, others clear
if ((a ^ flipSignBit) < (b ^ flipSignBit))
    System.out.println("borrow occurs");
Community
  • 1
  • 1
Durandal
  • 19,919
  • 4
  • 36
  • 70
1

From Java Language Specification (Java SE 8) The integer operators do not indicate overflow or underflow in any way. So you have to test yourself :

  • sum of two positive number and negative result => overflow
  • sum of two negative number and positive result => underflow
  • sum of a positive and a negative can't neither overflow nor underflow
  • rule for sub : a - b = a + (-b)

This is ok as long as you test at each operation between to numbers.

Serge Ballesta
  • 143,923
  • 11
  • 122
  • 252
  • Here's this answer in code: `a<0 ? (b<0 ? a+b>=0 : false) : (b>0 ? a+b<0 : false)` – Markus A. Jun 20 '14 at 16:39
  • My answer is more adapted for understanding how it works, but I must say that the algorithm given by Durandal is more optimized because bit operations are fast and there is one single test. – Serge Ballesta Jun 20 '14 at 16:46
  • @SergeBallesta are you sure the question is about integer overflow? Isn't a carry when you add 9 + 3, then the carry is 1 and you get 12? Hard to explain, see here: http://en.wikipedia.org/wiki/Carry_(arithmetic) – Thomas Uhrig Jun 20 '14 at 16:56
  • @SergeBallesta your method works for overflow but not for carry. – kaetzacoatl Jun 20 '14 at 17:00
  • @ThomasUhrig I saw the wikipedia article on Carry. You are speaking of *decimal arithmetic carry* or *manual carry* with decimal digits, when I speak of *carry flag* described later in same article under *Computing*. It was very used with 8 bit computers (who remembers the ancestral 8080, the ZX80 from the Sinclair ZX80 or the 6502 form the Apple II ...) where nearly all integer operations went through carry. – Serge Ballesta Jun 20 '14 at 17:17
  • @kaetzacoatl Overflow indicates the value overflowed the value range of the type - that is the equivalent of a set carry flag. The classical *carry* is more associated with *unsigned* math. But since java works with signed types most readers (including me) will draw the conclusion you're asking about *signed* math. If you want unsigned, make that explicitly clear, the context in which you're asking implies signed for most of us. – Durandal Jun 20 '14 at 17:39
  • Shouldn't that be `add of two …`? (and `can't`) (or, instead of _add_, _addition_ or _sum_) – greybeard Feb 05 '16 at 20:24