使用位运算符除以0（模拟除以0）

Question

我们知道可以使用位运算符来除任意两个数。例如：

int result = 10 >> 1; //reult would be 5 as it's like dividing 10 by 2^1

有没有可能我们可以使用位操作将数字除以 0？

编辑 1： 如果我重新表述我的问题，我想实际将数字除以零并破坏我的机器。我该怎么做？

编辑 2： 让我们暂时忘记 Java。无论使用何种编程语言，机器都可以将数字除以 0 吗？

编辑 3： 由于实际上不可能做到这一点，有没有一种方法可以使用接近 0 的非常小的数字来模拟它？

另一个编辑：有人提到 CPU 硬件会阻止除以 0。我同意，没有直接的方法可以做到这一点。例如，让我们看一下这段代码：

i = 1;
while(0 * i != 10){
    i++;
}

我们假设 i 的最大值没有上限。在这种情况下，不会有编译器错误，CPU 也不会抵抗这种情况。现在，我希望我的机器找到与 0 相乘得到的结果（这显然永远不会发生）或者死于尝试。

所以，因为有一种方法可以做到这一点。如何通过直接操作位来实现？

最终编辑： 如何在不使用按位运算符的情况下在 Java 中执行二进制除法？（对不起，纯属自相矛盾）

注意：我试过用 0 模拟除法并发布了我的答案。但是，我正在寻找一种更快的方法。

Answer 1

不，没有，因为您只能使用右移除以 2 的幂。

Answer 2

你的要求是不可能的。

除以 0 在数学上是不可能的。这个概念根本不存在，所以没有办法模拟它。

如果你真的想做极限运算（除以 0+ 或 0-）那么仍然没有办法使用按位来做，因为它只允许你除以幂两个。

这里是一个仅使用按位运算除以 2 的幂的例子

10 >> 1 = 5

查看您发布的评论，如果您只是想在用户尝试除以 0 时退出您的程序，您可以简单地验证它：

if(dividant == 0)
    System.exit(/*Enter here the exit code*/);

这样你就可以避免 ArithmeticException。

在与您交换了一些意见后，您似乎想做的是使操作系统崩溃除以 0。

不幸的是，据我所知，任何可以在计算机上编写的语言都经过验证足以处理除以 0。

想想一个简单的计算器，你支付 1 美元，尝试除以 0，它甚至不会崩溃，它只会抛出一条错误消息。无论如何，这可能在处理器级别得到验证。

编辑

在对你的问题多次 edits/comments 之后，你似乎正在尝试检索除以 0+ 或 0- 的 Infinity这是 0 的条款。

您可以通过 double/float 除法来实现。

System.out.println(1.0f / 0.0f);//prints infinity
System.out.println(1.0f / -0.0f);//prints -Infinity
System.out.println(1.0d / 0.0d);//prints infinity
System.out.println(1.0d / -0.0d);//prints -Infinity

请注意，即使你写0.0，这个值也不是真的等于0，它只是非常接近它。

Answer 3

一种模拟无符号整数除法（不考虑使用的除数）的方法是通过重复减法除法：

BigInteger result = new BigInteger("0");
int divisor = 0;
int dividend = 2;

while(dividend >=  divisor){

    dividend = dividend - divisor;              
    result = result.add(BigInteger.ONE);            

}

第二种方法是使用 Restoring Division 算法（感谢@harold），它比第一种算法快得多：

int num = 10;
BigInteger den = new BigInteger("0");
BigInteger p = new BigInteger(new Integer(num).toString());
int n = 2048; //Can be changed to find the biggest possible number (i.e. upto 2^2147483647 - 1). Currently it shows 2^2048 - 1 as output 
den = den.shiftLeft(n);

BigInteger q = new BigInteger("0");

for(int i = n; i > 0; i -= 1){
    q = q.shiftLeft(1);
    p = p.multiply(new BigInteger("2"));
    p = p.subtract(den);

    if(p.compareTo(new BigInteger("0")) == 1 
        || p.compareTo(new BigInteger("0")) == 0){
        q = q.add(new BigInteger("1"));
    } else {
        p = p.add(den);
    }
}

System.out.println(q);

Answer 4

如果你想要一个比division by repeated subtraction (which you posted), and that will run indefinitely when you try to divide by zero, you can implement your own version of the Goldschmidt division更快的除法方法，并且当除数为零时不抛出错误。

算法是这样工作的：

1. Create an estimate for the factor f
2. Multiply both the dividend and the divisor by f
3. If the divisor is close enough to 1
    Return the dividend
4. Else
    Go back to step 1

通常情况下，我们需要在开始之前缩小被除数和除数，这样 0 < divisor < 1 就可以满足了。在这种情况下，因为我们要除以零，所以不需要这一步。我们还需要选择一个任意精度，超出这个精度我们认为结果足够好。

不检查 divisor == 0 的代码如下所示：

static double goldschmidt(double dividend, double divisor) {
    double epsilon = 0.0000001;
    while (Math.abs(1.0 - divisor) > epsilon) {
        double f = 2.0 - divisor;
        dividend *= f;
        divisor *= f;
    }
    return dividend;
}

这比重复减法除法快得多，因为它以二次方式而不是线性方式收敛到结果。除以零时，这并不重要，因为这两种方法都不会收敛。但是如果你试着除以一个小数，比如10^(-9)，你可以清楚地看到差异。

如果不想让代码运行无限，而是returnInfinity除以零时，可以修改为 dividend 达到 Infinity:

时停止

static double goldschmidt(double dividend, double divisor) {
    double epsilon = 0.0000001;
    while (Math.abs(1.0 - divisor) > 0.0000001 && !Double.isInfinite(dividend)) {
        double f = 2.0 - divisor;
        dividend *= f;
        divisor *= f;
    }
    return dividend;
}

如果 dividend 和 divisor 的起始值是 dividend >= 1.0 和 divisor == 0.0，您将得到 Infinity 作为之后的结果，在大多数 2^10 次迭代。那是因为最坏的情况是 dividend == 1 你需要将它乘以二 (f = 2.0 - 0.0) 1024 次才能得到 2^1024，它大于 Double.MAX_VALUE.

Goldschmidt 部门是在 AMD 速龙 CPU 中实现的。如果您想了解一些较低级别的详细信息，可以查看这篇文章：浮点除法和平方根算法及实现在 AMD-K7 TM值微处理器.

编辑：

处理您的意见：

请注意，您发布的 Restoring Division 方法的代码迭代了 2048 (2^11) 次。我将您代码中 n 的值降低为 1024，因此我们可以比较两种方法执行相同的迭代次数。

我运行两个实现都用 dividend == 1 执行了 100000 次，这对 Goldschmidt 来说是最坏的情况，并且这样测量运行ning 时间：

long begin = System.nanoTime();
for (int i = 0; i < 100000; i++) {
    goldschmidt(1.0, 0.0); // changed this for restoringDivision(1) to test your code
}
long end = System.nanoTime();
System.out.println(TimeUnit.NANOSECONDS.toMillis(end - begin) + "ms");

运行Goldschmidt 部门的宁时间约为 290 毫秒，您的代码的宁时间约为 23000 毫秒（23 秒）。因此，此实施在此测试中 80 倍快 。这是预料之中的，因为在一种情况下我们正在做 double 乘法，而在另一种情况下我们正在使用 BigInteger.

您实施的优点在于，由于您使用的是 BigInteger，因此您可以使结果与 BigInteger 支持的一样大，而此处的结果受限于 Double.MAX_VALUE .

实际上，在除以零时，Goldschmidt 除法会在每次迭代中将被除数加倍，这相当于左移，直到达到最大可能值。所以使用 BigInteger 的等价物是：

static BigInteger divideByZero(int dividend) {
    return BigInteger.valueOf(dividend)
                     .shiftLeft(Integer.MAX_VALUE - 1 - ceilLog2(dividend));
}

static int ceilLog2(int n) {
    return (int) Math.ceil(Math.log(n) / Math.log(2));
}

函数ceilLog2()是必须的，这样shiftLeft()就不会造成溢出。根据您分配的内存量，这可能会导致 java.lang.OutOfMemoryError: Java heap space 异常。所以这里要做出妥协：

您可以非常快地将除法模拟达到运行，但结果上限为 Double.MAX_VALUE，

或

您可以获得与 2^(Integer.MAX_VALUE - 1) 一样大的结果，但达到该限制可能需要太多内存和时间。

编辑 2：

处理您的新评论：

Please note that no division is happening in your updated code. It's just trying to find the biggest possible BigInteger

首先，让我们证明当 divisor == 0:

时，Goldschmidt 划分退化为左移

static double goldschmidt(double dividend, double divisor) {
    double epsilon = 0.0000001;
    while (Math.abs(1.0 - 0.0) > 0.0000001 && !Double.isInfinite(dividend)) {
        double f = 2.0 - 0.0;
        dividend *= f;
        divisor = 0.0 * f;
    }
    return dividend;
}

因数 f 将始终等于 2.0，并且第一个 while 条件将始终为真。所以如果我们消除冗余：

static double goldschmidt(double dividend, 0) {
    while (!Double.isInfinite(dividend)) {
        dividend *= 2.0;
    }
    return dividend;
}

假设dividend是一个Integer，我们可以使用左移来做同样的乘法：

static int goldschmidt(int dividend) {
    while (...) {
        dividend = dividend << 1;
    }
    return dividend;
}

如果我们能达到的最大值是2^n，我们需要循环n次。当dividend == 1时，这相当于：

static int goldschmidt(int dividend) {
    return 1 << n;
}

当dividend > 1时，我们需要减去ceil(log2(dividend))以防止溢出：

static int goldschmidt(int dividend) {
    return dividend << (n - ceil(log2(dividend));
}

因此表明如果 divisor == 0.

Goldschmidt 除法等同于左移

However, shifting the bits to the left would pad bits on the right with 0. Try running this with a small dividend and left shift it (once or twice to check the results). This thing will never get to 2^(Integer.MAX_VALUE - 1).

现在我们已经看到 n 左移等同于 2^n 的乘法，让我们看看 BigInteger 版本是如何工作的。考虑以下示例，如果有足够的可用内存并且股息是 2 的幂，我们将达到 2^(Integer.MAX_VALUE - 1)：

对于dividend = 1

BigInteger.valueOf(dividend).shiftLeft(Integer.MAX_VALUE - 1 - ceilLog2(dividend))
= BigInteger.valueOf(1).shiftLeft(Integer.MAX_VALUE - 1 - 0)
= 1 * 2^(Integer.MAX_VALUE - 1)
= 2^(Integer.MAX_VALUE - 1)

对于dividend = 1024

BigInteger.valueOf(dividend).shiftLeft(Integer.MAX_VALUE - 1 - ceilLog2(dividend))
= BigInteger.valueOf(1024).shiftLeft(Integer.MAX_VALUE - 1 - 10)
= 1024 * 2^(Integer.MAX_VALUE - 1)
= 2^10 * 2^(Integer.MAX_VALUE - 1 - 10)
= 2^(Integer.MAX_VALUE - 1)

如果 dividend 不是 2 的幂，我们将通过将 dividend.

重复加倍来尽可能接近 2^(Integer.MAX_VALUE - 1)

Answer 5

正如其他人指出的那样，您不能在数学上除以 0。

但是，如果您想要除以 0 的方法，可以使用 Double 中的一些常量。例如你可以有一个方法

public static double divide(double a, double b){
    return b == 0 ? Double.NaN : a/b;
}

或

public static double posLimitDivide(double a, double b){
    if(a == 0 && b == 0)
        return Double.NaN;
    return b == 0 ? (a > 0 ? Double.POSITIVE_INFINITY : Double.NEGATIVE_INFINITY) : a/b;

这将 return a/x 的极限，其中 x 接近 +b。

这些应该没问题，只要你在任何使用它们的方法中考虑到它。好的，我的意思是不好，如果你不小心的话，以后可能会导致不确定的行为。但这是一种用实际值而不是异常来指示结果的明确方法。

使用位运算符除以0（模拟除以0）

Using bitwise operator to divide by 0 (Simulation of division by 0)

java

bitwise-operators