Java无符号除法是否需要转换为long类型？

Question

我已经编写了一个解释器，需要对无符号整数进行32位除法计算。在Java中，我可以这样做：

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

但我希望避免将数字转换为长整型再转回整型。Java已经为这种特殊情况提供了无符号右移运算符>>>，因此可能有一种聪明的方法来进行无符号除法。

请注意，加法和乘法运算正常工作，因为补码数字可以直接使用。

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

- Adam Goode

Answer 1

在Java 8及以上版本中，Integer提供了许多操作无符号int的方法。

reg[a] = <a rel="nofollow noreferrer" href="https://docs.oracle.com/javase/8/docs/api/java/lang/Integer.html#divideUnsigned-int-int-">Integer.divideUnsigned</a>(reg[b], reg[c]);

- HTNW

---

如果JVM的实现者做得好，这个函数调用将被内置为本地无符号除法机器指令 - 这意味着没有开销，并且可能与有符号除法一样快。 - Nayuki

Answer 2

如果您将数字向下移动一位，那么您可以将两个结果数字相除，然后再向上移动两次（因为结果数字会变小4倍）。但是这仅适用于偶数，因为您将失去最低有效位。

我真的不认为检查该条件（或检查小于2³¹的数字）会节省您任何时间。

- Chad Okere

Answer 3

你可以一直使用BigInteger，它适用于任意大小的整数，但这比提升为long并将其转换回int要昂贵得多。您的意图是为了提高性能（因此您希望使用“纯整数”解决方案以避免强制转换的时间），还是为了改善代码的可读性/理解性（在这种情况下，BigInteger可能更整洁）？

- Ash

Answer 4

其他人已经提到了一些简单而明确的方法，比如将其转换为long，或使用{{link1：Integer.divideUnsigned()}}（Java SE 8+），或使用{{link2：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，只需按照逻辑中的隐式模式进行简单的修改即可。

- Nayuki