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

Question

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

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

但我想避免转换为 long 并返回 int。 Java 已经为这种特殊情况提供了无符号右移运算符 >>>，因此也许有一种聪明的方法可以以相同的方式进行无符号除法。

请注意，加法和乘法可以正常工作，因为二进制的补数可以正常工作。

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

Answer 1

在 Java 8 及更高版本中，Integer 具有对无符号 int 进行操作的完整集合

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，不使用更广泛的类型，如 < code>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，通过遵循逻辑中的隐式模式很容易做到这一点。