Are there any effective many-to-one algorithms without using modulo operator?-CodePudding

Given a set containing 1~N and I tried to fairly map them into one of M slots (N > M). I think this is many-to-one mapping problems.

The naive solution is using modulo operator, given N = 10 and M = 3, we can do mapping like:

N   M

1 % 3 = 1 (assign to 2nd slot)
2 % 3 = 2 (assign to 3rd slot)

...

9 % 3 = 0 (assign to 1st slot)

This solution seems pretty fair but takes expensive operator. Are there any existing algorithm to take care of this kind of problem?

Thanks in advance!

CodePudding user response：

It is debatable if % is a slow operator, but bit manipulation is faster. If you are happy to map into a number of bins that are a power of two, N=2^k, then you mask out the lower k bits

x & ((1 << k)-1);

If the number of buckets is a Mersenne prime, N = 2^s-1 there is also a quick way to get the remainder:

unsigned int mod_Mersenne(unsigned int x, unsigned int s)
{
     unsigned int p = (1 << s) - 1;
     unsigned int y = (x & p)   (x >> s);
     return (y > p) ? y - p : y;
}

I believe you can also do it branchless, but I don’t remember how.