java - 恢复除法算法实现

Question

我正在尝试实现 Restoring Division算法和事情变得非常错误。这是我的代码:

public static void main(String[] args){

    int num = 10;
    long den = 2;
    long p = num;
    int n = 32;
    den = den << n;
    StringBuilder s = new StringBuilder("");
    long q = 0;
    for(int i = n; n > 0; n--){

        p = (2 * p) - den;
        if(s.length() > 0){
            s.delete(0, s.length() - 1);                
        }
        s.append(Long.toString(q,2));

        if(p >= 0){
            s.setCharAt(i, '1');
        }else{  
            s.setCharAt(i, '0');
        }

        q = Integer.parseInt(s.toString(), 2);
    }
    System.out.println(q);
}

我收到 java.lang.StringIndexOutOfBoundsException: String index out of range: 32 异常。这是因为我试图在一个不存在的位置设置一个字符(或有点技术性)。

如何正确实现？我可以获得带前导零的二进制字符串吗？

Answer 1

很奇怪你会涉及任何String就在这样一个过程中。您正在使用二进制算术，因此请使用整数数据类型和运算符，尤其是按位运算符( & 、 | 、 ^ 、 << 、 >> 、 >>> )。每个整数数据类型都实现一个“带前导零的二进制字符串”。特别是对于这种情况，给定恢复除法算法的约束，即输入均为正。

我可能会这样写中心部分:

q = 0;
for(int i = 32; i > 0; i -= 1){
    q <<= 1;
    p = (2 * p) - den;

    if(p >= 0){
        q += 1;
    } else {
        // implicit: q += 0
        p += den;
    }
}

请注意，每次迭代操作的是位 0。之前的部分结果(第一次迭代时为 0)左移一位以腾出空间，这样在所有 32 次迭代之后，每个位都在正确的位置。