Разделите 2 числа без использования /, * или% - PullRequest
Новая
       10

Разделите 2 числа без использования /, * или%

1 голос
/ 27 марта 2020

Допустим, мы предполагаем, что a = 16 b = 3

  • Сначала я пытаюсь найти x, на которое, когда я умножу 3, а затем вычту из 16, получим минимальную разницу
  • 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, в то время как l oop не удастся
  • res = 4 и a станет 4
  • Теперь снова, пока l oop запустится
  • 4-3 << 0 => 4- (3 * 1) - 4-3 << 1 => 4- (3 * 2)
  • при x = 1, в то время как l oop не удастся
  • res = 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;

    }
}

1 Ответ

0 голосов
/ 27 марта 2020

Одним из способов упростить программу будет поиск x только один раз, а затем уменьшение x на 1 каждые l oop: 

    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;

    }
...