java - 二进制长除法算法

Question

我一直在尝试在 java 中重新创建以下算法:

Set quotient to 0
Align leftmost digits in dividend and divisor
Repeat
If that portion of the dividend above the divisor is greater than or equal to the divisor
Then subtract divisor from that portion of the dividend and
Concatentate 1 to the right hand end of the quotient
Else concatentate 0 to the right hand end of the quotient
Shift the divisor one place right
Until dividend is less than the divisor
quotient is correct, dividend is remainder
STOP

这也可以在这里找到:

这是我的代码:

public class Division {
    public static void main(String[] args) {
        int quotient =0;
        int a = 123;
        int b = 5;
        int bfirst = b;
        String a1 = Integer.toBinaryString(a);
        String b1 = Integer.toBinaryString(b);
        int aLength = a1.length();
        int bLength = b1.length();
        int power = aLength - bLength;
        b =(int) Math.pow(b, power);    

        while(a > bfirst) {
            if(a >= b) {
                a = a-b;
                quotient = quotient*2+1;
                b = b/2;
            } else {
                quotient = quotient*2;
                b = b/2;
            }
        }
        System.out.println(quotient);
    }
}

它有时会返回正确的答案，但有时不会。有什么想法吗？

Answer 1

我相信

b = (int) Math.pow(b, power);    

应该是

b = (int) (b * Math.pow(2, power));

变量b似乎是要与之比较的当前数字，并被减去 a .您正在进行二进制除法，并且在这一行之后的代码中，我发现该值仅除以 2。在本例中，Math.pow(b, power)没有意义。

---

此外，还缺少一个步骤。因为a - b将把所有的值都放到最后得到 a < bFirst ，所有结尾的零都不计入商，因为我们已经退出了循环。

替换

a = a-b;
quotient = quotient*2+1;
b = b/2;

与

bLength = Integer.toBinaryString(b).length();
int bfirstLength = Integer.toBinaryString(bfirst).length();
a = a-b;
quotient = quotient*2+1;
b = b/2;
if (a < bfirst) {
    quotient = quotient * (int)Math.pow(2, bLength - bfirstLength);
}

考虑到商的缺失零点。

---

此外还有一个差一错误。

while (a > bfirst) {

应该是

while (a >= bfirst) {

如果a可以被 b 整除, 长除法应该继续减去剩余的红利，而不是停止程序。

---

最后，一个数的二进制位数可以通过以下方式计算

(int) (Math.ln(a) / Math.ln(2)) + 1

---

最后，尝试利用System.out.println调试时在你的算法内部，它有很大帮助，让你准确地知道你的算法哪里出了问题。更好的是，如果您知道如何使用并且可用(通常集成到 IDE 中)，请使用调试器。

最后一个，在编码之前用一些示例手工完成算法 - 这绝对可以帮助您理解算法的工作原理。

整个东西，带有调试语句:http://ideone.com/JBzHdf