StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>There is almost certainly a more elegant way to do it, but here's enough to get you started.</p> <p>Usually division in this way is done by multiplying by the reciprocal, i.e., first multiplying and then right-shifting.</p> <p>(Note: remember that multplication can be accomplished by shifts and adds (e.g. <code>n * 3 = (n*2) + (n*1) = (n << 1) + (n) )</code> but I'm just going to use multiplication here. Your question said "shifts & adds" and I'm justifying my shorthand use of multiplication)</p> <p>In the examples below, I'm trying to explain the concepts with an example. In your specific case, you'll want to consider issues such as</p> <ol> <li><p>sign (I'm using unsigned ints below)</p></li> <li><p>overflow (below I'm using 32-bit unsigned longs to hold intermediate values but if you're on a smaller uC beware, adjust accordingly</p></li> <li><p>rounding (e.g. should 9/5 return 1 or 2? In C, it's 1, but maybe you want 2 because it's closer to the correct answer?)</p></li> <li><p>To the extent that you can (available bits), do your all of your multiplies before your divides (minimizing truncation errors). Again, be aware of overflow.</p></li> </ol> <p>As I said, read the below to understand the concepts, then tailor to your needs.</p> <p>Dividing by 192 is the same as multiplying by 1/192, which is the same as dividing by (64 * 3). There is not an exact (finite) binary representation of 1/3, so we're approximating it with 0x5555/(1 << 16).</p> <p>To divide by 192, we divide by 64 and then divide by 3. To divide by 3, we multiply by 0x5555 and shift right by 16 (or multiply by 0x55 and >> 8, or...)</p> <pre><code>// 8000/192 = // ((8000/64)/3) = // ((8000 >> 6) / 3) = // (((8000 >> 6) * 0x5555) >> 16) // (((8000 * 0x5555) >> 22 </code></pre> <p>Please note that the parentheses are intentional. You <strong>don't</strong> want to compute <code>(8000 * (0x5555/(1 << 16))</code> because the 2nd term is 0, and the product would be 0. Not good. </p> <p>So a 1-liner in code would be something like:</p> <pre><code> printf("Answer: %lu\n", ((8000UL * 0x5555UL) >> 22)); </code></pre> <p>This will yield 41, which is what "C" would yield for <code>8000/192</code>, even though 42 is "closer". By checking LSBs you could round if you wanted to.</p> <p>One could write a treatise on this topic, but fortunately <strong><a href="http://www.cs.uiowa.edu/~jones/bcd/divide.html">someone much smarter than me already has</a></strong>.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload