Неподписанное деление с фиксированной точкой в ​​C

Question

Мне нужен алгоритм для деления без знака с фиксированной запятой в C. Я могу использовать не более 32-битных слов.

Я хочу минимизировать количество битов, необходимых для представления целой части, при возможности использования чисел в диапазоне [0..15]. Таким образом, по-видимому, минимальное количество бит равно 4. Проблема в том, что алгоритм, который я придумал, работает только с использованием 5 бит. Поскольку он сравнивает остаток с делителем, а затем сдвигает остаток до тех пор, пока он не станет больше делителя, если у делителя самый старший бит 1, алгоритм ничего не сделает, но сместит остаток (он никогда не будет больше). Вот код:

int divu(int a, int b){
   int pt_int, r, pt_frac=0;
   int i;

   pt_int = ((unsigned) a/b) << BITS_FRAC;
   r = (unsigned) a%b;

   for (i=BITS_FRAC; i>=0; i--){
      if ((unsigned) r < b)
         r <<= 1;
      else{
         r -= b;
        pt_frac += 01 << i;
        r <<= 1;
      }
   }
   return pt_int + pt_frac;
}

Если у вас есть решение, но вы не хотите понимать код, просто опубликуйте его. :)

Пример:

Мы хотим разделить 1,5 на 2, что дает 0,75. Предположим, что мы используем 4 бита для целой части и 28 бит для дроби. Итак, наши числа шестнадцатеричные:

1.5:    0x18000000
2:      0x20000000
result: 0x0c000000 

Answer 1

У вас есть номер с фиксированной точкой 4,28, и вы хотите разделить на число 4,28. Вы находите точность после деления, вычитая точность числителя из знаменателя, поэтому прямое деление даст 4,28 - 4,28 = 0 - без значащих битов. Очевидно, это не сработает.

     1.5  [4.28] 0x18000000 
   / 2.0  [4.28] 0x20000000 
   =  0?  [0.00] 0x00000000

Идеальный способ сделать это - повысить числитель до 8,56 (умножив на 2 ^ 28), а затем выполнить 64-разрядное деление:

                     .   .   .   .
     1.5  [8.56] 0x180000000000000
   / 2.0  [4.28]        0x20000000 
   = 0.75 [4.28]        0x0c000000

Если вы действительно не можете использовать 64-битные числа, тогда ваш единственный вариант - уменьшить знаменатель. Например, вы можете использовать половину точности, разделив на 2 ^ 14

     1.5  [4.28] 0x18000000 
   / 2.0  [2.14]     0x8000
   = 0.75 [2.14]     0x3000

Затем вы можете умножить результат на тот же коэффициент, чтобы вернуться к числу 4,28: 0x3000 *(1<<14) = 0x0c000000

Вы теряете некоторую точность таким образом, но это неизбежно без использования больших числителей. Например 5.0/3.0 = 1.66667 = 0x1AAAAAA [4.28], но
((5.0<<28)/(3<<14))<<14 = 0x1AAA8000 [4.28] = 1.66662

Answer 2

Как указано здесь (Пример: умножение целого числа на обратную величину константы), вы можете повторно реализовать свое деление путем умножения на обратную величину.После этого вы сможете представить целую часть с 4 битами.