Bitshifts to obtain remainder

Question

I want to know how to obtain the remainder by dividing an integer with another integer (both positive) using bitshift or bitwise operators only. The / operator or % operator should not be used.

For example, for obtaining the remainder when divisor is of the form 2^k the following operation yields the remainder.

m = Remainder

n = The number

d = The divisor

m = n & ( d - 1 )

However this method works only when d is of the form 2^k . I want to know a similar method for non-powers of 2. I am currently working on a problem from programming challenges and want to employ such a method to reduce program execution time

Answer 1

Any answer that doesn't use the operator % will be a less efficient answer, but, if you absolutely cannot use the operator, then, one solution is to use a loop to subtract d from n repeatedly:

m = n;
while (m >= d)
{
  m -= d;
}

Assuming that your integers are 32-bit, then you can consider an optimized version where we delete multiples of d from n:

m = n;
for (i = 31; i >= 0; i--)
{
  di = d << i;
  if (di > 0 && m >= di) m -= di;
}

This example, assumes the integers are signed and watches for overflow i.e. the test for di > 0.