Divide函数

Question

我需要用Jack语言编写divide函数。

我的代码是：

function int divide(int x, int y) {

    var int result;
    var boolean neg;

    let neg = false;
    if(((x>0) & (y<0)) | ((x<0) & (y>0))){
        let neg = true;
        let x = Math.abs(x);
        let y = Math.abs(y);
    }

    if (y>x){
        return 0;
    }

    let result = Math.divide(x, y+y);

     if ((x-(2*result*y)) < y) {

        if (neg){
            return -(result + result);
        } else {
            return (result + result);
        }
    } else {
        if (neg){
            return -(result + result + 1);
        } else {
            return (result + result + 1);
        }
    }
}

该算法是次优的，因为每个乘法运算还需要O(n)个加法和减法运算。

我可以计算乘积2*result*y而不需要任何乘法吗？

谢谢

Answer 1

这是一个(无签名的)恢复除法(x/y)的实现，我实际上不认识Jack，所以我不是百分之百确定

var int r;
let r = 0;
var int i;
let i = 0;
while (i < 16)
{
    let r = r + r;
    if ((x & 0x8000) = 0x8000) {
        let r = r + 1;
    }
    if ((y ^ 0x8000) > (r ^ 0x8000)) {  // this is an unsigned comparison
        let x = x + x;
    }
    else {
        let r = r - y;
        let x = x + x + 1;
    }
    let i = i + 1;
}
return x;

您应该能够将其转换为带符号的除法。