使用按位运算符除以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模拟divison并发布了我的答案.但是,我正在寻找一种更快的方法.

Answer 1

如果你想要的是一个除法方法比通过重复减法(你发布的)除法更快,并且当你试图除以零时无限期地运行,你可以实现你自己的Goldschmidt除法版本,而不是在抛出错误时除数为零.

该算法的工作方式如下:

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),你可以清楚地看到差异.

如果您不希望代码无限期地运行,但是Infinity在除以零时返回,则可以将其修改为在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.01024 ()1024倍才能得到2^1024,这大于Double.MAX_VALUE.

Goldschmidt部门在AMD Athlon CPU中实施.如果您想了解一些较低级别的详细信息,可以查看本文: AMD-K7 TM微处理器中的浮点分区和平方根算法和实现.

编辑:

处理你的意见:

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

我运行了两次实现100000次dividend == 1,这是Goldschmidt最糟糕的情况,并测量了这样的运行时间:

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:

处理你的新评论:

请注意,您的更新代码中没有进行任何划分.它只是试图找到最大可能的BigInteger

首先,让我们表明Goldschmidt部门在以下情况下退化为左移divisor == 0:

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是a 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));
}

因此显示Goldschmidt分部相当于左移如果divisor == 0.

但是,将位向左移位会将右边的位填充为0.尝试使用小分红运行此操作并左移(一次或两次以检查结果).这件事永远不会发生2^(Integer.MAX_VALUE - 1).

现在我们已经看到左移n相当于乘以2^n,让我们看看BigInteger版本是如何工作的.考虑以下示例,显示2^(Integer.MAX_VALUE - 1)如果有足够的可用内存并且被除数是2的幂,我们将会得到:

对于 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的幂,我们将2^(Integer.MAX_VALUE - 1)通过反复加倍来尽可能接近dividend.