1

I want to add two shorts as if they are unsigned and get the carry bit from the addition.

So for example, the following shorts represented in binary

1111111111111111 (-1) +
0000000000000001 (1)
----------------
0000000000000000 (0)

Their addition has the carry bit of 1.

Is there a way to obtain this carry bit from two's compliment addition?

The only restriction to any solution is that the following data types cannot be used: int, long, char because I'm working on the Java Card platform

UPDATE:

The reason I need this is to re-create integer addition with two shorts. I am working with the Java Card platform, which doesn't support integers, hence I wanted to use two shorts to represent one integer.

WJS's answer was perfect for what I needed. The following code block illustrates what I wanted to create:

short xA = (short) 0b1111111111111111, xB = (short) 0b1111111111111111;
short yA = (short) 0b0000000000000000, yB = (short) 0b0000000000000001;
short targetA, targetB;

targetA = (short) (xA + yA + (xB < 0 && yB < 0 || xB < 0 && yB >= -xB || yB < 0 && xB >= -yB ? 1 : 0));
targetB = (short) (xB + yB);

Where A is the high part and B is the low part of the integer.

This code block is the short equivalent of target = x + y.

GeekOverdose
  • 325
  • 2
  • 10
  • I didn't understand the question! Why -1+1 carry is 1 – 时间只会一直走 Nov 10 '22 at 02:31
  • @时间只会一直走 The O/P wants to treat the numbers as if they are unsigned. – Old Dog Programmer Nov 10 '22 at 02:33
  • I don't know anything about `javacard`, or why it would restrict use of `long` or `char`. But, what about using [Integer](https://docs.oracle.com/javase/7/docs/api/java/lang/Integer.html) or [Short](https://docs.oracle.com/javase/7/docs/api/java/lang/Short.html), either objects of those types or static methods of those classes? – Old Dog Programmer Nov 10 '22 at 02:36
  • 2
    you’ll probably have to do the same as this question about longs : https://stackoverflow.com/questions/24331636/check-carry-from-long-operation-in-java – racraman Nov 10 '22 at 02:54
  • You might want to have a look [here](https://github.com/OpenCryptoProject/JCMathLib/blob/e81b6ba441024f6d592b31bc58f8820e6e3d959d/JCMathLib/src/opencrypto/jcmathlib/Bignat.java#L1117). Good luck with your project! – vlp Nov 10 '22 at 07:25
  • 1
    @时间只会一直走 because in Java, negatives such as -1 are represented in two's complement form. So when doing `(-1) + (1)` they actually add `0b1111111111111111` and `0b0000000000000001` like it is regular binary. If you do this addition on paper, you'll get `0` carry `1`. At least that is my understanding of it – GeekOverdose Nov 10 '22 at 10:18

2 Answers2

4

You can do it like this. A carry will occur if.

  • a and b are both negative
  • a is negative and b >= -a
  • b is negative and a >= -b
short a = some short;
short b = some short;
short carry = getCarry(a, b);

public static short getCarry(short a, short b) {
    if (a < 0 && b < 0 || a < 0 && b >= -a || b < 0 && a >= -b) {
          return 1;
    }
    return 0;
}

I tested this by comparing this carry to the one that would cascade into the upper 16 bits of an integer after addition of two shorts. In all cases, the two carry bits were equal.

WJS
  • 36,363
  • 4
  • 24
  • 39
  • 3
    yeah, mate this works for what I needed this for. I did further testing, and it still works after 1 billion random number iterations. Thanks a lot! – GeekOverdose Nov 10 '22 at 10:19
0

You just compare the result of the addition with the original number.

public static void main(String[] args) {
    short a = -1;
    short b = 1;
    short sum = (short)(a + b);
    int carry = Short.compareUnsigned(sum, a) < 0 ? 1 : 0;
    System.out.printf("sum = %d carry = %d%n", sum, carry);
}

output:

sum = 0 carry = 1

If you don't have Short.compareUnsigned() you can use the following alternative. See Calculating Carry Flag - Stack Overflow

static boolean unsignedLessThan(short a, short b) {
    return (a ^ Short.MIN_VALUE) < (b ^ Short.MIN_VALUE);
}