Java长乘法的高位? [英] high bits of long multiplication in Java?

问题描述

在Java中，有什么方法可以得到两个long的乘积的上半部分吗? IE.由于溢出而消失的部分. (因此128位结果的高64位)

Is there any way to get the high half of the multiplication of two longs in Java? I.e. the part that vanishes due to overflow. (So the upper 64 bits of the 128-bit result)

我习惯于在命令mul_hi执行此操作的情况下编写OpenCL代码:

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

由于OpenCL可以在我的CPU上有效地完成此操作，因此Java应该也可以做到这一点，但是我找不到如何在Java中执行该操作(甚至有效地模仿其行为)的方法.用Java可以做到吗?如果可以，怎么办?

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?

推荐答案

尽管误差是有限的(大多数情况下，误差比准确结果小2，并且误差最大，但可接受的误差在大多数情况下是错误的(66％))它永远不可能更大).来自

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

• 忽略x_lo * y_lo产品
• 先移动然后再添加x_hi * y_lo和x_lo * y_hi

• 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();

这篇关于Java长乘法的高位?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！