Code a division operation by a specific value without a division operator?

Even though the semester is already done, I've decided to continue this blog because its a great way to keep track of what I've learned and practice my writing. Also, because I didn't start the year right, this is my way of getting myself back on track!

Anyway, the subject of this post was asked to me and my colleagues by one of our seniors. He told us that back then there weren't much and they encountered this odd problem while on a project. At first, subtracting the dividend by the divisor while counting the number of times it has been subtracted seemed like a good idea but this solution is very slow. We got the right solution thanks to my colleague IC.

Objective: Divide any given number by a specific number without using the divider operation.

Conditions:
1. The process of multiplication, addition and bit shifting are available.
2. The memory registers are larger than the size of the integer to be divided.
3. Floating point numbers are not supported.

Sample Case: Divide any given 16-bit integer by 48 using a 32-bit register.

Solution:

Let x be the given number, d be the divisor and c be the constant multiplier which is divisible by two.

Hint: x/d is just equal to (x*c)/(d*c )

1. Determine a constant value of 1/48 which will be used as part of the multiplier. Note that a number divided by 48 is equal to that same number multiplied by 1/48:

1/48 = 0.020833333333333333333333333333333

2. Choose a multiplier that will not cause an overflow by dividing the size of the register to the maximum integer value. We are just looking for a specific multiplier that when multiplied by 0xFFFF (the maximum value for a 16 bit integer), will not be greater than 0xFFFFFFFF (the 32-bit register):

(0xFFFF * 1/48)c <= 0xFFFFFFFF so,
c = 0xFFFFFFFF / (0xFFFF * 1/48) = 0x300030 = 0b1100000000000000110000

3. Reduce this number into the highest number divisible by two because we can only use shift operations:

0b1100000000000000110000 can be reduced to 0b1000000000000000000000 which can easily be obtained since this is just 1 << 21.

4. Multiply the inverse constant of the divider by the number above:

0.20833333333333333333333333333333 * 0b1000000000000000000000 = 43690

5. To prevent any round down errors, round up the constant multiplier by adding one:

43690 + 1 = 43691

6. Multiply this constant to the given integer number and divide it with the same multiplier from step 3.

The final equation would then be the following:

(x * 43691) >> 21
Which is accurate until 1 << 15

I'm not a Math wizard so corrections, comments and suggestions are very much welcomed! ^_^