Деление без использования «/»

Question

Может кто-нибудь сказать мне эффективный подход к выполнению операции деления без использования '/'.Я могу вычислить целочисленное значение с шагом log(n), используя метод, аналогичный бинарному поиску.

115/3 
57 * 3 > 115
28 * 3 < 115
47 * 3 > 115
.
.
.
38 * 3 is quotient value .....

Но есть ли другой более эффективный метод?

Answer 1

Типичным способом является сдвиг и вычитание.Это в основном очень похоже на длинное деление, как мы узнали в школе.Большая разница в том, что в десятичном делении вам нужно оценить следующую цифру результата.В двоичном коде это тривиально.Следующая цифра всегда либо 0, либо 1. Если делитель (смещенный влево) меньше или равен текущему значению дивиденда, вы вычитаете его, а текущий бит результата равен 1. Если он больше, тотекущий бит результата равен 0. Код выглядит следующим образом:

unsigned divide(unsigned dividend, unsigned divisor) { 

    unsigned denom=divisor;
    unsigned current = 1;
    unsigned answer=0;

    if ( denom > dividend) 
        return 0;

    if ( denom == dividend)
        return 1;

    while (denom <= dividend) {
        denom <<= 1;
        current <<= 1;
    }

    denom >>= 1;
    current >>= 1;

    while (current!=0) {
        if ( dividend >= denom) {
            dividend -= denom;
            answer |= current;
        }
        current >>= 1;
        denom >>= 1;
    }    
    return answer;
}

Это работает почти так же, как когда мы делаем длинное деление вручную.Например, давайте рассмотрим 972/5.В десятичном делении на длинные мы делаем что-то вроде этого:

 ____ 
5)972

Затем мы вычисляем каждую цифру отдельно.5 входит в 9 один раз, поэтому мы записываем 1 в этой цифре ответа и вычитаем 1 * 5 из (этой цифры) дивиденда, а затем "понижаем" следующую цифру дивиденда:

  1
 ----
5)972
  5
  ---
  47

Мы продолжаем делать то же самое, пока не введем все цифры:

   194
  ----
 5)972
   5
   ---
   47
   45
   ---
    22
    20
   ---
     2

Итак, наш ответ 194 остаток 2.

Теперь давайте рассмотрим то же самое,но в двоичном.972 в двоичном виде - 11 1100 1100, а 5 - 101.Теперь есть одно принципиальное различие между делением в двоичном и десятичном виде: в десятичной дроби конкретная цифра может быть от 0 до 9, поэтому нам пришлось умножить, чтобы найти промежуточный результат, который мы собирались вычесть из дивиденда.В двоичном виде цифра всегда будет 0 или 1. Нам никогда не нужно умножать, потому что мы умножаем только на 0 или 1 (что мы обычно обрабатываем в операторе if - либо мы вычитаем, либо нет).

   -----------
101)1111001100

Итак, наш первый шаг - выяснить, какая цифра будет первой в результате.Мы делаем это, сравнивая 101 с 1111001100 и сдвигая его влево, пока он не станет больше.Это дает нам:

  |
 1111001100
10100000000

По мере того, как мы делаем это смещение, мы подсчитываем количество смещенных мест, чтобы мы знали, какую цифру результата мы заполняем в любой момент времени.Я показал это с вертикальной чертой выше.Затем мы сдвигаем промежуточный результат вправо на одно место и сдвигаем вертикальную черту вправо с ним, чтобы указать, где мы делаем, чтобы заполнить цифру результата:

    |
  1111001100
  1010000000

Оттуда мы проверяем, является ли сдвинутый делительменьше дивидендов.Если это так, мы заполняем 1 в правильном месте в ответе и вычитаем сдвинутый делитель из промежуточного результата [и чтобы помочь сохранить столбцы прямыми, я собираюсь вставить несколько пробелов]:

        1  
     -----------------------------
  101)1  1  1  1  0  0  1  1  0  0
      1  0  1  0  0  0  0  0  0  0
      ----------------------------
      1  0  1

Мы продолжаем в том же духе, заполняя цифры результата и вычитая сдвинутый делитель из промежуточного результата, пока мы не заполним все цифры.В дальнейших попытках помочь разобраться, я собираюсь написать каждую цифру результата в крайнем правом углу рядом с вычитаемым:

            1  1  0  0  0  0  1  0
     -----------------------------
  101)1  1  1  1  0  0  1  1  0  0
      1  0  1                             1
      -----------------------------
         1  0  1
         1  0  1                           1
      -----------------------------
            0  0  0                          0
         --------------------------
               0  0  0                        0
          -------------------------
                  0  0  1                      0
          -------------------------
                     0  1  1                    0
          -------------------------
                        1  1  0   
                        1  0  1                   1
           ------------------------
                           0  1  0                 0

Итак, мы получаем результат 11000010, остаток10. Преобразовав их в десятичную, мы получаем ожидаемые 194 и 2. соответственно.

Давайте рассмотрим, как это относится к приведенному выше коду.Мы начинаем со смещения делителя влево, пока он не станет больше, чем дивиденд.Затем мы многократно сдвигаем его вправо и для каждого сдвига вправо проверяем, меньше ли это значение, чем промежуточное значение, которое мы получили после последнего вычитания.Если оно меньше, мы снова вычитаем и заполняем 1 для этой цифры в нашем результате.Если оно больше, мы «вычитаем 0» (ничего не делаем) и заполняем «0» для этой цифры в результате (что, опять же, не требует от нас ничего делать, поскольку эти цифры уже установлены в0's).

Когда мы заполнили все цифры, это наш результат, и любая оставшаяся сумма, которую мы еще не вычли, является нашим остатком.

Некоторые спрашивают, почему я использовал|= вместо += в коде.Я надеюсь, что это помогает объяснить, почему.Хотя в этом случае они дают одинаковый результат, я не думаю о добавлении каждой цифры к существующему частичному ответу.Скорее, я думаю, что это место в ответе пустое, и or просто заполняет его.

Answer 2

Параметры:

• Код вашего собственного алгоритма деления на основе алгоритма длинного деления, который вы выучили в начальной школе.
• Возьмите -1 в знаменателе и умножьте на числитель
• Возьмите бревна числителя и знаменателя, вычтите, а затем поднимите основание бревна до той же степени

Мне не особенно нравятся подобные вопросы, потому что мы в основном ищем глупые уловки, но мы здесь.

Answer 3

Простая реализация Python с использованием базовой математики средней школы. Знаменатель - это просто число в степени отрицания 1.

def divide(a, b):
    return a * b ** -1

Answer 4

Ниже приведен код Java для деления числа без использования оператора деления.

private static int binaryDivide(int dividend, int divisor) {
    int current = 1;
    int denom = divisor;
    // This step is required to find the biggest current number which can be
    // divided with the number safely.
    while (denom <= dividend) {
        current <<= 1;
        denom <<= 1;
    }
    // Since we may have increased the denomitor more than dividend
    // thus we need to go back one shift, and same would apply for current.
    denom >>= 1;
    current >>= 1;
    int answer = 0;
    // Now deal with the smaller number.
    while (current != 0) {
        if (dividend >= denom) {
            dividend -= denom;
            answer |= current;
        }
        current >>= 1;
        denom >>= 1;
    }
    return answer;
}

Answer 5

() Это решение проблемы, при которой вам не разрешено использовать умножение либо ).

Мне нравится это решение: https://stackoverflow.com/a/5387432/1008519,, но мне сложно рассуждать (особенно о | -части). Это решение имеет немного больше смысла в моей голове:

var divide = function (dividend, divisor) {
  // Handle 0 divisor
  if (divisor === 0) {
    return NaN;
  }

  // Handle negative numbers
  var isNegative = false;
  if (dividend < 0) {
    // Change sign
    dividend = ~dividend+1;
    isNegative = !isNegative;
  }

  if (divisor < 0) {
    // Change sign
    divisor = ~divisor+1;
    isNegative = !isNegative;
  }

  /**
   * Main algorithm
   */

  var result = 1;
  var denominator = divisor;
  // Double denominator value with bitwise shift until bigger than dividend
  while (dividend > denominator) {
    denominator <<= 1;
    result <<= 1;
  }

  // Subtract divisor value until denominator is smaller than dividend
  while (denominator > dividend) {
    denominator -= divisor;
    result -= 1;
  }

  // If one of dividend or divisor was negative, change sign of result
  if (isNegative) {
    result = ~result+1;
  }

  return result;
}

1. Инициализировать результат равным 1 (поскольку мы собираемся удвоить наш знаменатель, пока он не станет больше дивиденда)
2. Удвойте знаменатель (с побитовыми сдвигами), пока он не станет больше дивиденда
3. Поскольку мы знаем, что наш знаменатель больше нашего дивиденда, мы можем вычесть делитель, пока он не станет меньше дивиденда
4. Верните записанные действия, которые потребовались, чтобы приблизиться к знаменателю как можно ближе, используя делитель

Вот несколько тестовых прогонов:

console.log(divide(-16, 3)); // -5
console.log(divide(16, 3)); // 5
console.log(divide(16, 33)); // 0
console.log(divide(16, 0)); // NaN
console.log(divide(384, 15)); // 25

Вот схема, которая обрабатывает как делитель 0, так и отрицательный дивиденд и / или делитель: https://gist.github.com/mlunoe/e34f14cff4d5c57dd90a5626266c4130

Answer 6

Деление двух чисел без использования /

int div(int a,int b){

    if(b == 0)
         return -1;   //undefined
    else if (b == 1)
         return a;    
    else if(b > 1){

       int count = 0;
       for(int i=b;i<=a;i+=b){
           count++;
       }
    }

    return count;

}

Answer 7

Основная концепция:

Допустим, мы вычислили 20/4, поэтому

4*(1+1) = 8 *(1+1) = 16 *(1+1) == 32 (which is bigger) X
so go back to 16 and try 16*(1+0.5) == 24 (bigger) X
so go back to 16 and try 16*(1+0.25) == 20 

Код:

float product=1,multiplier=2,a=1;
int steps=0;

void divCore(float number, float divideBy,float lastDivison)
{
    steps++;
    //epsilon check e.g (10/3) will never ends
    if(number - divideBy < 0.01)
        return;
    else
    {
        lastDivison = divideBy; 
        divideBy *= multiplier;
        if(number >= divideBy)
        {
            product *= multiplier;
            divCore(number,divideBy,lastDivison);
        }
        else
        {
            a *= 0.5;
            multiplier = 1 + a;
            divCore(number,lastDivison,lastDivison);
        }
    }
}

float Divide(float numerator, float denominator)
{
    //init data
    int neg=(numerator<0)?-1:1;
    neg*=(denominator<0)?-1:1;
    product = 1;
    multiplier = 2;
    a = 1;
    steps =0;
    divCore(abs(numerator),abs(denominator),0);
    return product*neg;
}

Answer 8

Поскольку ОП сказал, что это вопрос интервью, я думаю, что интервьюер хочет увидеть следующие вещи в дополнение к вашим навыкам кодирования.(Предположим, вы используете Java)

1. Как бороться с отрицательными числами?Обычно дивиденды и делители переводятся в положительные числа.Однако вы можете забыть, что Math.abs(Integer.MIN_VALUE) по-прежнему Integer.MIN_VALUE.Поэтому, когда дивидендом является Integer.MIN_VALUE, вы должны рассчитать его отдельно.

2. Каков результат "Integer.MIN_VALUE / -1"?В Integer такого значения нет.Вы должны обсудить это с интервьюером.Вы можете вызвать исключение для этого условия.

Вот код Java для этого вопроса, и вы можете проверить его leetcode: разделите два целых числа :

public int divide(int dividend, int divisor) {

    if(divisor == 0)
        throw new Exception("Zero as divisor!");

    int a = Math.abs(dividend);
    int b = Math.abs(divisor);

    boolean isPos = true;
    if(dividend < 0) isPos = !isPos;
    if(divisor < 0) isPos = !isPos;

    if(divisor == Integer.MIN_VALUE){

        if(dividend == Integer.MIN_VALUE) return 1;
        else return 0;
    }

    if(dividend == Integer.MIN_VALUE) {

        if(divisor == -1){

            // the result is out of Integer's range.
            throw new Exception("Invalid result.");
        } else {
            // Because Math.abs(Integer.MIN_VALUE) = Integer.MIN_VALUE
            // we avoid it by adding a positive divisor to Integer.MIN_VALUE
            // here I combined two cases: divisor > 0 and divisor < 0
            return divide((dividend + b), divisor) - divisor/b;
        }
    }

    int res = 0;        
    int product = b;

    while(a >= b){

        int multiplier = 1;
        while(a - product >= product){

            product = product << 1;// "product << 1" is actually "product * 2"
            multiplier = multiplier << 1;
        }
        res += multiplier;
        a -= product;
        product = b;
    }

    return isPos?res:-res;

}

Answer 9

Вот простой метод деления для целых без использования оператора '/': -

public static int divide(int numerator, int denominator) throws Exception {

    int q = 0;
    boolean isNumPos = (numerator >= 0) ? true : false;
    boolean isDenPos = (denominator >= 0) ? true : false;

    if (denominator == 0) throw new Exception("Divide by 0: not an integer result");

    numerator = Math.abs(numerator);
    denominator = Math.abs(denominator);

    while (denominator <= numerator) {
        numerator -= denominator;
        q++;
    }

    return (isNumPos ^ isDenPos) ? -q : q;
}

Answer 10

Вот один из JavaScript:

function divideWithoutDivision(a, b, precision) {
    precision = precision > 0 ? precision : 10

    var result = 0
    var decimalPosition = 1
    var A = a*0.1
    var howManyTimes = 0

    while (precision--) {
        A = A * 10
        howManyTimes = 0

        while (A >= b) {
            A = A - b
            howManyTimes += 1
        }

        result = result + howManyTimes*decimalPosition
        decimalPosition = decimalPosition * 0.1
    }

    return result
}

document.write('<br>20/3 = ', divideWithoutDivision(20, 3))
document.write('<br>10/3 = ', divideWithoutDivision(10, 3))
document.write('<br>10/4 = ', divideWithoutDivision(10, 4))
document.write('<br>17/14 = ', divideWithoutDivision(17, 14))
document.write('<br>23/4 = ', divideWithoutDivision(23, 4))

Это может быть улучшено путем округления после последнего десятичного знака точности.