java - 不使用 / ,* 或 % 将 2 个数字相除

Question

假设我们假设 a=16 b=3

• 首先，我试图找到当我乘以 3 然后从 16 减去时得到的 x 将得到最小差异
• 16-3<<0 =>16-(3*1) -- 16-3<<1 =>16-(3*2) -- 16-3<<2 =>16-(3*4) - - 16-3<<3 =>16-(3*8)
• 在 x=3 while 循环将失败
• res = 4 和 a 将变为 4
• 现在再次while循环将开始
• 4-3<<0 =>4-(3*1) -- 4-3<<1 =>4-(3*2)
• 在 x=1 while 循环将失败
• 资源 = 4+1

请帮助我解决复杂性，因为我的时间限制已超过

public class Solution {
    public int divide(int dividend, int divisor) {

        if(dividend == Integer.MIN_VALUE && divisor == -1){
            return Integer.MAX_VALUE;
        }
        int a = Math.abs(dividend);
        int b = Math.abs(divisor);
        int res = 0;
        while(a - b >= 0){

            int x = 0;
            while( (a - (b << x)) >= 0){
                x++;
            }
            res += 1 << (x-1);
            a -= b << (x-1);
            // System.out.println(res+" "+x+" "+a);

        }
        return (dividend >= 0) == (divisor >= 0) ? res :-res;

    }
}

标签： javabit-manipulationdivide

Answer 1

简化程序的一种方法是x只搜索一次，然后x在每个循环中减少 1：

    public int divide(int dividend, int divisor) {

        if(dividend == Integer.MIN_VALUE && divisor == -1){
            return Integer.MAX_VALUE;
        }
        int a = Math.abs(dividend);
        int b = Math.abs(divisor);
        int res = 0;
        int x = 0;
        while(a - (b << x) >= 0) {
            x++;
        }
        x--;
        while(a >= b) {
            int c = a - (b << x);
            if(c >= 0) {
                res += 1 << x;
                a = c;
            }
            x--;
        }
        return (dividend >= 0) == (divisor >= 0) ? res :-res;

    }