title: Fixed-point unsigned division in C
body: <p>I need an algorithm to do unsigned fixed-point division in C. I can use at most 32-bit words.</p>
  
  <p>I want to minimize the number of bits needed to represent the integer part while being able to use numbers in the range [0..15]. So apparently the minimum number of bits is 4. Problem is the algorithm which I came up only works using 5 bits. Because it compares the remainder with the divisor and then shifts the remainder until it is bigger than the divisor, if the divisor has the most significant bit 1, then the algorithm will do nothing but shift the remainder (it will never be bigger). Here's the code:</p>
  
  <pre><code>int divu(int a, int b){
     int pt_int, r, pt_frac=0;
     int i;
  
     pt_int = ((unsigned) a/b) &lt;&lt; BITS_FRAC;
     r = (unsigned) a%b;
  
     for (i=BITS_FRAC; i&gt;=0; i--){
        if ((unsigned) r &lt; b)
           r &lt;&lt;= 1;
        else{
           r -= b;
          pt_frac += 01 &lt;&lt; i;
          r &lt;&lt;= 1;
        }
     }
     return pt_int + pt_frac;
  }
  </code></pre>
  
  <p>If you do have a solution but don't want to understand the code, please, just post it. :)</p>
  
  <p>Example:</p>
  
  <p>We want to divide 1.5 by 2, which results 0.75. Suppose we are using 4 bits for the integer part and 28 bits for the fraction. So our numbers is hex are:</p>
  
  <pre><code>1.5:    0x18000000
  2:      0x20000000
  result: 0x0c000000 
  </code></pre>