Dividing an integer by (N + 1/2) where N is an integer and rounding
the quotient towards zero not any more difficult than plain integer
division. (N + 1/2) can also be expressed as (2N+1)/2. Simply shift
both the dividend and N (the divisor minus 1/2) left by one bit
(multiplication by 2) and add 1 to 2N. Find the integer quotient of
twice the dividend divided by (2N+1), chop off the least significant
bit and you're left with the desired result!
There are several ways to perform integer division. They range from the
simple but agonizingly slow...
// this takes O(2^N) time where N is number of bits
remainder := dividend;
quotient := 0;
while remainder >= divisor do
remainder := remainder - divisor;
quotient := quotient + 1;
end while
...to the faster but more complicated
circuits detailed here
and here.
|