Java 无符号除法无需强制转换为 long？

Question

我编写了一个解释器，要求我执行无符号整数的 32 位除法。在 Java 中，我可以这样做：

reg[a] = (int) ((reg[b] & 0xFFFFFFFFL) / (reg[c] & 0xFFFFFFFFL));

但我想避免转换为 long 并返回 int。 Java 已经为这种特殊情况提供了无符号右移运算符

>>>

，因此也许有一种聪明的方法可以以相同的方式进行无符号除法。

请注意，加法和乘法工作正常，因为两个补数都可以工作。

Java 有更好的方法来做到这一点吗？

Answer 1

在 Java 8 及更高版本中，

Integer

对无符号

int

s

具有完整的操作集合

reg[a] = Integer.divideUnsigned(reg[b], reg[c]);

Answer 2

好吧，如果你向下移动一位，你可以将所得的两个数字相除，然后向上移动两次（因为所得的数字会小 4 倍）。但这仅适用于偶数，因为您会丢失最低有效位。

我真的不认为这会节省您检查这种情况的时间。 （或检查小于 2³¹ 的数字）

Answer 3

您始终可以使用

BigInteger

，它适用于任意大小的整数，但这比升级为

long

并转换回

int

要昂贵得多。您的目的是提高性能（因此您需要一个“纯整数”解决方案来避免转换时间）还是提高代码的可读性/可理解性（在这种情况下 BigInteger 可能更简洁）？

Answer 4

其他人提到了简单且明确正确的方法，例如转换为

long

，或使用

Integer.divideUnsigned()

（Java SE 8+），或使用

BigInteger

。

实际上来说，

Integer.divideUnsigned()

是最清晰、最高效的方法，因为 JVM 可能会将此函数调用内化到本机无符号除法机器指令中，使其运行速度与语言级有符号除法运算符一样快

 /

。

但为了完整起见，这里介绍如何以相对有效的方式在纯 Java（无 C 或汇编）中模拟

uint32 / uint32

，不使用更广泛的类型，如

long

或

BigInteger

：

int divideUint32(int x, int y) {
    if (y < 0) {  // i.e. 2^31 <= unsigned y < 2^32
        // Do unsigned comparison
        return (x ^ 0x8000_0000) >= (y ^ 0x8000_0000) ? 1 : 0;
    }
    else if (x >= 0 || y == 0) {
        assert y >= 0;
        return x / y;  // Straightforward or division by zero
    }
    else {  // The hard case: signed x < 0 && signed y > 0
        assert x < 0 && y > 0;
        // In other words, 2^31 <= unsigned x < 2^32 && 0 < unsigned y < 2^31
        int shift = Integer.numberOfLeadingZeros(y);
        assert shift > 0;
        assert (y << shift) < 0;
        // Do one step of long division
        if (x < (y << shift))
            shift--;
        return (1 << shift) | (x - (y << shift)) / y;
    }
}

我已经在整个

int

值范围内检查了数百万个随机测试用例的代码。如果有人想知道如何调整代码以与

long

一起使用，通过遵循逻辑中的隐式模式很容易做到这一点。