Bitshifts to obtain remainder

bit-manipulation, java, number-theory

Solution

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`.

Problem

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

Original source