troubleshooting Question

How to compute the modulus of a number without a division operator ?

Avatar of HukkaHua
HukkaHua asked on
CAlgorithms
5 Comments2 Solutions1278 ViewsLast Modified:
Hi Folks,

This is another of the ones which I am not being able to understand :

Compute modulus division by (1 << s) - 1 without a division operator

unsigned int n;                      // numerator
const unsigned int s;                // s > 0
const unsigned int d = (1 << s) - 1; // so d is either 1, 3, 7, 15, 31, ...).
unsigned int m;                      // n % d goes here.

for (m = n; n > d; n = m)
{
  for (m = 0; n; n >>= s)
  {
    m += n & d;
  }
}
// Now m is a value from 0 to d, but since with modulus division
// we want m to be 0 when it is d.
m = m == d ? 0 : m;

Any help is greatly appreciated.

Thanks,
H
Join the community to see this answer!
Join our exclusive community to see this answer & millions of others.
Unlock 2 Answers and 5 Comments.
Join the Community
Learn from the best

Network and collaborate with thousands of CTOs, CISOs, and IT Pros rooting for you and your success.

Andrew Hancock - VMware vExpert
See if this solution works for you by signing up for a 7 day free trial.
Unlock 2 Answers and 5 Comments.
Try for 7 days

”The time we save is the biggest benefit of E-E to our team. What could take multiple guys 2 hours or more each to find is accessed in around 15 minutes on Experts Exchange.

-Mike Kapnisakis, Warner Bros