Целочисленного деления без использования/или * оператора

Question

Я иду через алгоритмы и datastructures учебник и наткнулся на этот вопрос:

1-28. Напишите функцию для выполнения целочисленного деления без использования либо операторов/или *. Найдите быстрый способ сделать это.

Как мы можем придумать быстрый способ сделать это?

Answer 1

Псевдокод:

count = 0 
while (dividend >= divisor) 
    dividend -= divisor 
    count++ 
//Get count, your answer 

Answer 2

Я не знаю, что вы имеете в виду быстро ... и это похоже на основной вопрос, чтобы проверить свой мыслительный процесс.

Простую функцию можно использовать счётчиком и продолжать вычитать дивизор из дивиденда, пока он не станет 0. Это процесс O(n).

int divide(int n, int d){ 
    int c = 0; 
    while(1){ 
     n -= d; 
     if(n >= 0) 
      c++; 
     else 
      break; 
    } 
    return c; 
} 

Другой способ можно использовать shift оператор, который должен сделать это в log(n) шагов.

int divide(int n, int d){ 
    if(d <= 0) 
     return -1; 
    int k = d; 
    int i, c, index=1; 
    c = 0; 
    while(n > d){ 
     d <<= 1; 
     index <<= 1; 
    } 
    while(1){ 
     if(k > n) 
      return c; 
     if(n >= d){ 
      c |= index; 
      n -= d;     
     } 
     index >>= 1; 
     d >>= 1; 
    } 
    return c; 
} 

Это как целое деление, как в средней школе.

PS: Если вам нужно лучшее объяснение, я сделаю это. Просто опубликуйте это в комментариях.

EDIT: отредактирован код wrt Erobrere's comment.

Answer 3

Обычно, когда в учебниках алгоритмов быстро они означают с точки зрения вычислительной сложности. То есть количество операций на бит ввода. В общем, они не заботятся о константах, поэтому, если у вас есть вход n бит, требуется ли две операции на бит или сто операций на бит, мы говорим, что алгоритм принимает O (n) времени. Это связано с тем, что если у нас есть алгоритм, который работает в O (n^2) времени (многочлен ... в данном случае, квадрат) и мы представляем себе алгоритм O(), который выполняет 100 операций за бит по сравнению с нашим алгоритмом, который может выполнять 1 операцию на бит, как только размер ввода составляет 100 бит, алгоритм полинома начинает работать очень медленно очень быстро (по сравнению с другим алгоритмом). По существу, вы можете представить две строки: y=100x и y=x^2. Возможно, ваш учитель сделал упражнение в алгебре (возможно, это было исчисление?), Где вы должны сказать, какой из них больше, поскольку x подходит к бесконечности. На самом деле это ключевая концепция в расхождении/сближении в исчислении, если вы уже там уже по математике. Независимо от того, с небольшим количеством алгебры, вы можете себе представить наши графики пересекаются в x=100 и y=x^2 быть больше для всех точек, где х больше, чем 100.

Насколько большинство учебников беспокоит, O (nlgn) или лучше считается «быстрым».Одним из примеров очень плохой алгоритм для решения этой задачи будет следующим:

crappyMultiplicationAlg(int a, int b) 
    int product = 0 
    for (b>0) 
     product = product + a 
     b = b-1 
    return product 

Этот алгоритм в основном использует «Ъ» в качестве счетчика и просто продолжает добавлять «а» до некоторой переменной для каждого времени б отсчитывает. Чтобы вычислить, насколько «быстрый» алгоритм (с точки зрения алгоритмической сложности), мы подсчитываем, сколько будет выполняться разных компонентов. В этом случае мы имеем только цикл for и некоторую инициализацию (которая в этом случае незначительна, игнорирует ее). Сколько раз работает цикл for? Вы можете сказать: «Эй, парень! Он работает только« b »раз! Это может быть даже не половина вход. То есть путь лучше чем O (n) время!"

Хитрость здесь в том, что мы имеем дело с размером входа с точки зрения хранения ... и все мы (должны) знать, что для хранения п разрядное целое число, нам нужно Л.Г. n бит. Другими словами, если у нас есть бит x, мы можем сохранить любое (без знака) число до (2^x) -1. В результате, если мы используем стандартное 4-байтовое целое число, это число может составлять до 2^32 - 1, что является хорошим числом в миллиардах, если моя память служит мне правильной. Если вы не доверяете мне, запустите этот алгоритм с числом, равным 10 000 000, и посмотрите, сколько времени потребуется. Все еще не убежден? Используйте номер long, чтобы использовать номер, например, 1,000,000,000.

Поскольку вы не просили помощи в алгоритме, я оставляю его для вас как упражнение по домашнему заданию (не пытаясь быть рывком, я - проблема с полным выводом и любовью). Если вам нужна помощь, не стесняйтесь спрашивать! Я уже набрал некоторые подсказки случайно, так как я не читал ваш вопрос правильно сначала.

EDIT: Я случайно сделал дерьмовый умножение алгоритм. Примером страшном алгоритма действительно разделением (я изменял) будет:

AbsolutelyTerribleDivisionAlg(int a, int b) 
    int quotient = 0 
    while crappyMultiplicationAlg(int b, int quotient) < a 
     quotient = quotient + 1 
    return quotient 

Этот алгоритм плохо для целого букета причин, не в последнюю очередь из которых является использование моего дерьмовый алгоритма умножения (который будет называться более одного раза даже при относительно «ручном» запуске). Даже если бы нам разрешили использовать оператор *, хотя это по-прежнему очень плохой алгоритм, во многом благодаря тому же механизму, который использовался в моем ужасном мультиальге.

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

Answer 4

unsigned bitdiv (unsigned a, unsigned d) 
{ 
unsigned res,c; 

for (c=d; c <= a; c <<=1) {;} 

for (res=0;(c>>=1) >= d;) { 
     res <<= 1; 
     if (a >= c) { res++; a -= c; } 
     } 
return res; 
} 

Answer 5

Самый простой способ выполнить деление является последовательным вычетах: вычесть b из a, пока a остается положительным. Фактор - это количество вычитаний.

Это может быть довольно медленно, так как вы будете выполнять q вычитания и тесты.

С a=28 и b=3,

28-3-3-3-3-3-3-3-3-3=1 

фактор является 9, а остальные 1.

Следующая идея, которая приходит на ум, состоит в том, чтобы вычесть несколько раз b за один проход. Мы можем попробовать с 2b или 4b или 8b ... так как эти числа легко вычислить с дополнениями. Мы можем идти как можно больше, если кратность b не превышает a.

В примере, 2³.3 является наибольшим кратным что возможно

28>=2³.3 

Таким образом, мы вычитаем 8 раз-в одном ходе, получая

28-2³.3=4 

Сейчас мы продолжаем уменьшать Остаток с нижним кратными, 2², 2 и 1, когда это возможно

4-2².3<0 
4-2.3 <0 
4-1.3 =1 

Тогда наш коэффициент 2³+1=9, а остаток 1.

Как вы можете проверить, каждый раз из b судится один раз, а общее количество попыток равно количеству удвоений, необходимых для достижения a. Это число - это просто количество бит, необходимых для записи q, что намного меньше, чем q.

Answer 6

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

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

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

    return result; 
} 

1. Мы инициализируем наш результат 1 (так как мы собираемся удвоить знаменатель, пока это не больше, чем дивиденд)
2. Двойной наш знаменатель (с побитовыми сдвигами) до тех пор, пока он не станет больше дивиденда
3. Поскольку мы знаем, что наш знаменатель больше нашего дивиденда, мы можем минус наш дивизор до тех пор, пока он не станет меньше нашего дивиденда.
4. Результат возврата, поскольку знаменатель теперь находится как можно ближе к результат, используя делитель

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

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

Здесь перекачивает суть оба в случае 0 делителем и отрицательный дивиденд и/или делитель: https://gist.github.com/mlunoe/e34f14cff4d5c57dd90a5626266c4130