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

Rosado

Wouldn't the fact that the bit representation is only in base-2 be a limitation? Consider the value 43/7 - the value is actually 6.142857... . What generic approach have you considered for a value in a base higher than 2? – Valida

There is no general method. You can replace the division with a multiplication and some shifts and additions/subtractions if you know the divisor, though. Ask any competent C compiler about it, and it will give you the magic values for any compile time constant. – Chrissychrist

Unless the answer involves only 1 bitshift statement, I'd bet you don't beat javas mod operator. – Garling

@rambocoder If you hardcode the magic multiplier and shift distances, it should beat a division on most CPUs. But that is of course limited to divisors you know at compile time. – Chrissychrist

I found this link. It alone doesn't qualify for an answer, but it's probably enough to get you on your way. – Valida

@Valida The above approach works for a value in a base higher than 2. However all the numbers have to be converted to binary beforehand. Most compilers inherently work with binary numbers.So this should not be a problem – Rosado

Modulus is already very fast (the IDIV opcode in x86 or amd64 already calculates modulus; it takes ~30 ticks to do so). I really doubt that slow divisions are the problem - there is probably an algorithm that requires less operations (not necessarily faster) as the answer. – Affricative

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.

Rafe

unfortunately, an overflowing shift doesn't necessarily result in a negative number, even if you assume a normal 2s-complement machine. – Herbalist