Деление без использования оператора «/»
Я не могу использовать ‘/’ и циклы, и я должен разделить некоторые числа.
операнды 32-битные, и я не могу использовать рекурсию.
Я подумал об использовании shr, но он дает мне только 2 ^ n деления и также не спасет напоминание.
есть идеи?
Решение
#include <stdio.h>
#include <stdlib.h>
int main()
{
div_t output;
output = div(27, 4);
printf("Quotient part of (27/ 4) = %d\n", output.quot);
printf("Remainder part of (27/4) = %d\n", output.rem);
output = div(27, 3);
printf("Quotient part of (27/ 3) = %d\n", output.quot);
printf("Remainder part of (27/3) = %d\n", output.rem);
return(0);
}
Выход:
Quotient part of (27/ 4) = 6
Remainder part of (27/4) = 3
Quotient part of (27/ 3) = 9
Remainder part of (27/3) = 0
Другие решения
Попробуйте этот метод на основе магических чисел:
Я реализовал это на основе этого ссылка на сайт
Это полезно только с фиксированным делителем.
#include <iostream>
#include <cmath>
using namespace std;
int main() {
// your code goes here
unsigned long MAX_NUM=1<<30; //Max num = 1073741824
unsigned long num = 1073741824;
unsigned long divisor=17;
//unsigned long magic_num=round(double(MAX_NUM)/divisor);
unsigned long magic_num = 63161284 // Fixed for divisor = 17
unsigned long div = (num * magic_num) >> 30;
unsigned long remain = num - div * divisor;
cout << div << endl;
cout << remain << endl;
return 0;
}
Если это академическое упражнение, они, вероятно, хотят, чтобы вы сделали:
a / b :: == e ** (log (a) — log (b))
int a_div_b( int a, int b, int pow=0 ) {
if (a<b) return 0;
if (a < (b<<(pow+1)))
return a_div_b(a-(b<<pow), b) + (1<<pow);
return a_div_b(a, b, pow+1);
}
Нет петель, нет /, O((log(a/b))^2) время. Я мог бы улучшить O(log(a/b))но я ленивый вниз от максиму пау как только найдешь, а не обратно).
Остаток может быть легко рассчитан с помощью b-a_div_b(a,b)*a без использования петель или /,
Он должен использовать O (1) памяти, так как он хвостовой рекурсивен.
detector