user1111929 - 1 year ago 68
Java Question

# high bits of long multiplication in Java?

Is there any way to get the high half of the multiplication of two

`long`
s in Java? I.e. the part that vanishes due to overflow. (So the upper 64 bits of the 128-bit result)

I'm used to writing OpenCL code where the command
`mul_hi`
does exactly this: http://www.khronos.org/registry/cl/sdk/1.0/docs/man/xhtml/mul_hi.html

Since OpenCL can do it efficiently on my CPU, Java should be able to do so as well, but I can't find how I should do this (or even mimic its behaviour efficiently) in Java. Is this possible in Java, and if so, how?

The accepted solution is wrong most of the time (66%), though the error is bounded (it can be smaller than the exact result by at most 2 and it can never be bigger). This comes from

• ignoring the `x_lo * y_lo` product
• first shifting and then adding `x_hi * y_lo` and `x_lo * y_hi`

My solution seems to always work for non-negative operands.

``````final long x_hi = x >>> 32;
final long y_hi = y >>> 32;
final long x_lo = x & 0xFFFFFFFFL;
final long y_lo = y & 0xFFFFFFFFL;
long result = x_lo * y_lo;
result >>>= 32;

result += x_hi * y_lo + x_lo * y_hi;
result >>>= 32;
result += x_hi * y_hi;
``````

Tested on a billion random operands. There should be a special test for corner cases and some analysis.

Dealing with negative operands would be more complicated as it'd prohibit using the unsigned shift and force us to handle intermediate result overflow.

In case speed doesn't matter much (and it rarely does), I'd go for

`````` BigInteger.valueOf(x).multiply(BigInteger.valueOf(y))
.shiftRight(64).longValue();
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download